summaryrefslogtreecommitdiff
path: root/16_2022.py
blob: 68deffee25ef74a6583323af0b71598bfbe88455 (plain)
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
import re
from collections import defaultdict

graph = {}
rates = {}
for line in open("data/16_2022.txt").read().strip().split("\n"):
    front, back = re.split(r"; tunnels? leads? to valves? ", line)
    x = front.split(" ")[1]
    rates[x] = int(front.split("=")[-1])
    graph[x] = back.split(", ")

node_id = defaultdict(lambda: len(node_id))
[node_id[u] for u in rates if rates[u]]
all_mask = (1 << len(node_id)) - 1
cache = defaultdict(lambda: [[-1 for mask in range(all_mask + 1)] for t in range(31)])


def dp(u, t, mask):
    if t == 0:
        return 0
    if cache[u][t][mask] == -1:
        best = max(dp(v, t - 1, mask) for v in graph[u])
        bit = 1 << node_id[u]
        if bit & mask:
            best = max(best, dp(u, t - 1, mask - bit) + rates[u] * (t - 1))
        cache[u][t][mask] = best
    return cache[u][t][mask]


print(dp("AA", 30, all_mask))
print(
    max(
        dp("AA", 26, all_mask - mask) + dp("AA", 26, mask)
        for mask in range(all_mask + 1)
    )
)