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
|
from collections import deque
from common import day
with open(f"input/{day()}") as fh:
G = [line.rstrip() for line in fh]
for i, s in enumerate(G):
if (j := s.find("S")) != -1:
start = (i, j)
if (j := s.find("E")) != -1:
end = (i, j)
def elevation(s):
if s == "S":
return 0
if s == "E":
return 25
else:
return ord(s) - 97
def get_neighbours(G, pos):
m, n = len(G), len(G[0])
i, j = pos
g = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
g = filter(lambda t: (0 <= t[0] < m) and (0 <= t[1] < n), g)
return filter(lambda p: elevation(G[p[0]][p[1]]) <= elevation(G[i][j]) + 1, g)
def bfs(start, end, G, visited):
q = deque()
q.append(start)
visited[start] = None
while q:
v = q.popleft()
if v == end:
return visited
else:
for w in get_neighbours(G, v):
if w not in visited:
q.append(w)
visited[w] = v
curr_min = 484
for i in range(len(G)):
for j in range(len(G[0])):
if G[i][j] == "a":
visited = {}
start = (i, j)
pomme = bfs(start, end, G, visited)
if pomme is None:
continue
path = [end]
parent = end
while True:
parent = visited[parent]
if parent is None:
break
path.append(parent)
curr_min = min(curr_min, len(path) -1)
print(curr_min)
|
