diff options
| -rw-r--r-- | 2024/input.10.txt | 60 | ||||
| -rwxr-xr-x | 2024/tcl/10.tcl | 99 | ||||
| -rwxr-xr-x | 2024/tcl/templ.tcl | 2 |
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 "" |