1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
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, [0])
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])
|
