-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday06.py
224 lines (199 loc) · 19.4 KB
/
day06.py
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
import marimo
__generated_with = "0.9.26"
app = marimo.App(width="medium")
@app.cell
def __():
data = """........#.............................................#.........#..............#.......#....................#....................#
......................#........#........................#.............##............................#.#.............#..........#..
....#..................................#..................#.........#....#..............#..#......................#........#...#..
.....#...#...............#................#..........................#......#.....................#.......................#.......
......................................................##.#....#..................................................................#
#....#....................#..................................#.....................................#......................#.......
.......#...........................#.......................#......#...#.................................................#...#.....
....................##..........................#................#..........................#.#..................#....#.........#.
#..................................#...............#...............#.........................#............##......................
.............................#....................................#...............#.........#..........#.......................#..
.................................#............###.......#............##......#...............................#...............#.#..
.#..........................................#.......#.......................##..#........#........#...............#...............
......#...#............#.#..............#...................#..........................................................##.........
#................##....................................................................#........#.................#...#...........
...#..........#..........................##......#....#..............................#......................................#.....
..............................##.#..........................................................#..............................#......
......#...........#....#..................#............#....................................................................#.....
.....................#........................#.......................................................#...........................
...................#.#..........................................................................................#.#...............
.........................................##.........................................................#.......#...###......#........
...............................................................##.......................#..........................#..............
...#...........#.................#..............#......#.....#..........................#....................#....#...............
.................................#................#................#..............................................#.......##.....#
........#..........................#................#.......................#...................#.................................
.............................#.............................#..........#.........................#........#........................
....#................#.#................#...........................................................#...#....#......#......#......
........#..............................#...............................#.................#........................................
...........................................#..#........#...#...........#..#.............#.........................................
.#.................#.#................................#................#.#..................................#........#............
.......#..........................................#.................................................................#.............
...................#....................................................#..#...............................................#......
...#.#........#...#.....#.....................................................................................................#...
......#.........................#......................#.............#.....................#......................................
..........................#............#.................................#..#..........#........#......................#..........
...#..#......#.......................#........................#...................................................................
............#...........#................#..............#.........................................................................
.#........#....#.........................................#........................................#...............................
...#......................##.........#.......#.#...........#................................................#...#.................
...........#......#.........#....#.....#.......................................................#.............#....................
.............#...#..............................................#.........#.....##....................#...#.........#.............
...............#................................#..........................................#.....#.#.........................#...#
................#.....#..#.............#..............#..............#.......#....................................................
......#.........................................................................................................#.........##......
..#...........................#.#...........................................#..#.....#............................................
...#...#..................#..................................#.........#...................#..................................#...
............#..#.....................#.........................................#.......#..................................#.......
...#.......................................................................#.............................#........................
......#..................#....................................#......##...........................................................
.#...............#.....#..........................................................................................#...............
...#.............#.........................#.....................#...#..........#....#............................#...............
...#............................#.......#...........#.........#........#.....#...........#...................................#....
.....................#...................#................................#...............................#......#.........#..##..
.............#........................................................................................#........................##.
.....#.......#.......#............................................................................................................
............................................#................................................................#..............#.....
....#..#......................................................#...................................................#...............
.................................#...##..................#.................................................#....#.................
........#...................................#...#..........................................................#......................
........................#........##...........#.......#........#...................................#..............................
...........#...#...................................................#..............#......#...............#.#..................#...
........#.............................................#...........................................................................
........#................#......#..........#..#........#.#.......#...#........................#..#......................#.......#.
.......#..........................................................................................................#.....#.....#...
......................##....................#.....#.................#...........#.......................#.##..........#......#....
....................................##....................................................................#.................#.....
..#.................................#.#...........#............................................#....#.............................
#...................................#...........................................#............#.........#...............#..........
.......................#.............................................................#..........#...#.............#.....#.........
#..................#.#.............................................................................#.................#............
.....................#......#.......#...........#..........................................^...............................#......
................................#......................#.#.....#..............#..................#....#.#......#....#.............
............................................................................#........#.....................................#......
.............#......................................................#...................................#......##..#....#.........
...............#.................#...................#...............#............................................................
..............#...........#..#...........................................#...................................#..........#.........
..........#...........................#...................#..............#...#.......#..........#...................#.............
.............#.#..................................#....#..#............#.....................#................#...#.....#.........
...................#..........................................................#............##.....................................
...........................................#............#........................................................................#
..#..............................#....#...........................................................................................
..#..#............#...........................#...#...........#............#.....#.................#..............................
....#...................#.........#...............................................................................................
.......#..........................#....................................##........#.................##...#.#........#..#...........
.#........................#....#.......#.....#...................#.............................................#..................
..#...............................................................#................................................#..............
.....#........................................#...................................................................................
..........................................#..........................................................#............................
....................###.........................#............................#...#...........#............#.......................
.....#.....#...............#........#.#....#...................#...........#........#...........#.................................
................................................................................................#...##............................
......................#............#.........................#.......................#.....#...........#...#.#....................
............................#....................#..................#..............#..................................#...........
...........................#...................................#..............................................................#...
..................#................#.....................#...................#........#..............#............................
............#.............#.....................#..................#.........#......................#............#............#...
....#..........................#...............................................................................................#..
................#.....................................#.............................#...........#........................#........
#.##...........#.........................................#...............#..........................................#.#...........
........................................#..............#.....................#............#.....#.................................
.......#....##..#..#.....#........................................................................................................
....##.............#..............................#...............................................................................
.....#........................#.........#..#......#........#......................#.......#..............#..........#.......#.....
..#....#.........................#.#....................#..#.......#.............#..................#........#..................#.
..........##....#........................................................................#........................................
........#......#................................................................................................#................#
.....#.......#...#.............#....................................#..#........................#...#..............#....#.........
.............#...................................................##...#...........................................................
..............#.............................................#.............#................#.............#..............#.........
..#....#..........#.....#......#......................#................................#...............................#..........
.................................................................................##......#...........................#.....#......
..#....#..........#.......#.........................................#...............#..#............................#........#....
...........#........#.#....................#........#.....................................#..................#....................
.......#............#................#...........#.............#......#.........#...........................#.....................
#.#....#.#...............#....#.....#.......................#...............................#...................##...#............
.................##...#.................................................................#...........................#.............
.....#........................................#.........#...................................................#.....................
....................#.....................#................................................#...##.....................#...........
...............#...............................................................#....#.............................................
.................#................#...#.....................................#......#....................#...............#.#.......
...................#............................................#..#....#..#........#...............................#.........#...
..#........#...............#..................#.....#..................#.....................................#........##...#......
.....#.....#....#.....#................#.#.....................##.............................................................#...
................#............#......#......#.......................................................#....................#........#
........#..............#..#......................................................................##.....##........................
.........#.............................#.........#.......................................#..........................#.##..........
.#...................#........................................................#....#......................................#.......
....#..........#.....#.........................................................................................#..................
.......#.............................#............#.........................#....#....#........#......#.....#.......#.............
..#.......#........................#........................#.....................................................................
........................#...............................#.#.............#................................#..................#....."""
data = [list(d) for d in data.splitlines()]
n = len(data)
m = len(data[0])
def get_start(data):
for i in range(n):
for j in range(m):
if data[i][j] == '^':
return i, j
start_location = get_start(data)
data[start_location[0]][start_location[1]] = '.'
return data, get_start, m, n, start_location
@app.cell
def __(data, m, n, start_location):
# counts num traversed squares starting at location
# and returns None if infinite loop
def get_used_pos(data):
direction = (-1, 0)
location = start_location
# multiply by
# 90 deg rotation
# matrix
def rotate(dir):
x, y = dir
return y, -x
def in_bounds(location):
x, y = location
return x >= 0 and y >= 0\
and x < n and y < m
# 2-vec sum
def move(loc, direc):
return loc[0] + direc[0], loc[1] + direc[1]
seen = set()
while in_bounds(location):
if data[location[0]][location[1]] == "#":
print('bad things')
if (direction, location) in seen:
return None
seen.add((direction, location))
next = move(location, direction)
if in_bounds(next) and data[next[0]][next[1]] == "#":
direction = rotate(direction)
else:
location = next
return set(location for _, location in list(seen))
used_pos = get_used_pos(data)
print(len(used_pos)) # 4515
return get_used_pos, used_pos
@app.cell
def __(data, get_used_pos, start_location):
from copy import deepcopy
count = 0
for (i, j) in get_used_pos(data):
if data[i][j] == "." and (i, j) != start_location:
new_data = deepcopy(data)
new_data[i][j] = "#"
if not get_used_pos(new_data):
count += 1
print(count) # 1309
return count, deepcopy, i, j, new_data
@app.cell
def __():
return
if __name__ == "__main__":
app.run()