Et la solution, enfin, nous apparaît avec un mélange de brutalité et de finesse.
On reprend où on en était quand on croyait avoir raison : on vient de reboucler sur un état (n°block, n°instruction).
On compare avec un éventuel hash et snapshot enregistré pour cet état. La première fois qu'on boucle : on n'en a pas.
Donc on prend une photo, c'est à dire l'état du terrain sur l'ensemble des lignes qui forment le cycle potentiel, et uniquement elles (en gros : str(board[-(hauteur actuelle - hauteur d'avant):]).
On calcule le hash de cette photo pour comparer plus vite.
On stocke ces deux valeurs dans deux tableaux.
On continue, et maintenant on va revenir une troisième fois sur le même état ! Sauf que là on a un hash et une photo, on compare.
Si c'est différent, on remplace et on poursuit.
Si c'est identique, on valide en comparant la photo complète hein, faudrait pas planter sur une peu probable collision, et on a enfin trouvé un vrai cycle authentique et prouvé par une photo certifiée, avec signature !
On reprend l'algo là où on en était.
Et on constate que le premier vrai cycle commence au bloc 59 (!?!?! Mais... Pourquoi si peu ?), avec un cycle de 1705 blocs.
On a trouvé deux cycles rigoureusement identiques, le premier de 60 à 1764 et le second de 1765 à 3469.
Ils ont une hauteur de 2649 lignes, et on a donc comparé deux blocs de 2649 lignes de Tetris qui se suivent, et ils étaient rigoureusement identiques, et chacun des deux commence avec le même bloc à la même instruction. On cycle, c'est acquis.
La zone début + 2 cycles + fin fait toujours 4995 blocs, on ne simule pas un bloc de plus.
Et on a toujours un résultat valide, mais là on en est sûrs.
[^] # Re: Le Jour du Tetris
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 17. Évalué à 2.
Et la solution, enfin, nous apparaît avec un mélange de brutalité et de finesse.
On reprend où on en était quand on croyait avoir raison : on vient de reboucler sur un état
(n°block, n°instruction).On compare avec un éventuel hash et snapshot enregistré pour cet état. La première fois qu'on boucle : on n'en a pas.
Donc on prend une photo, c'est à dire l'état du terrain sur l'ensemble des lignes qui forment le cycle potentiel, et uniquement elles (en gros :
str(board[-(hauteur actuelle - hauteur d'avant):]).On calcule le hash de cette photo pour comparer plus vite.
On stocke ces deux valeurs dans deux tableaux.
On continue, et maintenant on va revenir une troisième fois sur le même état ! Sauf que là on a un hash et une photo, on compare.
Si c'est différent, on remplace et on poursuit.
Si c'est identique, on valide en comparant la photo complète hein, faudrait pas planter sur une peu probable collision, et on a enfin trouvé un vrai cycle authentique et prouvé par une photo certifiée, avec signature !
On reprend l'algo là où on en était.
Et on constate que le premier vrai cycle commence au bloc 59 (!?!?! Mais... Pourquoi si peu ?), avec un cycle de 1705 blocs.
On a trouvé deux cycles rigoureusement identiques, le premier de 60 à 1764 et le second de 1765 à 3469.
Ils ont une hauteur de 2649 lignes, et on a donc comparé deux blocs de 2649 lignes de Tetris qui se suivent, et ils étaient rigoureusement identiques, et chacun des deux commence avec le même bloc à la même instruction. On cycle, c'est acquis.
La zone début + 2 cycles + fin fait toujours 4995 blocs, on ne simule pas un bloc de plus.
Et on a toujours un résultat valide, mais là on en est sûrs.
PS : Je nettoie un peu le code et je poste ça...