summaryrefslogtreecommitdiff
path: root/24_2022.py
blob: 27c0c73d0a79a74469e186b5abd8a1c76889cece (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
import sys
from collections import deque

infile = sys.argv[1] if len(sys.argv) > 1 else "data/24_2022.txt"
data = open(infile).read().strip()
lines = [x for x in data.split("\n")]

G = lines
R = len(G)
C = len(G[0])
r = 0
c = 0
while G[r][c] == "#":
    c += 1

BAD_CELLS = {}
for t in range((R - 2) * (C - 2) + 1):
    BAD = set()
    for rr in range(R):
        for cc in range(C):
            if G[rr][cc] == ">":
                BAD.add((rr, 1 + ((cc - 1 + t) % (C - 2))))
            elif G[rr][cc] == "v":
                BAD.add((1 + ((rr - 1 + t) % (R - 2)), cc))
            elif G[rr][cc] == "<":
                BAD.add((rr, 1 + ((cc - 1 - t) % (C - 2))))
            elif G[rr][cc] == "^":
                BAD.add((1 + ((rr - 1 - t) % (R - 2)), cc))
                assert 0 <= (rr - 1 - t) % (R - 2) < R - 2
            if cc == c:
                assert G[rr][cc] != "^" and G[rr][cc] != "v"
            if cc == C - 2:
                assert G[rr][cc] != "^" and G[rr][cc] != "v"
    BAD_CELLS[t] = BAD

p1 = False
SEEN = set()
start = (r, c, 0, False, False)
Q = deque([start])
while Q:
    (r, c, t, got_end, got_start) = Q.popleft()
    if not (0 <= r < R and 0 <= c < C and G[r][c] != "#"):
        continue
    if r == R - 1 and got_end and got_start:
        print(t)
        break
    if r == R - 1 and (not p1):
        print(t)
        p1 = True
    if r == R - 1:
        got_end = True
    if r == 0 and got_end:
        got_start = True
    if (r, c, t, got_start, got_end) in SEEN:
        continue
    SEEN.add((r, c, t, got_start, got_end))
    BAD = BAD_CELLS[t + 1]
    if (r, c) not in BAD:
        Q.append((r, c, t + 1, got_end, got_start))
    if (r + 1, c) not in BAD:
        Q.append((r + 1, c, t + 1, got_end, got_start))
    if (r - 1, c) not in BAD:
        Q.append((r - 1, c, t + 1, got_end, got_start))
    if (r, c + 1) not in BAD:
        Q.append((r, c + 1, t + 1, got_end, got_start))
    if (r, c - 1) not in BAD:
        Q.append((r, c - 1, t + 1, got_end, got_start))