2024.10HEADmaster

3 files changed, 159 insertions, 2 deletions

diff --git a/2024/input.10.txt b/2024/input.10.txt
new file mode 100644
index 0000000..94d285f
--- /dev/null
+++ b/2024/input.10.txt
@@ -0,0 +1,60 @@
+432109865210212123765432101234321098543289654320132112121058
+045678774324301012892343023445456787650198763013241001034569
+187678789465692321001056014896234986456787012894653212123678
+296589921056789433217837895687145675323891233765784589238987
+345437835434576544786921278761010014210710321212098676521067
+032126546323465435695430789760121223121653450303145125430678
+123010567810156543212345699859834321056544067654236012321589
+543213498987657665401030787348765430187432198765987622345432
+654100332394348972342321895201256589196343089543212331056741
+789011241003238981089400776100343678015434567630105449879870
+296721256210169895676510385011892349101325678921256756768987
+129830787323456765410321294332761058210012310123890891057610
+056745698234556786329454301245656567341110567894781232346521
+145894510149645699438765892398305678956923498965654343765430
+236586789838732388454326765567214307967845697874505652894321
+105675676545321267565810674354303212875430786543216701678912
+234321501656130054278989983289432120123421803403545810787600
+321030432567032123123678100176563018987578912012932921298541
+892349803498145031034563210327898101879647810123871092567432
+785056712387236567687654389410787632768756303294562783458943
+176120987656547858998545076585894583459843214785103698327874
+015431234543218947657898145894983298708941025672234567016761
+329122345692105438941763236783470165617652912341013053205430
+478031001785676323430154100102565674320543805432332122124321
+567649872434985610121894321211056589211230796901440345034234
+456659763323810765456765894323987401108921687878981236565105
+306778654310329876365498765012342322317834510967892387156076
+219865011078478901278321001231451015436123423456785493087189
+652104102569560110669125198340760896895034587655476334196892
+765233243458721321701034567654878987764105694344301243234561
+894310321029832459852567878723965430653298743213210358765410
+132123478010741069743478989014436321541056543401821569898324
+098034569123658978654321876101521087632347812114981678876543
+107765678034567867569270965437698794545938903003470549987432
+256872345621098654378187602348967003897821094012561232789501
+345901436438767789210094511059854112766123285723034341076521
+217894387589656231234543223456743245675054176894125652112430
+306105498678543140567672100145101230984169065765898763203431
+495218321067012056478981041234230121243078434965235678976521
+584349452652100987329891230765345698732154567874143454989210
+673458763643211011010010049874556781235463456963056763474321
+567647601781012567892102156743765470346322161012369812565232
+498678432692123476543103095652834387457210052623871001450143
+304509543543001989698234589501921098768921106780982341019898
+213219601982132670787825676501432349810123235691987432870767
+894348732676544561236910787432321056769894344302346549961251
+765210145690125650345210097899867892110765654219854678450340
+890100126780034743094303126934786543023234565678765012321231
+765987034621129802185412235025696541032167876789874349876012
+876856541234988012276543384110567832249054965694101256778123
+965987650945876543543215493201378980158345434783450126789894
+457871056876067875456906780110234589267210321692569034670765
+320432347780128965307878767820199674307890160541078765521254
+011876548991234534218349856936788765216543254332112340432345
+432965432781049621029256743245215656325321067210003451201056
+547876501632898756540178652101304567101452198760116764342767
+656983432542765987438769789012453898212968765641985895433898
+898792323101874104329054210589562456703879454332076016924567
+125601017652963265012123323676571329894312303549165327810430
+034340178943012378901012334568980016765601212678234456901321
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 ""