blob: 0efa76f5dcf74fd627528ed9cce026cf84f0bf2b (
plain)
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#!/usr/bin/env tclsh
set fp [open input r]
set map ""
while {1} {
set ret [gets $fp line]
if {$ret == -1} {
break
}
if {[string length $line] == 0} {
break
}
lappend map $line
}
close $fp
proc char_at {x y} {
set line [lindex $::map $y]
return [string index $line $x]
}
set height [llength $map]
set width [string length [lindex $map 0]]
proc find_start {} {
for {set i 0} {$i < $::width} {incr i} {
for {set j 0} {$j < $::height} {incr j} {
if {[char_at $i $j] == "^"} {
return "$i $j"
}
}
}
}
set start_point [find_start]
proc front_point {x y direction} {
if {$direction == "up"} {
return [list $x [expr {$y - 1}]]
} elseif {$direction == "down"} {
return [list $x [expr {$y + 1}]]
} elseif {$direction == "left"} {
return [list [expr {$x - 1}] $y]
} elseif {$direction == "right"} {
return [list [expr {$x + 1}] $y]
}
}
proc out_of_range {x y} {
return [expr {
($x < 0) || ($x >= $::width) || ($y < 0) || ($y >= $::height)
}]
}
proc turn_right {direction} {
if {$direction == {up}} {
return right
} elseif {$direction == {down}} {
return left
} elseif {$direction == {right}} {
return down
} else {
return up
}
}
proc next_state {x y direction} {
set forward [front_point $x $y $direction]
if {[out_of_range {*}$forward]} {
return [list {*}$forward $direction]
}
while {[char_at {*}$forward] == {#}} {
set forward [front_point $x $y [turn_right $direction]]
set direction [turn_right $direction]
}
return [list {*}$forward $direction]
}
proc will_loop {} {
global start_point
set state [list {*}$start_point up]
set past_states {}
while {1} {
if {[out_of_range {*}[lrange $state 0 1]]} {
return 0
}
if {[dict exists $past_states $state]} {
return 1
}
dict set past_states $state { }
set state [next_state {*}$state]
}
}
proc set_obstruction {x y} {
global map
set orig_line [lindex $map $y]
lset map $y [string replace $orig_line $x $x "#"]
}
proc clear_obstruction {x y} {
global map
set orig_line [lindex $map $y]
lset map $y [string replace $orig_line $x $x "."]
}
set count 0
for {set i 0} {$i < $width} {incr i} {
for {set j 0} {$j < $height} {incr j} {
if {[char_at $i $j] == "^"} {
continue
}
if {[char_at $i $j] == "#"} {
continue
}
set_obstruction $i $j
if {[will_loop]} {
set count [expr {$count + 1}]
}
clear_obstruction $i $j
}
}
puts $count
|
