Re: Ça chauffe, ça chauffe !

Côté algo :
* on crée nos valves (ou vannes, osef) ;
* on lie les objets les uns aux autres pour les liaisons directes ;
* on explore de proche en proche pour enregistrer la liste des autres valves avec la distance pour y aller depuis chaque valve ;
* on n'optimise pas en stockant la distance retour dans la valve distante, vu mon algo ça pouvait empêcher la valve distante de calculer certaines distances, modélisation fausse, résultat faux, et les données de test ne sont pas affectées ;
* on parcours à nouveau nos valves et on supprime les chemins vers les valves à flux nul, on réduit le problème aux seules valves utiles (15 en situation réelle, 6 en test), mais avec des distances complètes.

Là on ne cherche plus à se déplacer, juste à mesurer le temps qui passe à partir d'ici ou de là.
Et donc pour chaque situation :
* valve où on se trouve
* temps restant
* score final actuel (dès qu'on ouvre une valve on calcule directement toute la vapeur dégagée jusqu'au bout du temps imparti)
* liste des valves ouvertes

On calcule le score final en allant ouvrir chaque vanne accessible.

On récurse à partir de chaque destination possible (vannes encore ouvertes), et une fois au bout, soit du temps disponible (données réelles), soit de vannes à ouvrir (données de test), on a un chemin avec un score.

On ne retourne que le meilleur score, et pas tous les chemins trouvés, sinon on explose la RAM et la durée.
Et à la fin on a notre résultat.

class Valve:
 def __init__(self, name, flow, links):
 self.name = name
 self.flow = int(flow)
 self.locallinks = links.strip().split(", ")
 self.links = dict()
 # considering valve with no flow as already opened
 self.open = self.flow == 0
 def __repr__(self):
 return f"{self.name}@{self.flow}: {' '.join(f'{n.name}:{d}' for n, d in sorted(self.links.items()))}"
 def __lt__(self, other):
 return self.name < other.name
 def linkvalves(self, valves):
 self.valves = valves
 self.locallinks = [valves[link] for link in self.locallinks]
 # self.links = {link: 1 for link in self.locallinks}
 self.links[self] = 0
 def graph(self):
 explore = {self, }
 distance = 0
 while explore:
 distance += 1
 step = set(
 link
 for valve in explore
 for link in valve.locallinks
 if link not in self.links
 )
 for valve in step:
 self.links[valve] = distance
 explore = step
 def reducegraph(self):
 self.links = {
 link: score
 for link, score in self.links.items()
 if link.flow
 }
 def getscores(self, timeleft, currentscore, opened):
 self.scores = dict()
 for link, distance in self.links.items():
 timeafter = timeleft - distance - 1
 # valve already opened or too far to be useful
 if link in opened or timeafter <= 0:
 continue
 self.scores[link] = currentscore + timeafter * link.flow, timeafter
 return self.scores
regex = re.compile(
 r"Valve ([A-Z]+) has flow rate=(\d+); "
 r"tunnels? leads? to valves? ([A-Z, ]+)")
valves = {
 v.name: v
 for v in (
 Valve(*regex.match(line).groups())
 for line in sys.stdin
 )
}
for valve in valves.values():
 valve.linkvalves(valves)
for valve in valves.values():
 valve.graph()
for valve in valves.values():
 valve.reducegraph()
def nextscores(valve, currentscore, timeleft, opened, currentpath):
 path = valve.getscores(timeleft, currentscore, opened)
 if not path: # end of the line !
 return currentscore, timeleft, currentpath, 1
 explored = 0
 r = (0, 0, "", 0)
 for link, (score, time) in path.items():
 x = nextscores(
 link,
 score,
 time,
 opened + [link],
 currentpath + "->" + link.name
 )
 explored += x[-1]
 r = x if x > r else r
 return r[0], r[1], r[2], explored
score, time, path, explored = nextscores(valves['AA'], 0, 30, [], 'AA')
print(f"Score {score}, explored {explored} paths : {path}")

Pour l'exercice 2 on conserve la même modélisation, aucun changement.
La fonction d'exploration change : on lui fourni deux explorateurs, chacun avec son chemin parcouru, et son temps restant.
Et on travaille sur l'explorateur qui a le plus de temps disponible à chaque itération.

class explorer: # pour se simplifier la vie
 def __init__(self, valve, timeleft, path=None):
 self.valve = valve
 self.timeleft = timeleft
 self.path = path or valve.name
 def __call__(self, s):
 return f"{self.path}->{s}"
 def __repr__(self):
 return f"time remaining {self.timeleft}{self.path}"
 def __lt__(self, other):
 return self.timeleft < other.timeleft
def doublescores(e1, e2, currentscore, opened):
 if e1 < e2: # look using the explorer with the most time remaining
 e2, e1 = e1, e2
 path = e1.valve.getscores(e1.timeleft, currentscore, opened)
 if not path: # end of the line !
 return (currentscore, e1, e2, 1)
 explored = 0
 r = (0, 0, "", 0)
 for link, (score, time) in path.items():
 x = doublescores(
 explorer(link, time, e1(link.name)),
 e2,
 score,
 opened + [link],
 )
 explored += x[-1]
 r = x if x > r else r
 return r[0], r[1], r[2], explored
score, p1, p2, explored = doublescores(
 explorer(valves['AA'], 26),
 explorer(valves['AA'], 26),
 0,
 [],
)
print(f"Score {score}, explored {explored} paths, {p1}{p2}")

Et voilà, on a bien perdu du temps et fait chauffer la machine.

• Yth.