2024.10HEADmaster

1 files changed, 99 insertions, 0 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"