path: root/2024/tcl/10.tcl

#!/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"