Advent of code

◂ 16 décembre 2022 ▸

  Proboscidea Volcanium : Ouvrir des vannes dans un réseaux dans l'ordre optimal

Valve RO has flow rate=5; tunnels lead to valves NO, FD, QV, BV

 Valve GT has flow rate=0; tunn … 

1. graphe.png
2. code.py
3. codePartie1_ancienAlgo.py
4. codePartie2_tropLent.py

from functools import cache

f = open("input.txt", 'r')
lines = [line[:-1] for line in f.readlines()]

START = 'AA'
TEMPS_PARTIE1 = 30
TEMPS_PARTIE2 = 26

VANNES = []       # 50 vannes au total
DEBITS = []
DISTANCES = None  # tableau 50×50

for line in lines:
    tokens = line.split()
    vanne = tokens[1]
    debit = int(tokens[4][5:-1])
    VANNES.append(vanne)
    DEBITS.append(debit)
DEBITS = tuple(DEBITS)


NOMBRE_VANNES_TOT = len(VANNES)  
maxLongueurChemin = NOMBRE_VANNES_TOT - 1  # si graphe connexe
DISTANCES = [ (NOMBRE_VANNES_TOT * [maxLongueurChemin + 1]) for _ in VANNES]

for line in lines:
  tokens = line.split()
  vanne = tokens[1]
  vannesTunnels = list(map(lambda s:VANNES.index(s), map(lambda s: s[-1]==',' and s[:-1] or s, tokens[9:])))
  indiceVanne = VANNES.index(vanne)
  for vanneTunnel in vannesTunnels:
      DISTANCES[vanneTunnel][indiceVanne] = 1
      DISTANCES[indiceVanne][vanneTunnel] = 1


### Calcul des distances entre tous les points du graphes, avec l'algo de
###    https://fr.wikipedia.org/wiki/Algorithme_de_Floyd-Warshall
for k in range(len(VANNES)):
    DISTANCES[k][k] == 0
    for i in range(len(VANNES)):
        for j in range(len(VANNES)):
            DISTANCES[i][j] = min(DISTANCES[i][j], DISTANCES[i][k] + DISTANCES[k][j])



VANNES_UTILES = tuple([ i for i in range(len(VANNES)) if DEBITS[i] > 0])


# le cache permet de passer 60 secondes à 25 secondes d'exécution
@cache
def getChemins(vanneEnCours, vannesUtilesRestantes, tempsRestant, departChemin1=None):
    chemins = []
    debitSupplementaire = tempsRestant * DEBITS[vanneEnCours]
    for i in range(len(vannesUtilesRestantes)):
        nouvellesVannesUtilesRestantes = list(vannesUtilesRestantes[:])
        prochaineVanne = nouvellesVannesUtilesRestantes.pop(i)
        if departChemin1 and prochaineVanne < departChemin1:  # eviter de calculer à double les répartitions symétriques entre moi et l'éléphant
            continue
        temps = DISTANCES[prochaineVanne][vanneEnCours] + 1
        if temps >= tempsRestant:
            continue
        for (debitTotal, parcours) in getChemins(prochaineVanne, tuple(nouvellesVannesUtilesRestantes), tempsRestant - temps):
            nouveauDebit = debitTotal + debitSupplementaire
            nouveauParcours = [vanneEnCours] + parcours
            chemins.append( (nouveauDebit, nouveauParcours) )

    if len(chemins) == 0:   # plus le temps d'aller ailleurs (ou plus de vanne restante, mais jamais le cas)
        chemins = [ (debitSupplementaire, [vanneEnCours]) ]   # créer un parcours qui s'arrête ici
    return chemins


### Partie 1
chemins = getChemins(VANNES.index(START), VANNES_UTILES, TEMPS_PARTIE1)
meilleurDebit = max(debit for (debit, parcours) in chemins)
meilleursChemins = [[VANNES[v] for v in parcours] for (debit, parcours) in chemins if debit == meilleurDebit]
print("Réponse partie 1:", meilleurDebit, meilleursChemins)

### Partie 2
VANNES_UTILES_SET = set(VANNES_UTILES)

meilleurDebit = 0
meilleurChemin1   = None
meilleursChemins2 = None

chemins1 = getChemins(VANNES.index(START), VANNES_UTILES, TEMPS_PARTIE2)
for (debit1, parcours1) in chemins1:
    departChemin1 = parcours1[0]
    chemins2 = getChemins(VANNES.index(START), tuple(VANNES_UTILES_SET.difference(set(parcours1))), TEMPS_PARTIE2, departChemin1) 
    maxDebits2 = max(debit for (debit, parcours) in chemins2) 
    if debit1 + maxDebits2 >= meilleurDebit:
        meilleurDebit = debit1 + maxDebits2
        meilleurChemin1 = [VANNES[v] for v in parcours1]
        meilleursChemins2 = [[VANNES[v] for v in parcours2] for (debit2, parcours2) in chemins2 if debit2 == maxDebits2]
print("Réponse partie 2:", meilleurDebit, meilleurChemin1, meilleursChemins2)