blob: 2e285bdea4f334b07badb087baa88706db8214e9 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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"
|
