1 files changed, 61 insertions, 0 deletions
diff --git a/problem12.py b/problem12.py
new file mode 100644
index 0000000..7aefcd3
--- /dev/null
+++ b/problem12.py
@@ -0,0 +1,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)