This repository has been archived by the owner on Mar 28, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
21.js
239 lines (219 loc) · 19.7 KB
/
21.js
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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
const input = `...................................................................................................................................
.##.....#.........#........#...#......#.#.#..#..#......#....#..............#..............#........#...#.#....#...#....##.#.....#..
...........#..#.....##.#.##...........#.##.......#.....................##....#.#..#....#.#......##.....#...#....#....#.....#.......
.....#.#..................##.....#.#...#............#.#...........................#..............#......#.......#.##...............
.........#...#.........#.##......#.#...#..#.#.#......#.#..................##.#...#...........#..............#....#....#....#.......
..##.......#.#...#.#.#......#.#..##.##.#.........#..#.............#..........#...##.###................#.#.........................
..............##......#...........#.#....#.#......#...##.......#.............#........#....#...#..#.#.........#.....#...#...#..#...
......##..#.#.###..#.......#............#...#.....#.#..........................#.##....##....#.#....#.#.....#.#....#.....#.........
.........#...#.#..#.....##.....#.#....#........#..#..........#..#.................#...................#.....#....#..........#......
.##........................#.........#....#....................#................#....#.#..#..##.#..#......#..#..............#......
..#.#.......##..#..#.................#..............................#.#.........##...............#..#.#.....#.....##.........##....
.......#.#..##.###....#.##...#.#..#.#.##........##...............................#......#............#.....#...#.##....#.#.....#...
.................#......#............#..#....................#....#.....##.......#.......#..#............#.#....#.##.#.............
..#...#..##.....#.....#....#...#.#..#..........#..........#..##.#..##..#...........#.......#......##....#.#........#........#..###.
.#......#................#.#.#.........##.....#...........##....#...#.....#...............###..#....##......#..#....##.......#.#...
..#.....#........#....#....#.###..#.#........#....................#.....##..........#.............#.#.....#...........#............
.#.##...............#.....#....#....#.......#..................#...#.......##.........#.......................#...#.........#...#..
.#.........#.........###.....#.##......#...................#....#.....##.###................#..............#.......#..#.#..........
.........#...#......#..###.....##........#...........#.......#....#.....##.................##.....#.#....#....##.#..#....#.........
.#.................#....#......#...............................#.....#.........................#...#........#....#.................
...#........#...............##.#..#..............#.....#...#.#....#.....#..................#....#.....####...#........##...........
.....................#...#...#.......#.................#.#...##.#....#.....#...##.................#....###.#....#...#........#.....
..........#.........#.........#..#....................##.......#..#......#.................#...#..............#.#..#....#..........
.#.#..##.........#.....##..#...#................##....#......#.........#..#.#.#...............#.......#.....................#.#....
....#.#...#.#........#.......#.#...#...............##..............#............##.................#....#....#.##.....#.#........#.
..#.....#......#........#........#...........#....................#..#........#.....................#.#.#.................##.....#.
...#..##........#.....#...........#.........#..#.#............##.....#.#..............#........#........#..#.....#.................
......#......#....#....#....#........................#......#..##...##....#........##...........................#...#...#...#......
.#........#..#...#...#...##...##...........###.......#.........#....#.....#.#..#.........#........#...#...#.#........#.............
...#...............#...#................#....#.##..........#.......#...#..#......#....##.......................#.#..##.......#...#.
.#....#.....#.......###..##...............##....#..#..............###..#..#.....#....#.....................#..#....###.#...##....#.
...#........#...#.......................#..........#.....###..###.............##.........#...........#.#..#..#..##.......#....#....
..#....##......#........###.................#...............#...........#...........................................#.........#....
......##....#.#.#.....................#............#...###.........#....#......#....###..................#.....#...................
...#.................#.#..............#.#.#.........#........#.....##......#..#......#.........#..............#####............###.
.................#...#......................#...#............#.....##.#....#..#....#...#.##.................##.................#...
........#.....................................#.#.#.........#..#...#...............#.......#.....#............#...........#........
.......#.#....#........#...............###............#........#........#....#..#..........................#.....#..#...#....#.....
..#...#...........#.............#...........###.....#..#...........##...#...........#...#.......#..........#......##..###......#...
.#..........#.#...##............#.##...#.......#.#.............#...#.#...##.............#....#....#.........#.#...#...#.......#.##.
............#.#...................#......#....#..##....#.#.#.#.#......#..........#......#.#..............................#.....#...
..#..#.........#...##........#.#.........#..#...#...........#.............#.#.....#.....#....##.....##.............................
.....#........#.................#.#.......##..#........#.......#......##........#......#......##...............##...........#...#..
.#..........................#..##..#.....#...#...#........#...##..#.....##.##........#..#........#...#...........#.................
..#.#......#...##.........#......#..........#.............#...#..........#.#.......#........#...#..#................##.............
..#.....#.#..#............#.......................#.#...#...#.......#.....#.....#..#.......##...#..................#.............#.
.......#.##..#.............#...##...#..#..##............#..#.##......#......#..#..#.#.#......#......#..#...........#.........#.....
..........##...................#................##....#...........#.....................#.....#................................#...
...#.#.......#...........#...#....#..#.#...#.....#..#........#......#......#.#.#.........#.......#....###.#...........#............
.#..#.......#..............#.....#..#........#...#......#......#........#..........................##........#.....................
......#.#.#............#.....#..........#...#...#....#...#.##..#...#...#......#........#.#.#.#.....##.......##...................#.
.......#...............#...#...................#.....#..........#.....##.................#.#.........##..###.......................
.#.#..............##...#...#.....#.........#...........#.....###....#...........#.#.......##..##.......#.#.........................
...#..#.........#..#...#..............##.#......#..........#.......#...#....#..#.......................#.#.......#.............#...
...#...#.............#......#.....#............#..##............#...#.#.#.##.......#....##........#........##..#..#.........#......
................#..#.............#......##.#.##...#...#....#...........#...#.....#.....#..#.#.#....##...#...................##..#..
.......................#..#.......##....#..#.#........#........#..#..###....#..........#..#..#........##..#...................#....
..#...........#......#.####..........#.#.......#........#.............#........#...#...#......#....#...#...#.......................
..#........#.................#.##.#...#....#.....#....#...#........#.....#.##.........#.#........#......#.##.#....#.##.#........#..
................#.#..............#........#.###.#.#..................................#.##.....#.#.##.#...#...#.#...##..............
...............#.....#...........###....#.#...#....##......#..#.....#....................#..#..........#....#.........#............
..............##...#....#.#.##...#....#........###.....#.#..#..#..........#.........##...#......#.#...#...#.#...#..#...#..#........
..........#.......#.............#.................#...............#.....##......##...........#..##..#......#......#..#.#...........
........#...#........#..............#...............#.#..#..#.................###.......#......#....#......#.#..#..#...............
........###...#...#...#.#......#....#...#...........#.....#................#...........###..#.............#....#...................
.................................................................S.................................................................
...........#...#..#.#.........#...##....................##.#.###.........#...........##...............#....................#.......
......#.................#..........#.........#..##....#......##.......#.#.............#...............#.###......#.#......#........
................#.##.#......##........#....#.....#.......................#......#.......#................#####........#.#..........
.........#..#...#.....#...#....#..........#.#......#..#....#..#.....#.#...#...............#...###.#.#.#.#..#..#..#.#..#...#........
............#...###................................#..#.#...#......#..............#........#......#.#.....#.#.......#..............
..#.......#.......#.#.#.#........#....#.......#..#.....#.....#.....#...........#.......#..#.......#.......#....###......#..........
.....................................#...#..........#.....#....#..........#............#........#......####...........#............
.##...........#....#...#......#....##....##.#......#......#.......#..##.....#.....#.........#....#..#............#....#............
...................##..............##....###......#.#....##........#..........#..#.##......#.......#.........#.....................
..##..#.......#..........................#.#..#.........#.......#.......#.....#..#......#...........#...........#.###........#.....
..................#.#....###....####.#.......##.....#....#.....................................#...#...#......#....................
.###....#..............#.......#.##.##....#...###....#.##.#....##...............#.#..........#...........#.##.##...................
.....#.#.............#............#......##..#.........#.#..#...#.................#....#...#.......#...#..................#........
....#..#..........#.#.......##...#.....#...##.#....#.....#..#.......#..........#......................#..#................#.##.#...
.#...#...............#...#.....#...#..#...#....#.#...#.#...#.......#...#.......#......................###..#.................##....
......#...#.........#.#......#...##...##.....#...#...#...##...#......#...#....#####..........#...............#...........#.#...#.#.
.#..........##...........................#...#....#..#............#.........#......#....#........#.....#.....#.................#.#.
..##..#......#................#.......#.....#.......#.##....##..#......#.....#.............#....#..#...##.......................##.
......#........#.........#.#....##.........##..............#..#.....#.#...#.......#........#...........................#.......#.#.
.......#......##.............#...##.......#...#..#.........##..##.....##.#.....#.......#..................#........#.#....#.....#..
..#.......#.................#........#....#....##.##..........#.#......##..#...#......#...#........###.#...............#......##...
..........#.#..................###.#..............#...#.....#.#...#........#.#....#..#.......#..#.#.#........................#.....
..#..........#.#............#.#.#......##...............#.#..#..#.###.....#..#..##.##............##.....................#...#.#....
...#.#..##.......#..........##.#.......#..#..........#.......#..#..........#..#.#...#.......#............................##....#...
.#..#.............#.##..........#...#...#.##...##.......#...#........##.#..#............##..##...................#......#.....#....
.......................................##....#.........#.....................................#...#..........#.#....#........#......
....#......#.#...................#.#.......#.#.......#..#.#.#.....#...........#.#.##.......##.....#...........##........##....#.##.
.........#.........##............#......#.##.##....##.......#..............#.##........##.#......#........#......###..........##.#.
......#............#.#.......................#...#......#.#.....#...#.........#.#.#....#..................#.......##.......#.......
.....#..#....#..#.........#.......#.#....#....#.#..........#......#..#.....#.......#.#.......#..............#....#.................
....#.................#..#.........#....#......#.#....#.........#.........#..#...#....#.##......................#........#.#..#.#..
.#..#..............#.......#........#.....#......#..................#.#...#...#.#...#......#..........##.#.#.#.............#.......
.#............#.#....##..................##..#.....#.....#................##..............##.#..................#.##..#....#..#.#..
......#.....##...##...##...#..............#.......##..#......##...#.....#....#.#.#........#...........#...#....#.........#.........
...#....#..#.....#.......#.................................#..........#....#....#.......#...........#.#..#..#...........##...#..#..
............#...........#..#..............#...#.........#..............#..........#.#..#..........##......##..#....................
....#.#....#..#.......#......#..........................#.#.#.#.#.................#....................#.....###.......#......#....
.....#.....#..#............#.#..#......................#....#.......#..#....#..........................#.#.#......#.##.#...........
.......#..............#........#............#....#......#.#..#..............#.#.##.#.....................#....#............#..#.##.
...#........................#....#..................#...#.#.###...#...#......#..##...##.......#.#.....#..........#..###..........#.
....##....#....#.......#..##........#..........#.....#.#....#..#...#...........................#..#.......#.....#......#...#.......
.....#...##.#...#...##...#.....................#.#....#..#.....#................#................#..#.#......................#.....
........#...#.....##.##..#........#...##.........#..#.#.............##........#............#..###.....#.....#............#.........
.#........##.....##....#...#...........#........................#.##.##.........##...............#..#...#...........#.......##.#...
.......#................#.#........................##......#........#......#.....#............#........#.....#.#...#...#.#.....#...
.......#.....#.#....#....#....###.....#...........#.....#.....#...##....##.....#..........#..#.#......#..###.#.........#...#...##..
...#.#........#....#..#.....#..#......#.#.##..........##........#...#.......................#..#......#......#.....#..........#....
..###.....#.........##.....#....#.##.....#..........#....##.........#..#...............#.............#.##.....#......#..#..........
...#..##...................##.#.....#.###....#................#............#.........#...........................#.......#.#.......
.#....#.........................#...#.........#..........#..#.........#...#...........#.................#.............#.....##..##.
...............#.....#...#....#...#......#................#.......##...............#..#.............#........#....#.##.#...........
....#............#...#............#....#......#.........###....#........#.........#.....#.#.##....#...#...............##..##.......
.....#..#..................#....#...........#.#.#.......................#.........#.......#####..##....#.............#...#......##.
.....#..#..#..................###......#....#....##...................#.#.......#..##....#.....#..........#.#....##.#.#..#......#..
.......##.........###..................#..........#................###..............##.##.#.#.#....#................#...#..#.#..#..
.#..#.........###.......#.....#......#.......#.................#..............##...#........#....#..#.....##.......#.....#.........
..........#.....##.........#.........#.###.....#.#..............#....#...................................##...............#......#.
.#...##..#...#.....##....#.#.#..........##.#................................#......##......#.........#..##..##.........##........#.
......#.#.....#...........##.#..#.....#.......#........#....................#........##.#...#.....##...#.###..#..#....#........#...
....##...........##.....#...............##.#...#..#........................#......#........#.##.......#....#..#...#.........#..##..
....####.#....#.#.......##...###....#...##..#.#...................................#.......##....##.#.#.................#..##....##.
........#.........#....#.......#.......#.#...........#..................#..#..#...##...#.....##....##.#..#.##.........#............
.#............#..#.#.....#......#.##.#.#.#..#....##..#..............................#....#........#.....#..........#...#......#....
............#.....#.#........##.#.....#......#.#.........#...............#.....#.#.#.##......#....#.#.....#.....................#..
...................................................................................................................................`;
const example1 = `...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........`;
const dirs = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0]
];
(async function main () {
for (let [name, rawData] of [['example1', example1], ['input', input]]) {
const garden = rawData.split('\n').map(line => line.split(''))
const n = garden.length
const half = n / 2 >> 0
const startY = half
const startX = half
for (let part2 of [false, true]) {
let ans = 0
let steps = part2
? name == 'input' ? 26501365 : 5000
: name == 'input' ? 64 : 6
console.log('---------')
console.log('| |')
console.log('| START |')
console.log('| |')
console.log('---------')
console.time(`start ${name} ${part2 ? 'part 2' : 'part 1'}`)
function fill (y, x, d) {
const plots = [[y, x, d]]
const ans = new Set()
const seen = new Set()
while (plots.length) {
let [y, x, d] = plots.shift()
if (d%2 == 0) ans.add(`${y},${x}`)
if (d == 0) continue
for (let [dy, dx] of dirs) {
const ny = y + dy
const nx = x + dx
if (
ny < 0 || ny >= n ||
nx < 0 || nx >= n ||
garden[ny][nx] == '#' ||
seen.has(`${ny},${nx}`)
) continue
seen.add(`${ny},${nx}`)
plots.push([ny, nx, d - 1])
}
}
return ans.size
}
if (part2) {
const width = (steps / n >> 0) - 1
const odd_count = ((width / 2 >> 0) * 2 + 1) ** 2
const even_count = (((width + 1) / 2 >> 0) * 2) ** 2
const fill_odd = fill(startY, startX, 2*n + 1)
const fill_even = fill(startY, startX, 2*n)
const corner_t = fill(n - 1, startX, n - 1)
const corner_b = fill(0, startX, n - 1)
const corner_l = fill(startY, 0, n - 1)
const corner_r = fill(startY, n - 1, n - 1)
const small_tl = fill(0, 0, half - 1)
const small_tr = fill(0, n - 1, half - 1)
const small_bl = fill(n - 1, 0, half - 1)
const small_br = fill(n - 1, n - 1, half - 1)
const large_tl = fill(0, 0, n + half - 1)
const large_tr = fill(0, n - 1, n + half - 1)
const large_bl = fill(n - 1, 0, n + half - 1)
const large_br = fill(n - 1, n - 1, n + half - 1)
ans = fill_odd * odd_count + fill_even * even_count +
corner_t + corner_b + corner_l + corner_r +
(width + 1) * (small_tl + small_tr + small_bl + small_br) +
width * (large_tl + large_tr + large_bl + large_br)
} else {
ans = fill(startY, startX, steps)
}
console.log(ans);
console.timeEnd(`start ${name} ${part2 ? 'part 2' : 'part 1'}`)
}
}
})()