fork download 
  1. import sys
  2. from pprint import pprint
  3.  
  4. sys.setrecursionlimit(10**6) 
  5.  
  6. rate_dict = dict()
  7. neighbors_dict = dict()
  8. for line in sys.stdin:
  9.     line = line.strip()
  10.     if line:
  11.         args = line.split()
  12.         name = args[1]
  13.         rate = int(args[4].split('=')[1][:-1])
  14.         next_hop = args[9:]
  15.         # remove ',' from the next_hop elements (if any)
  16.         next_hop = list(map(lambda x: x.replace(',', ''), next_hop))
  17.         rate_dict[name] = rate
  18.         neighbors_dict[name] = next_hop
  19.  
  20. cache = dict() # for memoization
  21. opened = set()
  22.  
  23. def explore(time_left, valve, current_flow):
  24.     global cache, opened, neighbors_dict, rate_dict
  25.  
  26.     if time_left <= 0: return current_flow # time's up!
  27.  
  28.     # no need to explore further if we know already that this solution won't be any better!
  29.     if (time_left, valve) in cache and cache[(time_left, valve)] >= current_flow:
  30.         return 0
  31.  
  32.     # the first time we register the value or we found a better one
  33.     # i.e. spending the same amount of time and reaching the same valve after releasing more pressure (than the previous try)
  34.     cache[(time_left, valve)] = current_flow
  35.  
  36.     # we have 2 options:
  37.     # (1) we don't open the current valve (skip)
  38.     ans = 0
  39.     for neighbor in neighbors_dict[valve]:
  40.         ans = max( ans,
  41.                    explore(
  42.                         time_left - 1,
  43.                         neighbor,
  44.                         current_flow
  45.                     )
  46.                 )
  47.  
  48.     # (2) we open the current valve (if it's not opened already!)
  49.     if valve not in opened:
  50.         opened.add(valve)
  51.         time_left -= 1 # we need a minute to open the valve
  52.         for neighbor in neighbors_dict[valve]:
  53.             ans = max( ans,
  54.                        explore(
  55.                             time_left - 1,
  56.                             neighbor,
  57.                             current_flow + ( time_left * rate_dict[valve] )
  58.                         )
  59.                     )
  60.         opened.remove(valve)
  61.  
  62.     return ans
  63.  
  64.  
  65. print(explore(30, 'AA', 0))
  66. # print(max(cache.values()))
  67.  
  68.  
Success #stdin #stdout 0.13s 9800KB
comments (?)
stdin 
Valve VR has flow rate=11; tunnels lead to valves LH, KV, BP
Valve UV has flow rate=0; tunnels lead to valves GH, RO
Valve OH has flow rate=0; tunnels lead to valves AJ, NY
Valve GD has flow rate=0; tunnels lead to valves TX, PW
Valve NS has flow rate=0; tunnels lead to valves AJ, AA
Valve KZ has flow rate=18; tunnels lead to valves KO, VK, PJ
Valve AH has flow rate=0; tunnels lead to valves ZP, DI
Valve SA has flow rate=0; tunnels lead to valves VG, JF
Valve VK has flow rate=0; tunnels lead to valves RO, KZ
Valve GB has flow rate=0; tunnels lead to valves XH, AA
Valve AJ has flow rate=6; tunnels lead to valves IC, OH, ZR, NS, EM
Valve PJ has flow rate=0; tunnels lead to valves KZ, SP
Valve KO has flow rate=0; tunnels lead to valves KZ, LE
Valve AA has flow rate=0; tunnels lead to valves TW, GB, TI, NS, UL
Valve TW has flow rate=0; tunnels lead to valves TU, AA
Valve VG has flow rate=25; tunnel leads to valve SA
Valve BP has flow rate=0; tunnels lead to valves RO, VR
Valve XH has flow rate=0; tunnels lead to valves GB, RI
Valve TX has flow rate=0; tunnels lead to valves RI, GD
Valve IR has flow rate=10; tunnels lead to valves TN, NY, JF
Valve TU has flow rate=0; tunnels lead to valves JD, TW
Valve KC has flow rate=0; tunnels lead to valves SP, RO
Valve LN has flow rate=0; tunnels lead to valves EM, RI
Valve HD has flow rate=0; tunnels lead to valves FE, SC
Valve KE has flow rate=0; tunnels lead to valves OM, RI
Valve VY has flow rate=0; tunnels lead to valves PW, BS
Valve LH has flow rate=0; tunnels lead to valves OM, VR
Valve EM has flow rate=0; tunnels lead to valves AJ, LN
Valve SO has flow rate=22; tunnels lead to valves ZP, FE
Valve EC has flow rate=0; tunnels lead to valves OM, UL
Valve KV has flow rate=0; tunnels lead to valves SP, VR
Valve FE has flow rate=0; tunnels lead to valves SO, HD
Valve TI has flow rate=0; tunnels lead to valves AA, PW
Valve SC has flow rate=14; tunnel leads to valve HD
Valve ZP has flow rate=0; tunnels lead to valves SO, AH
Valve RO has flow rate=19; tunnels lead to valves UV, BP, VK, KC
Valve ZR has flow rate=0; tunnels lead to valves OM, AJ
Valve JL has flow rate=21; tunnels lead to valves GN, TN
Valve PW has flow rate=9; tunnels lead to valves TI, GN, VY, GD, IC
Valve UL has flow rate=0; tunnels lead to valves EC, AA
Valve GN has flow rate=0; tunnels lead to valves JL, PW
Valve TN has flow rate=0; tunnels lead to valves JL, IR
Valve NV has flow rate=0; tunnels lead to valves RI, JD
Valve DI has flow rate=23; tunnels lead to valves LE, AH
Valve IC has flow rate=0; tunnels lead to valves PW, AJ
Valve JF has flow rate=0; tunnels lead to valves SA, IR
Valve LE has flow rate=0; tunnels lead to valves DI, KO
Valve BS has flow rate=0; tunnels lead to valves JD, VY
Valve JD has flow rate=15; tunnels lead to valves NV, TU, BS
Valve SP has flow rate=24; tunnels lead to valves KC, KV, PJ
Valve NY has flow rate=0; tunnels lead to valves IR, OH
Valve OM has flow rate=7; tunnels lead to valves EC, GH, KE, ZR, LH
Valve GH has flow rate=0; tunnels lead to valves OM, UV
Valve RI has flow rate=3; tunnels lead to valves NV, KE, LN, XH, TX
stdout 
1852
https://ideone.com/zKmUFl
language:
Python 3 (python  3.12)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!