day 23 brute

1 files changed, 91 insertions, 0 deletions

diff --git a/23.py b/23.py
new file mode 100644
index 0000000..e3f2ead
--- /dev/null
+++ b/23.py
@@ -0,0 +1,91 @@
+from collections import defaultdict
+from sys import stdin
+
+inp = [line.rstrip("\n") for line in stdin]
+
+start = (inp[0].index("."), 0)
+end = (inp[-1].index("."), len(inp) - 1)
+
+
+def neighbours(
+    maze: list[str], prev: tuple[int, int], position: tuple[int, int]
+) -> list[tuple[int, int]]:
+    ret = []
+    for dx in (-1, 1):
+        nx = position[0] + dx
+        if nx < 0 or nx >= len(maze[0]):
+            continue
+        if (nx, position[1]) == prev:
+            continue
+        c = maze[position[1]][nx]
+        if c == "#":
+            continue
+        if dx < 0 and c == ">" or dx > 0 and c == "<":
+            continue
+        ret.append((nx, position[1]))
+    for dy in (-1, 1):
+        ny = position[1] + dy
+        if ny < 0 or ny >= len(maze):
+            continue
+        if (position[0], ny) == prev:
+            continue
+        c = maze[ny][position[0]]
+        if c == "#":
+            continue
+        if dy < 0 and c == "v" or dy > 0 and c == "^":
+            continue
+        ret.append((position[0], ny))
+    return ret
+
+
+to_explore: list[tuple[tuple[int, int], tuple[int, int]]] = [(start, (start[0], 1))]
+edges: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict(set)
+while to_explore:
+    root, pos = to_explore.pop()
+    prev = root
+    dist = 1
+    while True:
+        neighs = neighbours(inp, prev, pos)
+        if len(neighs) != 1 or inp[neighs[0][1]][neighs[0][0]] in "^>v<":
+            edges[root].add((dist, pos))
+            for n in neighs:
+                to_explore.append((pos, n))
+            break
+        dist += 1
+        prev = pos
+        pos = neighs[0]
+
+
+def longest(
+    start: tuple[int, int],
+    goal: tuple[int, int],
+    seen: frozenset[tuple[int, int]],
+    edges: dict[tuple[int, int], set[tuple[int, tuple[int, int]]]],
+) -> int | None:
+    if start == goal:
+        return 0
+    maximum = 0
+    new_seen = seen | {start}
+    for dist, n in edges[start]:
+        if n in seen:
+            continue
+        d = longest(n, goal, new_seen, edges)
+        if d is None:
+            continue
+        if d + dist > maximum:
+            maximum = d + dist
+    return maximum if maximum > 0 else None
+
+
+print(longest(start, end, frozenset(), edges))
+
+fullgraph: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict(
+    set, ((k, v.copy()) for k, v in edges.items())
+)
+
+for k, v in edges.items():
+    for dist, pos in v:
+        fullgraph[pos].add((dist, k))
+
+
+print(longest(start, end, frozenset(), fullgraph))