Advent of code

◂ 17 décembre 2022 ▸

  Pyroclastic Flow : Tetris: calculer la hauteur finale d'une chute de pierres

>>><<>>><<<>>>><<>>><<<<>>>><<<>>>><<<>>><<<<>><<><>><<<>>>><<< … 

1. codePartie1.py
2. code.py
3. amelioration_estLibre.diffy
4. visualisation.txt
5. visualisationTerminalCouleurs.png
6. couleurs.diffy

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

JETS = lines[0]
NB_COLONNES = 7
VIDE = ' '
NB_PIERRES = [2022, 1000000000000]
TYPES_PIERRES = '-+LIO'
MOUVEMENTS = {'>':1, '<':-1}

HAUTEURS_PIECES = {'-':1, '+':3, 'L':3, 'I':4, 'O':2}
LARGEURS_PIECES = {'-':4, '+':3, 'L':3, 'I':1, 'O':2}
PIECES = {
        '-':((0,0),(1,0),(2,0),(3,0)),
        '+':((1,0),(0,1),(1,1),(2,1),(1,2)),
        'L':((0,0),(1,0),(2,0),(2,1),(2,2)),
        'I':((0,0),(0,1),(0,2),(0,3)),
        'O':((0,0),(0,1),(1,0),(1,1)),
        }

HAUTEUR_MAX_MUR = 3*NB_PIERRES[-1]  # hauteur moyenne = 2.6, donc 3*NB_PIERRES bien suffisant pour avoir au moins ce nombre de pierres
if HAUTEUR_MAX_MUR > 100000:        # on évite un tableau de taille 1000 milliards,
    HAUTEUR_MAX_MUR = 100000        #    et on croise les doigts pour trouver un cycle avant 10'000

mur = [ NB_COLONNES*[VIDE] for _ in  range(HAUTEUR_MAX_MUR) ] 
mur[0] = NB_COLONNES * '#'   # plancher à hauteur 0
hauteurAtteinte = 0    # plancher

def estLibre(typePierre, px, py, mur):
    # Pas besoin de tester les bords gauche/droite sur chaque morceau
    if px < 0 or px + LARGEURS_PIECES[typePierre] > NB_COLONNES:
        return False

    return all( mur[py+dy][px+dx] == VIDE  for (dx,dy) in PIECES[typePierre])

def placer(typePierre, mur, px, py):
    for (dx,dy) in PIECES[typePierre]:
        mur[py + dy][px + dx] = typePierre


# hauteur libre dans une colonne donnée, depuis la hauteur hauteurAtteinte vers le bas
def hauteurLibre(mur, hauteurAtteinte, indiceColonne):
    for h in range(hauteurAtteinte, 0, -1):
        if mur[h][indiceColonne] != VIDE:
            return hauteurAtteinte - h
    return hauteurAtteinte

# pour repérer un cycle: il faut la hauteur libre de chaque colonne et où on en est dans les cailloux et les jets
def getConfig(mur, hauteurAtteinte, typePierre, indiceJet):
    profondeurs = tuple(map(lambda col:hauteurLibre(mur, hauteurAtteinte, col), range(NB_COLONNES)))
    return (indiceJet, typePierre, profondeurs)    # d'abord indiceJet, c'est le plus souvent différent et donc la comparaison sera False plus rapidement

# pour repérer les cycles dans les agencements de cailloux (obligatoire pour partie 2)
anciennesConfigs = []
hauteurAnciennesConfigs = []  # pour calculer la hauteur finale


cycle_typesPierres = cycle(TYPES_PIERRES)     # '-', '+', 'L', 'I', 'O', '-', '+'… 
cycle_indexJets    = cycle(range(len(JETS)))  # 0, 1, 2, …, 0, 1, 2, …    /depuis le temps que j'attendais de pouvoir utiliser itertools.cycle :)

for _ in range(NB_PIERRES[-1]):
    typePierre = next(cycle_typesPierres)
    posX = 2        # coin en bas à gauche
    posY = hauteurAtteinte + 4

    rienDessous = True
    while rienDessous:
        indiceJet = next(cycle_indexJets)
        if estLibre(typePierre, posX + MOUVEMENTS[JETS[indiceJet]], posY, mur):
            posX += MOUVEMENTS[JETS[indiceJet]]

        if estLibre(typePierre, posX, posY-1, mur):
            posY -= 1
        else:
            rienDessous = False

    placer(typePierre, mur, posX, posY)
    hauteurAtteinte = max(hauteurAtteinte, posY + HAUTEURS_PIECES[typePierre] - 1)

    # repérage de cycle:
    config = getConfig(mur, hauteurAtteinte, typePierre, indiceJet)
    if config in anciennesConfigs:               # essayer de trouver directement l'indice renvoie une exception en cas d'échec, c'est couteux
        indice = anciennesConfigs.index(config)  # on doit reparcourir de nouveau la liste, mais on le fait qu'une seule fois en fin de programme

        longueurCycle = len(anciennesConfigs) - indice
        hauteurCycle = hauteurAtteinte - hauteurAnciennesConfigs[indice]

        for numPartie in range(len(NB_PIERRES)):
            nbPierresPartie = NB_PIERRES[numPartie]
            nbCycles = (nbPierresPartie - indice - 1) // longueurCycle
            longueurDernierBoutCycle = (nbPierresPartie - indice - 1) % longueurCycle
            print("Réponse partie " + str(numPartie + 1) + ':',   hauteurAnciennesConfigs[indice + longueurDernierBoutCycle]   +   nbCycles * hauteurCycle)
        break
    else:
        anciennesConfigs.append(config)
        hauteurAnciennesConfigs.append(hauteurAtteinte)



    ## recherche sans reparcourir pour avoir indice (utiliser directement index()) mais sans Exception couteuse
    #    anciennesConfigs.append(config)
    #    indice = anciennesConfigs.index(config)  # on ne cherche qu'une seule fois et on sait que config est dedans
    #    dejaLa = (indice < len(anciennesConfigs) - 1)   # déjà là avant s'il est trouvé avant la fin



# si pas trouvé de cycle mais arrivé au bout:
if hauteurAtteinte == hauteurAnciennesConfigs[-1]:
    print("Réponse partie " + str(len(NB_PIERRES)) + ':',   hauteurAtteinte)



# Dessiner pour le plaisir le début et la fin de la tour :
if True:
    if hauteurAtteinte == hauteurAnciennesConfigs[-1]:
        h = hauteurAtteinte
        vides = NB_COLONNES * [0]
    else:
        h = hauteurAnciennesConfigs[indice + longueurDernierBoutCycle] 
        vides = anciennesConfigs[indice + longueurDernierBoutCycle][2]
    print('\n#' + NB_COLONNES*VIDE + '#')
    for i in range(h, h - 20, -1):
        ligne = [(h-i < vides[c]) and VIDE or mur[i][c] for c in range(NB_COLONNES)]
        print('#' + ''.join(ligne) + '#')
    for _ in range(3):
        print('    .')
    for i in range(20, -1, -1):
        print('#' + ''.join(mur[i]) + '#')