16 store path and print it

1 files changed, 11 insertions, 5 deletions

diff --git a/16.py b/16.py
index 42f11d0..7a4bcb5 100644
--- a/16.py
+++ b/16.py
@@ -10,14 +10,19 @@ class Node:
     neighbours: list[tuple[str, int]]
 
 ids = {'AA': 0}
+rids = {0: 'AA'}
 nextid = 1
 def intern(n):
     global nextid
     if n in ids: return ids[n]
     ids[n] = nextid
+    rids[nextid] = n
     nextid += 1
     return nextid - 1
 
+def extern(i):
+    return rids[i]
+
 regex = re.compile(r'^Valve (..) has flow rate=([0-9]+); tunnels? leads? to valves? (.*)$')
 inp = {}
 with open_day(16) as f:
@@ -52,15 +57,15 @@ def sum_flow(open_valves):
     return total
 
 recurse_cache = dict()
-def recurse(open_valves=1, current=0, flow=0, time_left=30):
+def recurse(open_valves=1, current=0, flow=0, time_left=30, path=[]):
     key = (current, flow, time_left)
     if key in recurse_cache: return recurse_cache[key]
     cnode = nodes[current]
-    best = flow
+    best = flow, path
     def check(open_valves, current, flow, time_left):
         nonlocal best
-        new = recurse(open_valves, current, flow, time_left)
-        if new > best: best = new
+        new = recurse(open_valves, current, flow, time_left, path + [current])
+        if new[0] > best[0]: best = new
     for neighbour, cost in cnode.neighbours:
         if cost >= time_left: continue
         check(open_valves, neighbour, flow, time_left - cost)
@@ -69,4 +74,5 @@ def recurse(open_valves=1, current=0, flow=0, time_left=30):
     recurse_cache[key] = best
     return best
 
-print(recurse())
+v, p = recurse()
+print(v, [extern(s) for s in p])