• # Rhaaaaaa !!!

    Posté par (Mastodon) . En réponse au message Advent of Code 2023, jour 21. Évalué à 3.

    Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
    encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution...

    On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
    Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.

    Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
    Pour les zones en diagonale, on va rentrer par la case au coin.
    Ya pas plus rapide.

    Le terrain fait 131x131, et le départ au centre en 65x65.
    Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre.
    65 + 1 + 131 * (distance - 1) quand on va en ligne droite nord, sud, est ou ouest.
    Et 65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2) pour les cases qui sont au moins un peu en diagonale.
    Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
    On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
    On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.

    On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être plein tout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.
    Ben oui, si on entre dans une zone mettons via (0, 0), la case (0, 0) d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.
    On a en fait un damier de damiers, yay !

    Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
    On additionne.

    En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.

    ...●くろまる...
..●くろまる○しろまる●くろまる..
.●くろまる○しろまる●くろまる○しろまる●くろまる.
●くろまる○しろまる●くろまる○しろまる●くろまる○しろまる●くろまる
.●くろまる○しろまる●くろまる○しろまる●くろまる.
..●くろまる○しろまる●くろまる..
...●くろまる...

    En distance 0 on a la zone de départ.
    En distance 1 on a 4 zones directement liées.
    En distance 2 on a 4 zones directes, et 4 zones diagonales.
    En distance 3 c'est 4 et 8.
    En distance n, c'est 4 et (n-1)*4.
    Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
    Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.

    Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.

    Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
    Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
    Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
    Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
    Je dénombre, j'additionne.

    Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
    On passe à la distance suivante.
    On s'arrête avec une petite marge où on va additionner des zéros.
    J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes...

    Et puis, voilà, résultat :)

    Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.

    from sys import stdin
from dataclasses import dataclass
from functools import cached_property
data = stdin.read().strip().splitlines()
LARGEUR = len(data[0]) # 131
HAUTEUR = len(data) # 131
XMAX = LARGEUR - 1
YMAX = HAUTEUR - 1
MIDDLE = XMAX // 2 # 65
ROCKS = frozenset((x, y) for y, _ in enumerate(data) for x, t in enumerate(_) if t == '#')
START = "".join(data).index("S")
START = (START % LARGEUR, START // LARGEUR) # 65x65
STEPS1, STEPS2 = (64, 26501365)
@dataclass
class exploration:
 sx: int = 0
 sy: int = 0
 def run(self):
 def dest(x, y):
 yield (x - 1), y
 yield (x + 1), y
 yield x, (y - 1)
 yield x, (y + 1)
 explored = {(self.sx, self.sy)}
 exploring = {(self.sx, self.sy)}
 steps = [{(self.sx, self.sy)}]
 overexplored = set()
 s = 0
 while exploring:
 s = s + 1
 exploring = {
 d
 for x, y in exploring
 for d in dest(x, y)
 if d not in ROCKS
 }.difference(explored).difference(overexplored)
 for x, y in exploring:
 if (x < 0 or x >= LARGEUR or y < 0 or y >= LARGEUR) and (x, y) not in overexplored:
 overexplored.add((x, y))
 exploring.difference_update(overexplored)
 steps.append(exploring) # adds an empty set() at the end
 explored.update(exploring)
 self._exploration = steps
 self.even = self.explored(0, len(steps))
 self.odd = self.explored(1, len(steps))
 @cached_property
 def exploration(self):
 if not hasattr(self, '_exploration'):
 self.run()
 return self._exploration
 def explored(self, start=0, steps=None):
 steps = min(steps + 1, len(self.exploration))
 return sum(
 len(self.exploration[i])
 for i in range(start, steps, 2)
 )
exp1 = exploration(*START)
ex1 = exp1.explored(STEPS1 % 2, STEPS1)

    Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
    Pour le premier problème, on démarre en START = (65, 65) et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.

    Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.

    N = exploration(MIDDLE, 0)
S = exploration(MIDDLE, YMAX)
E = exploration(XMAX, MIDDLE)
W = exploration(0, MIDDLE)
NE = exploration(XMAX, 0)
NW = exploration(0, 0)
SE = exploration(XMAX, YMAX)
SW = exploration(0, YMAX)
# nombre minimum de pas pour explorer entièrement n'importe quelle zone.
MAXEXPLORATION = max(len(x.exploration) - 1 for x in [N, S, E, W, NE, NW, SE, SW])
def bigexploration(x, y):
 bx = MIDDLE + 1 + LARGEUR * (abs(x) - 1)
 by = MIDDLE + 1 + HAUTEUR * (abs(y) - 1)
 bd = bx + by
 if y == 0:
 if x > 0:
 return E, bx
 if x < 0:
 return W, bx
 return exp1, 0
 elif x == 0:
 if y > 0:
 return S, by
 return N, by
 if x > 0 and y > 0:
 return SE, bd
 if x > 0 and y < 0:
 return SW, bd
 if x < 0 and y > 0:
 return NE, bd
 return NW, bd
FINESTEPS = STEPS2 - MAXEXPLORATION * 2
odd = STEPS2 % 2
score = exp1.odd if odd else exp1.even

    La fonction bigexploration retourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en (x, y) par rapport à celle de départ.
    FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis * 2 pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplement STEPS2 - MAXEXPLORATION fonctionne.

    Après ça le code est moche et répétitif, dans l'esprit de bigexploration.

    for distance in range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2):
 for ex, steps in [
 bigexploration(0, -distance),
 bigexploration(0, distance),
 bigexploration(distance, 0),
 bigexploration(-distance, 0),
 ]:
 remaining = STEPS2 - steps
 odd = remaining % 2
 if steps > STEPS2:
 continue
 s = ex.odd if odd else ex.even
 if steps > FINESTEPS:
 s2 = ex.explored(odd, remaining)
 print(f"Finescore({remaining}) {s2} / {s} {s!=s2}")
 s = s2
 score += s
 if distance <= 1:
 continue
 for ex, steps in [
 bigexploration(1, 1 - distance),
 bigexploration(-1, 1 - distance),
 bigexploration(1, distance - 1),
 bigexploration(-1, distance - 1),
 ]:
 remaining = STEPS2 - steps
 odd = remaining % 2
 if steps > STEPS2:
 continue
 s = ex.odd if odd else ex.even
 if steps > FINESTEPS:
 s2 = ex.explored(odd, remaining)
 print(f"FineDiago({remaining}) {s2} / {s} {s!=s2}")
 s = s2
 score += s * (distance - 1)
ex2 = score

    Et bigre, même le range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2) m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !

    On vérifie l'intérêt de nos FINESTEPS avec les sorties :

    Finescore(130) 5635 / 7509 True
Finescore(130) 5661 / 7509 True
Finescore(130) 5624 / 7509 True
Finescore(130) 5672 / 7509 True
FineDiago(195) 6610 / 7509 True
FineDiago(195) 6571 / 7509 True
FineDiago(195) 6560 / 7509 True
FineDiago(195) 6573 / 7509 True
FineDiago(64) 957 / 7566 True
FineDiago(64) 958 / 7566 True
FineDiago(64) 946 / 7566 True
FineDiago(64) 957 / 7566 True

    On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.

    C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(

    • Yth, vivement les vacances.