from utils import open_day from functools import cache from dataclasses import dataclass from itertools import count, chain from concurrent import futures import re @dataclass class Node: flow: int 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: for line in f: m = regex.match(line) assert(m) valve, flow, neighbours = m.group(1, 2, 3) inp[valve] = (int(flow), neighbours.split(', ')) nodes = {} for valve, (flow, neighbours) in inp.items(): if valve != 'AA' and flow == 0: continue actual_neighbours = [] for n in neighbours: prev = valve for cost in count(1): if n == 'AA' or inp[n][0] != 0: break l, r = inp[n][1] nnext = r if l == prev else l prev = n n = nnext actual_neighbours.append((intern(n), cost)) nodes[intern(valve)] = Node(flow, actual_neighbours) def solve(nodes, open_valves=1, time_left=30): nodemask = 2 ** len(nodes) - 1 recurse_cache = dict() def recurse(open_valves, current, flow, time_left, path): key = (current, flow, time_left) if key in recurse_cache: return recurse_cache[key] best = flow, path if open_valves == nodemask: recurse_cache[key] = best return best cnode = nodes[current] def check(open_valves, current, flow, time_left): nonlocal best 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) if not (open_valves & (1 << current)) and time_left > 0: check(open_valves | 1 << current, current, flow + cnode.flow * (time_left - 1), time_left - 1) recurse_cache[key] = best return best return recurse(open_valves, 0, 0, time_left, []) v, p = solve(nodes) print(v, [extern(s) for s in p]) with futures.ProcessPoolExecutor(max_workers=5) as executor: seen = set() perms = 2 ** len(nodes) def solve2(nodes, a, b): return solve(nodes, a, 26), solve(nodes, b, 26) futs = [] for i in range(perms): a = i | 1 b = (i ^ (perms - 1)) | 1 if a in seen or b in seen: continue seen.add(a) seen.add(b) futs.append(executor.submit(solve2, nodes, a, b)) best = (0, None, None) for future in futures.as_completed(futs): av, bv = future.result() total = av[0] + bv[0] if total > best[0]: best = total, av[1], bv[1] v, p1, p2 = best print(v, [extern(s) for s in p1], [extern(s) for s in p2])