commit 3d71e3cbbef71fe71d248c97df29f47d953a4dda (patch)
parent 636dd73a95666d2dd37cb94905aa895c7bf00113
Author: Alex Karle <alex@alexkarle.com>
Date: Sun, 22 Dec 2024 14:24:43 +0100
2024: Add day 16 pt 1 first draft
It runs, but it's not really optimal maybe?
Diffstat:
| A | 2024/16/1.py | | | 62 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 62 insertions(+), 0 deletions(-)
diff --git a/2024/16/1.py b/2024/16/1.py
@@ -0,0 +1,62 @@
+#!/usr/bin/env python3
+import sys
+import heapq
+
+def parse():
+ G = []
+ for l in sys.stdin:
+ G.append([c for c in l.strip()])
+ # all examples the same w S at bottom left facing east
+ return G, (len(G) - 2, 1), '>'
+
+def pprint(G):
+ for i in range(len(G)):
+ for j in range(len(G[0])):
+ print(G[i][j], end="")
+ print("")
+
+def peek(G, pos, dir):
+ i, j = pos
+ if dir == "^":
+ return G[i-1][j], (i-1, j)
+ elif dir == ">":
+ return G[i][j+1], (i, j+1)
+ elif dir == "v":
+ return G[i+1][j], (i+1, j)
+ elif dir == "<":
+ return G[i][j-1], (i, j-1)
+ else:
+ raise Exception(f"Bad dir: {dir}")
+
+def turns(dir):
+ if dir == "^" or dir == "v":
+ return ["<", ">"]
+ elif dir == ">" or dir == "<":
+ return ["^", "v"]
+ else:
+ raise Exception(f"Bad dir: {dir}")
+
+def walk(G, pos, dir):
+ h = []
+ seen = set()
+ heapq.heappush(h, (0, pos, dir, [pos]))
+ while h:
+ (cost, pos, dir, pth) = heapq.heappop(h)
+ if (pos, dir) in seen:
+ continue
+ seen.add((pos, dir))
+ (next, npos) = peek(G, pos, dir)
+ if next == "E":
+ for p in pth:
+ G[p[0]][p[1]] = '*'
+ pprint(G)
+ return cost + 1
+ if next != '#':
+ heapq.heappush(h, (cost + 1, npos, dir, pth + [npos]))
+ for ndir in turns(dir):
+ heapq.heappush(h, (cost + 1000, pos, ndir, pth))
+ raise Exception("No path found")
+
+if __name__ == '__main__':
+ G, pos, dir = parse()
+ print(walk(G, pos , dir))
