summaryrefslogtreecommitdiff
path: root/12_2022.py
blob: 92da9a24c1da09479bcf860f2d99005c665e4963 (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
import sys
from collections import deque

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

g = []
for l in lines:
    g.append(l)
r = len(g)
c = len(g[0])
e = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
    for j in range(c):
        if g[i][j] == "S":
            e[i][j] = 1
        elif g[i][j] == "E":
            e[i][j] = 26
        else:
            e[i][j] = ord(g[i][j]) - ord("a") + 1


def bfs(part):
    q = deque()
    for i in range(r):
        for j in range(c):
            if (part == 1 and g[i][j] == "S") or (part == 2 and e[i][j] == 1):
                q.append(((i, j), 0))
    s = set()
    while q:
        (i, j), k = q.popleft()
        if (i, j) in s:
            continue
        s.add((i, j))
        if g[i][j] == "E":
            return k
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            rr = i + dr
            cc = j + dc
            if 0 <= rr < r and 0 <= cc < c and e[rr][cc] <= 1 + e[i][j]:
                q.append(((rr, cc), k + 1))


print(bfs(1))
print(bfs(2))