#!/usr/bin/env python3

# import numpy as np
from functools import reduce
from re import findall
from copy import deepcopy
import sys

import traceback

# filename = "in/day16.ref"
filename = "in/day16.pzl"
data = open(filename).read()
lines = [line for line in data.rstrip('\n').split('\n')]


N = dict()

for line in lines:
    a = line.split(' ')
    name = a[1]
    rate = int(a[4].split('=')[1][:-1])
    to = a[9:]
    to = [i.strip(',') for i in to]
    N[name] = {'rate': rate, 'to': to}

# print(N)

res1 = 0
res2 = 0

NZR = set([i for i in N.keys() if N[i]['rate'] > 0])
# print(NZR)

def get_dist(cn, en, steps, S):
    if cn == en:
        return steps
    elif S[cn] < steps:
        return 999

    S[cn] = steps
    m = 999
    for n in N[cn]['to']:
        m = min(m, get_dist(n, en, steps+1,S))
    return m

D = dict()
for i in N.keys():
    D[i] = dict()
    for j in N.keys():
        D[i][j] = get_dist(i, j, 0, {i:999 for i in N.keys()} )
# print(D)


def best2_first(time, cn, rate, gas, opened):
    if time == 29:
        return gas
    elif time == 28:
        return gas + rate

    if len(NZR) == len(opened):
        gas += (30-time-1) * rate
        return gas

    best = list()
    for n in NZR - opened:
        d = get_dist(cn, n, 0, {i:999 for i in N.keys()} )
        val = N[n]['rate'] * (30-time-d)
        # print(n, d, val)
        val = val/(d-0.5)
        best.append((n, d, val))
    best = sorted(best, key=lambda x: x[2], reverse=True)
    # print(best)

    m = 0
    for (n, d, val) in best[:2]:
        op = opened.copy()
        op.add(n)
        mm = best2_first(time + d + 1, n, rate + N[n]['rate'],
                   gas + (d+1)*rate + N[n]['rate'], op)
        m = max(m, mm)
    return m


def dual_best2_first(time, cn1, cn2, cn1_rem, cn2_rem, rate, gas, opened, p1, p2):


    best1 = list()
    if cn1_rem == 0:
        rate += N[cn1]['rate']
        for n1 in NZR - opened:
            # d1 = get_dist(cn1, n1, 0, {i:999 for i in N.keys()} )
            d1 = D[cn1][n1]
            val1 = N[n1]['rate'] * (30-time-d1)
            val1 = val1/(d1-0.5)
            best1.append((n1, d1, val1))
        best1 = sorted(best1, key=lambda x: x[2], reverse=True)

    best2 = list()
    if cn2_rem == 0:
        rate += N[cn2]['rate']
        for n2 in NZR - opened:
            # d2 = get_dist(cn2, n2, 0, {i:999 for i in N.keys()} )
            d2 = D[cn2][n2]
            val2 = N[n2]['rate'] * (30-time-d2)
            val2 = val2
            best2.append((n2, d2, val2))
        best2 = sorted(best2, key=lambda x: x[2], reverse=True)

    gas += rate
    # print(best1, best2, p1, p2)

    if time == 29:
        return gas

    if len(best1) == 1 and len(best2) == 1:
        if best1[0][0] == best2[0][0]:
            if best1[0][1] < best2[0][1]:
                best2 = list()
            else:
                best1 = list()
            # print(best1, best2)
            # sys.exit(1)


    if len(best1) > 0 and len(best2) == 0:
        m = 0
        for (n1, d1, val1) in best1[:4]:
            op = opened.copy()
            op.add(n1)
            mm =  dual_best2_first(time+1, n1, cn2,
                       d1, cn2_rem - 1,
                       rate, gas, op, p1 + [n1], p2)
            m = max(m, mm)

    elif len(best2) > 0 and len(best1) == 0:
        m = 0
        for (n2, d2, val2) in best2[:4]:
            op = opened.copy()
            op.add(n2)
            mm =  dual_best2_first(time+1, cn1, n2,
                       cn1_rem - 1 , d2,
                       rate, gas, op, p1, p2 + [n2])
            m = max(m, mm)

    elif len(best1) > 0 and len(best2) > 0:
        m = 0
        for (n1, d1, val1) in best1[:6]:
            for (n2, d2, val2) in best2[:6]:
                if n1 == n2:
                    continue
                op = opened.copy()
                op.add(n1)
                op.add(n2)
                mm = dual_best2_first(time+1, n1, n2,
                           d1, d2,
                           rate, gas, op, p1 + [n1], p2 + [n2])
                m = max(m, mm)
    else:
        op = opened.copy()
        m = dual_best2_first(time+1, cn1, cn2,
                   cn1_rem - 1, cn2_rem - 1,
                   rate, gas, op, p1, p2)
    return m


res1 = best2_first(0, 'AA', 0, 0, set())
# res1 = dual_best2_first(0, 'AA', 'AA', 0, -1, 0, 0, set())
res2 = dual_best2_first(4, 'AA', 'AA', 0, 0, 0, 0, set(), list(), list())


print('res1:', res1)
print('res2:', res2)