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
|
from queue import PriorityQueue
L = {
(y, x): int(c)
for y, l in enumerate(open("input").readlines())
for x, c in enumerate(l.strip())
}
W = max(x for (_, x) in L.keys())
H = max(y for (y, _) in L.keys())
def oob(y, x, d, c):
return x > W or x < 0 or y > H or y < 0
def neighbours(y, x, d, c):
ns = []
if d != 2:
ns.append((y - 1, x, 0, c + 1 if d == 0 else 0))
if d != 3:
ns.append((y, x + 1, 1, c + 1 if d == 1 else 0))
if d != 0:
ns.append((y + 1, x, 2, c + 1 if d == 2 else 0))
if d != 1:
ns.append((y, x - 1, 3, c + 1 if d == 3 else 0))
return ns
def part1():
q = PriorityQueue()
q.put((0, (0, 0, 1, 0)))
v = set()
while q:
p, c = q.get()
if c[:2] == (H, W):
break
if c in v:
continue
v.add(c)
for n in neighbours(*c):
if not oob(*n) and c[3] < 3:
q.put((p + L[n[:2]], n))
print(p)
def part2():
q = PriorityQueue()
q.put((0, (0, 0, 1, 0)))
v = set()
while q:
p, c = q.get()
if c[:2] == (H, W) and c[3] >= 3:
print(p)
break
if c in v:
continue
v.add(c)
for n in neighbours(*c):
if n[2] != c[2] and c[3] < 3:
continue
if not oob(*n) and n[3] < 10:
q.put((p + L[n[:2]], n))
part1()
part2()
|
