#!/usr/bin/env python3
import re

lines = (x.strip() for x in open("input.txt"))
lines = (re.search(r"([A-Z]{2}).*?(\d+).*?([A-Z]{2}(?:, [A-Z]{2})*)", line).groups() for line in lines)
nodes = {name: (int(p), [(1, neighbor) for neighbor in neighbors.split(", ")]) for name, p, neighbors in lines}

for name in [*nodes.keys()]:
    (p, edges) = nodes[name]
    if len(edges) != 2 or p != 0:
        continue
    dist = sum(e[0] for e in edges)
    (_, edge1), (_, edge2) = edges
    idx = next(i for i, (_, edge_node) in enumerate(nodes[edge1][1]) if edge_node == name)
    nodes[edge1][1][idx] = (dist, edge2)
    idx = next(i for i, (_, edge_node) in enumerate(nodes[edge2][1]) if edge_node == name)
    nodes[edge2][1][idx] = (dist, edge1)
    del nodes[name]

def solve(pos, opened, minute, released, per_minute, path):
    if minute < 30 and (minute < 10 or released > 100) and (minute < 20 or released > 800):
        pressure, neighbors = nodes[pos]
        # open the value
        if pos not in opened and pressure > 0:
            yield from solve(pos, {pos, *opened}, minute+1, released+per_minute, per_minute+pressure, [*path, ("drain", pos, minute, released)])
        # go to neighbor
        if len(opened) < len(nodes)-1:
            for dist, name in neighbors:
                yield from solve(name, opened, minute+dist, released+per_minute*dist, per_minute, [*path, ("move", pos, "to", name, minute, released)])
        # finish
        yield released + (30-minute+1)*per_minute, [*path, ("finish", pos, minute, released, per_minute)]

mx = 0
for val, path in solve("AA", set(), 1, 0, 0, []):
    if val > mx:
        print(val, path)
        mx = val

# 2253 [('move', 'AA', 'to', 'KQ', 1, 0), ('drain', 'KQ', 3, 0), ('move', 'KQ', 'to', 'RF', 4, 0), ('drain', 'RF', 7, 51), ('move', 'RF', 'to', 'AZ', 8, 68), ('drain', 'AZ', 10, 138), ('move', 'AZ', 'to', 'VI', 11, 173), ('drain', 'VI', 13, 283), ('move', 'VI', 'to', 'IM', 14, 338), ('drain', 'IM', 17, 569), ('move', 'IM', 'to', 'IY', 18, 646), ('drain', 'IY', 20, 838), ('move', 'IY', 'to', 'AQ', 21, 934), ('drain', 'AQ', 23, 1156), ('move', 'AQ', 'to', 'HA', 24, 1267), ('drain', 'HA', 26, 1535), ('move', 'HA', 'to', 'IY', 27, 1669), ('finish', 'IY', 29, 1961, 146)]