◂ 22 décembre 2023 ▸
Sand Slabs : Briques qui tombent, donc Tetris 3D de I de différentes longueurs
5,0,63~7,0,63
9,5,296~9,8,296
9,2,274~9,4,274
1,4,2~1,6,2
9,6,347~9,6,349
⋮
- code.py
from itertools import product
f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]
from typing import Optional
Brique = list[range] # [range, range, range]
IndexBrique = int
X,Y,Z = 0,1,2 # "besoin" que de Z
briques: list[Brique] = []
for line in lines:
triplets = [ map(int, triplet.split(',')) for triplet in line.split('~') ]
briques.append([ range(start, end+1) for start,end in zip(*triplets) ])
rangex, rangey, rangez = [range(min(b[i].start for b in briques), max(b[i].stop for b in briques)) for i in range(3)]
print("Ranges:", rangex, rangey, rangez)
# Calcul des positions occupées par les briques (38'200 cases): plus rapide que de vérifier tous les couples de briques possibles (1'485² paires)
colonnes: list[list[list[Optional[IndexBrique]]]] = [ [rangez.stop * [None] for y in rangey] for x in rangex ]
for ib,b in enumerate(briques):
for x,y,z in product(*b):
assert colonnes[x][y][z] is None
colonnes[x][y][z] = ib
# Calcul pour chaque brique des briques situées immédiatement dessous
en_dessous: list[set[IndexBrique]] = [ set() for i in range(len(briques)) ]
for x in rangex:
for y in rangey:
lastB: Optional[IndexBrique] = None
lastZ: Optional[int] = None
for z,ib in enumerate(colonnes[x][y]): #if ib is not None:
if ib is None:
continue
if lastB is None:
lastB = ib
elif ib != lastB:
en_dessous[ib].add(lastB)
lastB = ib
lastZ = z
# Calcul de la hauteur après chute: se fait récursivement à partir des briques immédiatement en dessous.
# hauteur_finales est finalement un simple cache, et la fonction pourrait faire 1 ligne en utilisant @lru_cache(len(briques))
hauteurs_finales: list[Optional[int]] = len(briques) * [None]
def calc_hf(ib):
if hauteurs_finales[ib] is not None:
return hauteurs_finales[ib]
hauteurs_finales[ib] = max( (calc_hf(ib2)+len(briques[ib2][Z]) for ib2 in en_dessous[ib]), default=0 )
return hauteurs_finales[ib]
for ib,b in enumerate(briques):
h = calc_hf(ib)
b[Z] = range( h, h + len(b[Z]) )
# Calcul, pour chaque brique b, de ses supports, c'est-à-dire des briques sur lesquelles elle est posée :
# -> pour chaque brique b2 juste en dessous, on a la position de notre brique b[Z].start = 1 + la pos du plus haut cube de b2 = b2[Z].stop
supports: list[list[IndexBrique]] = [ [ib2 for ib2 in en_dessous[ib] if briques[ib2][Z].stop == b[Z].start] for ib,b in enumerate(briques) ]
# Calcul du nombre de briques qui n'ont pas qu'une seul support exactement (0 ou 2 et plus ok)
reponse_partie_1 = len([ib for ib,b in enumerate(briques) if not min((len(supps) for supps in supports if ib in supps), default=0) == 1])
print("Réponse partie 1:", reponse_partie_1)
# Une brique tombe avec la brique enlevée si elle n'est pas sur le sol (= pas 0 support) et que tous ses supports tombent aussi.
# -> fonction récursive. On part de l'idée que la brique enlevée "tombe" quand on l'enlève, pour éviter de traiter un cas particulier
from functools import lru_cache
@lru_cache(None)
def tombe_si_enleve(ib: IndexBrique, enlevee: IndexBrique) -> bool:
if ib == enlevee:
return True
if len(supports[ib]) == 0:
return False
return all(tombe_si_enleve(ib2, enlevee) for ib2 in supports[ib])
print("Partie 2… calcul de la réponse (récursif avec cache, prend un peu de temps)…")
# Pas oublier de faire - 1 car on ne compte au final pas la brique enlevée (aussi comptée par tombe_si_enleve comme brique qui tombe quand on l'enlève)
reponses_partie_2 = sum( sum(1 for ib,b in enumerate(briques) if tombe_si_enleve(ib, enl)) - 1
for enl,_ in enumerate(briques) )
print("Réponse partie 2:", reponses_partie_2)