python caché

Un parcours de graph avec la complication que l'état du graph change pendant le parcours.

J'ai procédé en brute force et n'ai pas trouvé vraiment de moyen de couper des branches, si ce n'est marquer dès le départ les vannes à 0 comme étant déjà ouverte. Ça marchait bien jusqu'à 20 de profondeur mais passé ça, ça ramait trop (je timeout à 10 min). J'ai donc ajouté du cache et bim, 0.37s et 91MB de cache.

Cependant cette solution ne passe pas à l'échelle pour le parcours à 2 qui multiplie les branches.

J'ai ouïe dire des solutions où on pré-calcul des distances ou des scores mais je crois que je vais en rester là, j'ai déjà un retard de deux jours. J'ai atteint ma limite.

part 1

import sys
import re
pat = re.compile('Valve ([A-Z]{2}) has flow rate=([0-9]+); tunnels? leads? to valves? ([ ,A-Z]+)')
P = dict()
for i,l in enumerate(sys.stdin.read().splitlines()):
 g = pat.search(l)
 p = int(g[2])
 P[g[1]] = (i, p, g[3].split(", "))
STEPS = int(sys.argv[1])
ALLO = 0
for _,(i,p,_) in P.items():
 if p == 0:
 ALLO = ALLO | (1<<i) 
cache = {}
def step(pos="AA", left=STEPS, opens=ALLO):
 if left <= 0:
 return 0
 key = (pos, left, opens)
 r = cache.get(key, -1)
 if r >= 0:
 return r
 (i, p, nh) = P[pos]
 is_open = opens & (1 << i)
 a = 0
 if not is_open: # also means 0 - worth opening valve ?
 left -= 1 # cost to open
 opens = opens | (1<<i)
 a = p*(left+30-STEPS) + max(step(n, left-1, opens) for n in nh)
 b = max(step(n, left-1, opens) for n in nh)
 r = max(a,b)
 cache[key] = r
 return r
print(step())