◂ 14 décembre 2023 ▸
Parabolic Reflector Dish : Faire glisser des cailloux dans 4 directions successives
...O.....#O#... …
#OO..O.##..#... …
.###..O.#...O.# …
O.O......OO.O#. …
.#....#.O#...O. …
.#.....O..#...# …
⋮
- code.py
- code_optim_deplacer_cailloux.py
- code_oneLiners_lievreTortue.py
- code_numpy.py
from functools import reduce
from typing import Any
Grille = list[str]
""" Le Nord est à gauche. On tourne la grille au départ. """
def calc_north_load(grille: Grille) -> int :
return sum( len(ligne)-c for ligne in grille for c,v in enumerate(ligne) if v == 'O' )
def rotation_droite(grille: Grille) -> Grille:
return [''.join([ grille[len(grille)-1-r][c] for r in range(len(grille))]) for c in range(len(grille[0])) ]
def rotation_gauche(grille: Grille) -> Grille :
return [''.join([grille[r][len(grille[0])-1-c] for r in range(len(grille))]) for c in range(len(grille[0])) ]
def grille_penchee_a_gauche(grille: Grille) -> Grille:
return [ligne_penchee_a_gauche(ligne) for ligne in grille]
def ligne_penchee_a_gauche(ligne: str) -> str:
return '#'.join([ (nb:=token.count('O'))*'O' + (len(token)-nb)*'.' for token in ligne.split('#')])
grille: Grille = rotation_gauche(open("input.txt").read().split())
solution_partie1 = calc_north_load(grille_penchee_a_gauche(grille))
def cycle(grille: Grille) -> Grille:
return reduce(lambda g,_:rotation_droite(grille_penchee_a_gauche(g)), 'meow', grille)
""" Implémentation de détection de boucle (répétition d'état) sans mise en cache, grâce à l'algo lièvre-tortue """
def lievre_tortue(f: callable, tortue:Any) -> tuple[int,int,Any]:
i,longueur_boucle = 0,1
for _ in '^^':
lievre = f(tortue)
while tortue != lievre:
tortue, lievre, i = f(tortue), f(f(lievre)), i+1
longueur_boucle = i-longueur_boucle
return (i, longueur_boucle, tortue)
def do_cycles(grille: Grille, nombre_cycles_a_faire: int) -> Grille:
cycles_faits, longueur_boucle, grille = lievre_tortue(cycle, grille)
return reduce(lambda g,f:f(g), ((nombre_cycles_a_faire - cycles_faits) % longueur_boucle)*[cycle], grille)
print("Réponse partie 1:", solution_partie1)
print("Réponse partie 2:", calc_north_load(do_cycles(grille, 1_000_000_000)))