En fait, les données tournent forcément en rond.
Avec mes données :
On a 269 actions, et 750 positions.
Il est obligatoire qu'en 269*750 = 201750 déplacements on ait bouclé, pour chaque fantôme.
Il y a 6 fantômes.
On va donc chercher la longueur du cycle, et toutes les sorties (zone en ..Z) possibles à partir d'une entrée (..A).
Dès qu'on retombe sur la première sortie trouvée, ET qu'on en est au même point dans le programme : on a fait une boucle.
Il se trouve que :
* toutes les longueurs de boucles (entre deux passages sur une même sortie) sont divisibles par 269, on a donc un vrai cycle dès qu'on retombe sur la première sortie visitée ;
* on tombe, pour chaque entrée, sur une et une seule sortie, donc chaque cycle est indépendant ;
* la durée pour tomber sur la sortie une première fois est la même que la longueur du cycle, donc tous les cycles commencent au même point dans le temps : 0.
Ex: A -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z
Le cycle fait n de long, n est un nombre entier de fois le programme exécuté (n divisible par 269), et démarrer en A est équivalent à démarrer en Z.
Ça simplifie à mort, puisqu'en pratique il ne reste plus qu'à calculer le PPCM des longueurs de cycles.
Si ça n'avait pas été le cas, les cycles auraient été beaucoup plus longs, mais toujours inférieurs à 169*750 = 201750, ce qui se calcule vite.
Par contre on aurait pu avoir des périodes de démarrage où on parcours quelques zones, avant de « tomber » sur un cycle, et de rester dedans, ils auraient pu ne pas commencer au même moment.
Et là le PPCM des cycles ne permet que d'avoir la longueur du super-cycle de l'ensemble des 6 fantômes, mais pas le moment où ils se trouvent tous sur une sortie en même temps.
Ce qui pourrait ne jamais arriver, et c'est probablement pour ça que le problème est « aussi simple », ça aurait peut-être été trop difficile de s'assurer qu'il y ait une solution, et que cette solution soit effectivement calculable rapidement ?
J'ai pas d'idée géniale, là tout de suite, sur comment résoudre ce problème là, mais la force brute n'est pas une solution, mon propre super-cycle faisant presque 12000 milliards, la solution on va pas tomber dessus par hasard.
J'ai failli tenter de résoudre le gros problème, mais heureusement j'ai d'abord regardé mes cycles, et la simplicité m'a fait prendre le raccourci d'un PPCM multiple vite fait.
Yth.
PS: ça me rappelle une histoire de Tetris l'année dernière, avec des cycles de dingue et beaucoup de méninges triturées :)
[^] # Re: Partie 2
Posté par Yth (Mastodon) . En réponse au journal Advent of Code 2023, day 8. Évalué à 2. Dernière modification le 08 décembre 2023 à 14:43.
En fait, les données tournent forcément en rond.
Avec mes données :
On a 269 actions, et 750 positions.
Il est obligatoire qu'en 269*750 = 201750 déplacements on ait bouclé, pour chaque fantôme.
Il y a 6 fantômes.
On va donc chercher la longueur du cycle, et toutes les sorties (zone en ..Z) possibles à partir d'une entrée (..A).
Dès qu'on retombe sur la première sortie trouvée, ET qu'on en est au même point dans le programme : on a fait une boucle.
Il se trouve que :
* toutes les longueurs de boucles (entre deux passages sur une même sortie) sont divisibles par 269, on a donc un vrai cycle dès qu'on retombe sur la première sortie visitée ;
* on tombe, pour chaque entrée, sur une et une seule sortie, donc chaque cycle est indépendant ;
* la durée pour tomber sur la sortie une première fois est la même que la longueur du cycle, donc tous les cycles commencent au même point dans le temps : 0.
Ex: A -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z
Le cycle fait n de long, n est un nombre entier de fois le programme exécuté (n divisible par 269), et démarrer en A est équivalent à démarrer en Z.
Ça simplifie à mort, puisqu'en pratique il ne reste plus qu'à calculer le PPCM des longueurs de cycles.
Si ça n'avait pas été le cas, les cycles auraient été beaucoup plus longs, mais toujours inférieurs à 169*750 = 201750, ce qui se calcule vite.
Par contre on aurait pu avoir des périodes de démarrage où on parcours quelques zones, avant de « tomber » sur un cycle, et de rester dedans, ils auraient pu ne pas commencer au même moment.
Et là le PPCM des cycles ne permet que d'avoir la longueur du super-cycle de l'ensemble des 6 fantômes, mais pas le moment où ils se trouvent tous sur une sortie en même temps.
Ce qui pourrait ne jamais arriver, et c'est probablement pour ça que le problème est « aussi simple », ça aurait peut-être été trop difficile de s'assurer qu'il y ait une solution, et que cette solution soit effectivement calculable rapidement ?
J'ai pas d'idée géniale, là tout de suite, sur comment résoudre ce problème là, mais la force brute n'est pas une solution, mon propre super-cycle faisant presque 12000 milliards, la solution on va pas tomber dessus par hasard.
J'ai failli tenter de résoudre le gros problème, mais heureusement j'ai d'abord regardé mes cycles, et la simplicité m'a fait prendre le raccourci d'un PPCM multiple vite fait.
PS: ça me rappelle une histoire de Tetris l'année dernière, avec des cycles de dingue et beaucoup de méninges triturées :)