commit c1bae5098163c6feddcf241161baadb14cdd06fb (patch)
parent 3d71e3cbbef71fe71d248c97df29f47d953a4dda
Author: Alex Karle <alex@alexkarle.com>
Date: Sun, 22 Dec 2024 18:48:14 +0100
2024: Add day 16 part 2
Diffstat:
| D | 2024/16/1.py | | | 62 | -------------------------------------------------------------- |
| A | 2024/16/sol.py | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 67 insertions(+), 62 deletions(-)
diff --git a/2024/16/1.py b/2024/16/1.py
@@ -1,62 +0,0 @@
-#!/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))
diff --git a/2024/16/sol.py b/2024/16/sol.py
@@ -0,0 +1,67 @@
+#!/usr/bin/env python3
+import sys
+import heapq
+from collections import defaultdict
+
+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 step(pos, dir):
+ i, j = pos
+ if dir == "^":
+ return (i-1, j)
+ elif dir == ">":
+ return (i, j+1)
+ elif dir == "v":
+ return (i+1, j)
+ elif dir == "<":
+ return (i, j-1)
+ else:
+ raise Exception(f"Bad dir: {dir}")
+
+
+# Return [(cost, newpos, newdir)]
+def neighs(G, pos, dir):
+ if dir == "^" or dir == "v":
+ return [(1, step(pos, dir), dir), (1001, step(pos, ">"), ">"), (1001, step(pos, "<"), "<")]
+ elif dir == ">" or dir == "<":
+ return [(1, step(pos, dir), dir), (1001, step(pos, "^"), "^"), (1001, step(pos, "v"), "v")]
+ else:
+ raise Exception(f"Bad dir: {dir}")
+
+def walk(G, pos, dir):
+ h = []
+ best = 100000
+ dist = defaultdict(lambda: 100000)
+ tiles = set()
+ heapq.heappush(h, (0, pos, dir, [pos]))
+ while h:
+ (cost, pos, dir, pth) = heapq.heappop(h)
+ #print(cost, pos, dir, pth)
+ if cost > dist[(pos, dir)]:
+ continue
+ dist[(pos, dir)] = cost
+ if G[pos[0]][pos[1]] == "E" and cost <= best:
+ best = cost
+ for p in pth:
+ tiles.add(p)
+ for neigh in neighs(G, pos, dir):
+ (ecost, npos, ndir) = neigh
+ if G[npos[0]][npos[1]] == '#':
+ continue
+ heapq.heappush(h, (cost + ecost, npos, ndir, pth + [npos]))
+ return best, len(tiles)
+
+if __name__ == '__main__':
+ G, pos, dir = parse()
+ print(walk(G, pos , dir))
