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])