i hate graphs

1 files changed, 77 insertions, 0 deletions

diff --git a/2023/17/solve.py b/2023/17/solve.py
new file mode 100644
index 0000000..24e4471
--- /dev/null
+++ b/2023/17/solve.py
@@ -0,0 +1,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()