no no recursion

1 files changed, 24 insertions, 33 deletions

diff --git a/2023/12/solve.py b/2023/12/solve.py
index da0efc1..9ae7213 100644
--- a/2023/12/solve.py
+++ b/2023/12/solve.py
@@ -3,38 +3,29 @@ L = [
     for l in open("input").readlines()
 ]
 
+# couldn't get caching to work without recursion
+cache = {}
+
+
+# see previous commit for no recursion
+def arrangements(pat, sol, done):
+    if (pat, sol, done) in cache:
+        return cache[(pat, sol, done)]
+
+    if not pat:
+        return 1 if not sol and not done else 0
 
-# look mum no recursion!! :OOO
-def arrangements(pat, sol):
     arr = 0
-    done = [0]
-    sols = [sol]
-    pats = [pat]
-
-    current = (tuple(sol),pat)
-
-    while pats or sols:
-        p = pats.pop()
-        s = sols.pop()
-        d = done.pop()
-
-        if not p:
-            arr += 1 if not s and not d else 0
-            continue
-
-        for ch in "#." if p[0] == "?" else p[0]:
-            if ch == '#':
-                sols.append(s)
-                pats.append(p[1:])
-                done.append(d + 1)
-            elif not d:
-                sols.append(s)
-                pats.append(p[1:])
-                done.append(0)
-            elif s and s[0] == d:
-                sols.append(s[1:])
-                pats.append(p[1:])
-                done.append(0)
+
+    for ch in "#." if pat[0] == "?" else pat[0]:
+        rst = pat[1:]
+        if ch == "#":
+            arr += arrangements(rst, sol, done + 1)
+        elif not done:
+            arr += arrangements(rst, sol, 0)
+        elif sol and sol[0] == done:
+            arr += arrangements(rst, sol[1:], 0)
+        cache[(pat, sol, done)] = arr
 
     return arr
 
@@ -42,16 +33,16 @@ def arrangements(pat, sol):
 def part1():
     res = 0
     for pat, sol in L:
-        res += arrangements(f".{pat}.", sol)
+        res += arrangements(f".{pat}.", tuple(sol), 0)
     print(res)
 
 
 def part2():
     res = 0
     for pat, sol in L:
-        res += arrangements("?".join([pat] * 5) + ".", sol * 5)
+        res += arrangements("?".join([pat] * 5) + ".", tuple(sol * 5), 0)
     print(res)
 
 
 part1()
-# part2()
+part2()