Advertisement
Guest User

Untitled

a guest
Dec 20th, 2022
825
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.99 KB | None | 0 0
  1. from typing import Iterator
  2.  
  3. from aoclib import show_answers, get_puzzle_input
  4. import re
  5. from collections import defaultdict
  6.  
  7. def solutions() -> Iterator[int]:
  8.  
  9.     pattern = "Valve (?P<at>\w\w).*rate\=(?P<rate>\d+).*valves? (?P<to>.*)"
  10.     data = {(g:=re.search(pattern,line).groupdict())["at"]:(int(g["rate"]),frozenset([n.strip() for n in g["to"].split(",")])) \
  11.             for line in get_puzzle_input(day=16,example=False)}
  12.  
  13.     #Creating a distance map
  14.     paths = defaultdict(list)
  15.     visits = defaultdict(set)
  16.     trs = [("AA","AA")]
  17.     rates = {k:r for k,(r,_) in data.items()}
  18.     while trs:
  19.         tr = trs.pop(0)
  20.         for to_valve in data[tr[1]][1]:
  21.             next_tr = tr[0],to_valve
  22.             if tr[0]==to_valve or to_valve in visits[tr[0]]:
  23.                 continue
  24.             visits[tr[0]].add(to_valve)
  25.             if tr in paths and not next_tr in paths:
  26.                 paths[next_tr] = paths[tr] + [tr[1]]
  27.             elif tr[0]==tr[1]:
  28.                 paths[next_tr] = []
  29.             trs.append((to_valve,)*2)
  30.             trs.append(next_tr)
  31.     distancies = {(v1,v2):len(v)+1 for (v1,v2),v in paths.items() if rates[v2] and (rates[v1] or v1=="AA")}
  32.    
  33.    
  34.     #Part 1 and part 2 generelized so that you could solve for another elephant in part 3 =)
  35.     init_part1 = set([(0,frozenset({"AA"}),((30,"AA"),))])
  36.     init_part2 = set([(0,frozenset({"AA"}),((26,"AA"),(26,"AA")))])
  37.     for states in init_part1,init_part2:
  38.         t0=pc()
  39.         max_pressure = 0
  40.         iterations = 0
  41.         while states:
  42.             iterations+=1
  43.             pr, open_valves, agents = states.pop()
  44.             valves = set(rates.keys())-open_valves
  45.             while valves:
  46.                 to_valve = valves.pop()
  47.                 info = []
  48.                 for i, (tl,from_valve) in enumerate(agents):
  49.                     tr = from_valve, to_valve
  50.                     if tr not in distancies:
  51.                         continue
  52.                     dist = distancies[tr]
  53.                     rate = rates[to_valve]
  54.                     new_tl = tl - dist - 1
  55.                     if new_tl<=0:
  56.                         continue
  57.                     new_pr = pr + rate*new_tl
  58.                     new_open_valves = open_valves.union({to_valve})
  59.                     info.append((new_tl,new_pr,new_open_valves,to_valve,i))
  60.                 if info:
  61.                     new_tl,new_pr,new_open_valves,to_valve,index = max(info)
  62.                     new_agents = tuple(sorted((new_tl,to_valve) if i==index else a for i,a in enumerate(agents)))
  63.                     states.add((new_pr,new_open_valves,new_agents))
  64.                     if new_pr>max_pressure:
  65.                         max_pressure = new_pr
  66.             if iterations%100000==0:
  67.                 print(max_pressure,f"time: {pc()-t0:.2f}, iter: {iterations}, states: {len(states)}")
  68.         print(max_pressure,f"time: {pc()-t0:.2f}, iter: {iterations}, states: {len(states)}")
  69.         yield max_pressure
  70.        
  71. show_answers(solutions)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement