From 997f1b75995ebac79982e5fdd8bf9cce2e590285 Mon Sep 17 00:00:00 2001
From: Marvin Borner
Date: Sun, 17 Dec 2023 12:56:24 +0100
Subject: i hate graphs
---
2023/17/solve.py | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 77 insertions(+)
create mode 100644 2023/17/solve.py
(limited to '2023/17')
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()
--
cgit v1.2.3