diff options
author | Aleteoryx <alyx@aleteoryx.me> | 2024-12-10 15:13:28 -0500 |
---|---|---|
committer | Aleteoryx <alyx@aleteoryx.me> | 2024-12-10 15:13:28 -0500 |
commit | 6e83f9b78fb203296dc2307e81304aff4b4a2998 (patch) | |
tree | 20f7345e18caefddb13b8415a5b83246d3e9b47c /2024/tcl | |
parent | 4e699214a9fc35ede70becbd7f5e242732a8c50c (diff) | |
download | adventofcode-master.tar.gz adventofcode-master.tar.bz2 adventofcode-master.zip |
Diffstat (limited to '2024/tcl')
-rwxr-xr-x | 2024/tcl/10.tcl | 99 | ||||
-rwxr-xr-x | 2024/tcl/templ.tcl | 2 |
2 files changed, 99 insertions, 2 deletions
diff --git a/2024/tcl/10.tcl b/2024/tcl/10.tcl new file mode 100755 index 0000000..2e285bd --- /dev/null +++ b/2024/tcl/10.tcl @@ -0,0 +1,99 @@ +#!/bin/env tclsh + +source lib.tcl +setup 10 grid + +puts {Part 1: Count paths from trailheads} + +set endpoint_cache {} + +# get trail endings +set to_check {} +for {set x 0} {$x < $input(w)} {incr x} { + for {set y 0} {$y < $input(h)} {incr y} { + set cell [lindex $input(grid) $y $x] + if {$cell == 9} { + lappend to_check $y $x $y $x + dict set endpoint_cache [list $y $x] [list $y $x] 1 + } + } +} + +# BFS mark all cells +while {$to_check != {}} { + set new_to_check {} + foreach {y x end_y end_x} $to_check { + set cell [lindex $input(grid) $y $x] + foreach {y x} [list [expr {$y-1}] $x [expr {$y+1}] $x $y [expr {$x-1}] $y [expr {$x+1}]] { + if {$y >= $input(h) || $y < 0 || $x >= $input(w) || $x < 0} continue + if {[lindex $input(grid) $y $x] != $cell - 1} continue + if ![dict exists $endpoint_cache [list $y $x] [list $end_y $end_x]] { + dict set endpoint_cache [list $y $x] [list $end_y $end_x] 1 + lappend new_to_check $y $x $end_y $end_x + } + } + } + set to_check $new_to_check +} + +# check all trailheads +set paths_count 0 +for {set y 0} {$y < $input(h)} {incr y} { + for {set x 0} {$x < $input(w)} {incr x} { + set cell [lindex $input(grid) $y $x] + if {$cell == 0} { + incr paths_count [llength [dict keys [dict get $endpoint_cache [list $y $x]]]] + } + } +} + +puts "Count: $paths_count" + +puts "" +puts {Part 2: DFS all paths from every trailhead} + +set dfs_cache {} +set dfs_total 0 +for {set x 0} {$x < $input(w)} {incr x} { + for {set y 0} {$y < $input(h)} {incr y} { + set cell [lindex $input(grid) $y $x] + if {$cell == 0} { + set cursors {} + lappend cursors {} $y $x + + while {$cursors != {}} { + set cursors [lassign $cursors hist cy cx] + set cell [lindex $input(grid) $cy $cx] + + if {[dict exists $dfs_cache [list $cy $cx]]} { + set incr [dict get $dfs_cache [list $cy $cx]] + foreach {hy hx} $hist { + dict incr dfs_cache [list $hy $hx] $incr + } + + continue + } + + if {$cell == 9} { + foreach {hy hx} $hist { + dict incr dfs_cache [list $hy $hx] + } + + continue + } + + foreach {ny nx} [list [expr {$cy-1}] $cx [expr {$cy+1}] $cx $cy [expr {$cx-1}] $cy [expr {$cx+1}]] { + if {$ny >= $input(h) || $ny < 0 || $nx >= $input(w) || $nx < 0} continue + if {[lindex $input(grid) $ny $nx] != $cell + 1} continue + + set cursors [linsert $cursors 0 [concat $hist $cy $cx] $ny $nx] + } + } + + incr dfs_total [dict get $dfs_cache [list $y $x]] + } + } +} + + +puts "Total: $dfs_total" diff --git a/2024/tcl/templ.tcl b/2024/tcl/templ.tcl index 51a96ff..fae0842 100755 --- a/2024/tcl/templ.tcl +++ b/2024/tcl/templ.tcl @@ -8,8 +8,6 @@ puts {Part 1: } foreach line $input { } -close $input - puts "1: $" puts "" |