diff options
author | Tomasz Kramkowski <tomasz@kramkow.ski> | 2022-12-18 13:13:03 +0000 |
---|---|---|
committer | Tomasz Kramkowski <tomasz@kramkow.ski> | 2022-12-18 13:18:21 +0000 |
commit | 4224d099d7ed66dcb8514c462e3e5db389fe1c4e (patch) | |
tree | 964a77aa29141771dcf1d2b20bdc7f1b998e8d16 | |
parent | cae7abf229c588d64b68dc5a5a4aab6cdc9dffb2 (diff) | |
download | aoc2022-4224d099d7ed66dcb8514c462e3e5db389fe1c4e.tar.gz aoc2022-4224d099d7ed66dcb8514c462e3e5db389fe1c4e.tar.xz aoc2022-4224d099d7ed66dcb8514c462e3e5db389fe1c4e.zip |
16 store path and print it
-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]) |