+/AoC

advent of code

git clone https://git.julia.blue/+/AoC

Joseph RyanDays 15-186e46de2

master
2.7 KiB99 linesraw
1import re
2from collections import deque
3
4p = re.compile("Valve (..).*=(\d+);.*valves? (.*)")
5
6rates = {}
7adj = {}
8for line in open("input"):
9    cur, rate, paths = p.match(line).groups()
10    rates[cur] = int(rate)
11    adj[cur] = paths.split(", ")
12
13# # dot
14# print("strict graph D {")
15# for v, paths in adj.items():
16#     # if not rates[v]:
17#     #     print(v, '[style="invis"]')
18#     print(v, "--", f' {{{" ".join(paths)}}} ')
19# print("}")
20# import sys; sys.exit()
21
22# is there a better way than BFS from every node?
23# is repeatedly squaring the adjacency matrix cheaper?
24dists = {}
25for v in rates:
26    if not rates[v] and v != "AA":
27        continue
28    visited = {v}
29    q = deque([(n, 1) for n in adj[v]])
30    costs = {}
31    while q:
32        cur, cost = q.popleft()
33        visited.add(cur)
34        if rates[cur]:
35            costs[cur] = cost
36        for n in adj[cur]:
37            if n not in visited:
38                q.append((n, cost + 1))
39    dists[v] = costs
40
41# # dot
42# print("strict graph D {")
43# print('layout="circo"')
44# for v, paths in dists.items():
45#     for p,weight in paths.items():
46#         if weight == 1:
47#             print(v, "--", p)
48#         else:
49#             print(v, "--", p, f'[label="{weight}"]')
50# print("}")
51# import sys; sys.exit()
52
53
54def solve(cur, time, score, opened):
55    # print(cur, time, score, opened)
56    best = score
57    for n, dist in dists[cur].items():
58        if n in opened or dist >= time - 1:
59            continue
60        t = time - dist - 1
61        best = max(best, solve(n, t, score + t * rates[n], opened | {n}))
62    return best
63
64
65print(solve("AA", 30, 0, {"AA"}))
66
67
68def double(me_t, me, el_t, el, time, score, to_open):
69    if not time:
70        return score
71    score += time * (rates[me] * (not me_t) + rates[el] * (not el_t))
72    best = score
73    t = time - 1
74    if not me_t:
75        for v in to_open:
76            if dists[me][v] >= t:
77                continue
78            new = to_open - {v}
79            if not el_t:
80                for n in new:
81                    if dists[el][n] >= t:
82                        continue
83                    tmp = double(dists[me][v], v, dists[el][n], n, t, score, new - {n})
84                    best = max(tmp, best)
85            else:
86                tmp = double(dists[me][v], v, el_t - 1, el, t, score, new)
87                best = max(tmp, best)
88    elif not el_t:
89        for v in to_open:
90            if dists[el][v] >= t:
91                continue
92            new = to_open - {v}
93            tmp = double(me_t - 1, me, dists[el][v], v, t, score, new)
94            best = max(tmp, best)
95    best = max(best, double(me_t - 1, me, el_t - 1, el, t, score, to_open))
96    return best
97
98
99print(double(0, "AA", 0, "AA", 26, 0, set(dists) - {"AA"}))