+/AoC
advent of code
git clone https://git.julia.blue/+/AoC
6e46de2
master
1import re 2from collections import deque 3 4p = re .compile ("Valve (..).*=(\d+);.*valves? (.*)" ) 5 6rates = {} 7adj = {} 8for line in open ("input" ): 9cur ,rate ,paths = p .match (line ).groups () 10rates [cur ]= int (rate ) 11adj [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 : 26if not rates [v ]and v != "AA" : 27continue 28visited = {v } 29q = deque ([(n ,1 )for n in adj [v ]]) 30costs = {} 31while q : 32cur ,cost = q .popleft () 33visited .add (cur ) 34if rates [cur ]: 35costs [cur ]= cost 36for n in adj [cur ]: 37if n not in visited : 38q .append ((n ,cost + 1 )) 39dists [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) 56best = score 57for n ,dist in dists [cur ].items (): 58if n in opened or dist >= time - 1 : 59continue 60t = time - dist - 1 61best = max (best ,solve (n ,t ,score + t * rates [n ],opened | {n })) 62return best 63 64 65solve ("AA" ,30 ,0 , {"AA" })) 66 67 68def double (me_t ,me ,el_t ,el ,time ,score ,to_open ): 69if not time : 70return score 71score += time * (rates [me ]* (not me_t )+ rates [el ]* (not el_t )) 72best = score 73t = time - 1 74if not me_t : 75for v in to_open : 76if dists [me ][v ]>= t : 77continue 78new = to_open - {v } 79if not el_t : 80for n in new : 81if dists [el ][n ]>= t : 82continue 83tmp = double (dists [me ][v ],v ,dists [el ][n ],n ,t ,score ,new - {n }) 84best = max (tmp ,best ) 85else : 86tmp = double (dists [me ][v ],v ,el_t - 1 ,el ,t ,score ,new ) 87best = max (tmp ,best ) 88elif not el_t : 89for v in to_open : 90if dists [el ][v ]>= t : 91continue 92new = to_open - {v } 93tmp = double (me_t - 1 ,me ,dists [el ][v ],v ,t ,score ,new ) 94best = max (tmp ,best ) 95best = max (best ,double (me_t - 1 ,me ,el_t - 1 ,el ,t ,score ,to_open )) 96return best 97 98 99double (0 ,"AA" ,0 ,"AA" ,26 ,0 ,set (dists )- {"AA" }))