diff options
| -rw-r--r-- | 16.py | 16 |
1 files changed, 11 insertions, 5 deletions
@@ -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]) |