i still dont like graphs

3 files changed, 127 insertions, 73 deletions

diff --git a/2023/23/part1.py b/2023/23/part1.py
new file mode 100644
index 0000000..555a5eb
--- /dev/null
+++ b/2023/23/part1.py
@@ -0,0 +1,64 @@
+# adapted from day 16
+
+L = {
+    (y, x): c
+    for y, l in enumerate(open("input").readlines())
+    for x, c in enumerate(l.strip())
+    if c != "#"
+}
+
+
+def oob(y, x, d):
+    return (y, x) not in L
+
+
+def next(y, x, d):
+    if d == 0:
+        return (y - 1, x, d)
+    if d == 1:
+        return (y, x + 1, d)
+    if d == 2:
+        return (y + 1, x, d)
+    if d == 3:
+        return (y, x - 1, d)
+
+
+def neighbours(y, x, d):
+    ch = L[(y, x)]
+
+    if ch == "^":
+        return [next(y, x, 0)]
+    if ch == ">":
+        return [next(y, x, 1)]
+    if ch == "v":
+        return [next(y, x, 2)]
+    if ch == "<":
+        return [next(y, x, 3)]
+
+    return [next(y, x, k) for k in range(4) if abs(d - k) != 2]
+
+
+def dfs(y, x, d):
+    end = list(L.keys())[-1]
+    longest = 0
+    ps = []
+    st = []
+    st.append((y, x, d, set(), 1))
+    while st:
+        y, x, d, v, p = st.pop()
+        v.add((y, x))
+        ns = neighbours(y, x, d)
+        for n in ns:
+            if n[:2] not in v and not oob(*n):
+                np = p + 1
+                st.append((*n, set(v), np))
+
+                if n[:2] == end:  # reached end
+                    ps.append(np)
+
+    return ps
+
+
+ps = dfs(0, 1, 2)
+mx = max(p for p in ps)
+print(mx - 1)
diff --git a/2023/23/part2.py b/2023/23/part2.py
new file mode 100644
index 0000000..54e0bbe
--- /dev/null
+++ b/2023/23/part2.py
@@ -0,0 +1,63 @@
+L = [l.strip() for y, l in enumerate(open("input").readlines())]
+
+G = {}
+for y in range(1, len(L) - 1):
+    for x in range(1, len(L[0]) - 1):
+        if L[y][x] == "#":
+            continue
+        if L[y - 1][x] != "#":
+            if (y - 1, x) not in G:
+                G[(y - 1, x)] = set()
+            if (y, x) not in G:
+                G[(y, x)] = set()
+            G[(y - 1, x)].add((y, x, 1))
+            G[(y, x)].add((y - 1, x, 1))
+        if L[y][x - 1] != "#":
+            if (y, x - 1) not in G:
+                G[(y, x - 1)] = set()
+            if (y, x) not in G:
+                G[(y, x)] = set()
+            G[(y, x - 1)].add((y, x, 1))
+            G[(y, x)].add((y, x - 1, 1))
+
+# compress graph
+done = False
+while not done:
+    done = True
+    for (y, x), ns in G.items():
+        if len(ns) != 2:
+            continue
+        n1, n2 = ns
+        G[n1[:2]].add((n2[0], n2[1], n1[2] + n2[2]))
+        G[n2[:2]].add((n1[0], n1[1], n1[2] + n2[2]))
+        G[n1[:2]].remove((y, x, n1[2]))
+        G[n2[:2]].remove((y, x, n2[2]))
+        del G[(y, x)]
+
+        done = False
+        break
+
+
+def dfs(y, x):
+    end = list(G.keys())[-1]
+    ps = []
+    st = []
+    st.append((y, x, 1, set(), 1))
+    while st:
+        y, x, l, v, p = st.pop()
+        v.add((y, x))
+        ns = G[(y, x)]
+        for n in ns:
+            if n[:2] in v:
+                continue
+
+            np = p + n[2]
+            st.append((*n, set(v), np))
+
+            if n[:2] == end[:2]:  # reached end
+                ps.append(np)
+
+    print(max(p for p in ps))
+
+
+dfs(0, 1)
diff --git a/2023/23/solve.py b/2023/23/solve.py
deleted file mode 100644
index 185328e..0000000
--- a/2023/23/solve.py
+++ /dev/null
@@ -1,73 +0,0 @@
-import sys
-
-sys.setrecursionlimit(100000)
-
-L = {
-    (y, x): c
-    for y, l in enumerate(open("input").readlines())
-    for x, c in enumerate(l.strip())
-    if c != "#"
-}
-
-
-def oob(y, x, d):
-    return (y, x) not in L
-
-
-def next(y, x, d):
-    if d == 0:
-        return (y - 1, x, d)
-    if d == 1:
-        return (y, x + 1, d)
-    if d == 2:
-        return (y + 1, x, d)
-    if d == 3:
-        return (y, x - 1, d)
-
-
-def neighbours(y, x, d):
-    ch = L[(y, x)]
-
-    if ch == "^":
-        return [next(y, x, 0)]
-    if ch == ">":
-        return [next(y, x, 1)]
-    if ch == "v":
-        return [next(y, x, 2)]
-    if ch == "<":
-        return [next(y, x, 3)]
-
-    return [next(y, x, 0), next(y, x, 1), next(y, x, 2), next(y, x, 3)]
-
-
-def dfs(y, x, d, v, p):
-    v.add((y, x))
-
-    ps = []
-    ns = neighbours(y, x, d)
-    for n in ns:
-        if (n[0], n[1]) not in v and not oob(*n):
-            np = p + [n]
-            ps.append(tuple(np))
-            ps.extend(dfs(*n, set(v), np))
-
-    return ps
-
-
-def solve1():
-    ps = dfs(0, 1, 2, set(), [(0, 1)])
-    mx = max(len(p) for p in ps)
-    print(mx - 1)
-
-
-# def solve2():
-#     res = 0
-#     for x in range(W):
-#         res = max(res, visited(0, x, 2), visited(H, x, 0))
-#     for y in range(H):
-#         res = max(res, visited(y, 0, 1), visited(y, W, 3))
-#     print(res)
-
-
-solve1()
-# solve2()