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

#### Adaptation de la partie 1
#### BEAUCOUP TROP LENT !
from functools import cache

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

START = 'AA'
TEMPS = 26

VANNES = []
debits = []
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)

tunnels = []
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:])))
  tunnels.append(vannesTunnels)

# "qui" alterne entre 0 et 1. budy indique qu'on est en train de tourner une vanne
@cache
def meilleurdebit(positions, debits, tempsRestant, qui=0, busy=(False,False), comeFrom=(None,None)):
    if tempsRestant <= 0:
        return 0
    meilleur = 0

    if busy[qui]:
        busy = list(busy)
        busy[qui] = False
        return meilleurdebit(positions, debits, tempsRestant - qui, (qui+1)%2, tuple(busy), comeFrom)

    # pas tourner vanne
    for acces in tunnels[positions[qui]]:
        if acces == comeFrom[qui]:
            continue

        positionsN = list(positions)
        positionsN[qui] = acces
        comeFromN = list(comeFrom)
        comeFromN[qui] = positions[qui]
        meilleur = max(meilleur, meilleurdebit(tuple(positionsN), debits, tempsRestant - qui, (qui+1)%2, busy, tuple(comeFromN)))

    # tourner vanne
    if debits[positions[qui]] != 0:
        debitSupplementaire = debits[positions[qui]]*(tempsRestant-1)
        debits = list(debits)
        debits[positions[qui]] = 0   # ne pas rouvrir la vanne plus tard
        busy = list(busy)
        busy[qui] = True
        comeFromN = list(comeFrom)
        comeFromN[qui] = None
        for acces in tunnels[positions[qui]]:
            positionsN = list(positions)
            positionsN[qui] = acces
            meilleur = max(meilleur, debitSupplementaire + meilleurdebit(tuple(positionsN), tuple(debits), tempsRestant - qui, (qui+1)%2, tuple(busy), tuple(comeFromN)))

    return meilleur

print("Réponse partie 2:", meilleurdebit(2*(VANNES.index(START),), debits, TEMPS))