-
Notifications
You must be signed in to change notification settings - Fork 0
/
day16.py
115 lines (93 loc) · 2.57 KB
/
day16.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
"""
Day 16: The Floor Will Be Lava
"""
import multiprocessing
from enum import Enum
from itertools import chain
SAMPLE_INPUT = r"""
.|<2<\....
|v-v\^....
.v.v.|->>>
.v.v.v^.|.
.v.v.v^...
.v.v.v^..\
.v.v/2\\..
<-2-/vv|..
.|<<<2-|.\
.v//.|.v..
"""
class _Direction(Enum):
U = "up"
L = "left"
D = "down"
R = "right"
_LUT = {
(_Direction.U, "/"): (_Direction.R,),
(_Direction.U, "\\"): (_Direction.L,),
(_Direction.U, "-"): (_Direction.L, _Direction.R),
(_Direction.L, "/"): (_Direction.D,),
(_Direction.L, "\\"): (_Direction.U,),
(_Direction.L, "|"): (_Direction.D, _Direction.U),
(_Direction.D, "/"): (_Direction.L,),
(_Direction.D, "\\"): (_Direction.R,),
(_Direction.D, "-"): (_Direction.L, _Direction.R),
(_Direction.R, "/"): (_Direction.U,),
(_Direction.R, "\\"): (_Direction.D,),
(_Direction.R, "|"): (_Direction.D, _Direction.U),
}
def _move(y, x, d):
match d:
case _Direction.U:
return y - 1, x
case _Direction.L:
return y, x - 1
case _Direction.D:
return y + 1, x
case _Direction.R:
return y, x + 1
def _fill(data, y, x, d):
stack = [(y, x, d)]
visited = set(stack)
while stack:
y1, x1, d1 = stack.pop()
for d2 in _LUT.get((d1, data[y1][x1]), (d1,)):
y2, x2 = _move(y1, x1, d2)
if (
0 <= y2 < len(data)
and 0 <= x2 < len(data[y2])
and (y2, x2, d2) not in visited
):
stack.append((y2, x2, d2))
visited.add((y2, x2, d2))
return len({(y, x) for y, x, _ in visited})
def part1(data):
"""
>>> part1(SAMPLE_INPUT)
46
"""
return _fill(list(filter(None, data.splitlines())), 0, 0, _Direction.R)
_DATA2 = []
def _initializer2(data):
_DATA2[:] = data
def _fill2(args):
y, x, d = args
return _fill(_DATA2, y, x, d)
def part2(data):
"""
>>> part2(SAMPLE_INPUT)
51
"""
data = list(filter(None, data.splitlines()))
with multiprocessing.Pool(initializer=_initializer2, initargs=(data,)) as p:
return max(
p.imap_unordered(
_fill2,
chain(
((y, 0, _Direction.R) for y in range(len(data))),
((0, x, _Direction.D) for x in range(len(data[0]))),
((y, len(data[0]) - 1, _Direction.L) for y in range(len(data))),
((len(data) - 1, x, _Direction.U) for x in range(len(data[-1]))),
),
)
)
parts = (part1, part2)