Suite à mes messages précédents, j'ai avancé dans la résolution efficace du problème, mais en réalité pas terminé.
Mon idée c'était qu'on cycle dès qu'on revient à un couple (n°block, n°instruction) qui est déjà passé, n°block c'est de 1 à 5, et n°instruction de 0 à 10091 chez moi (taille des données en entrée), et 0 à 39 pour les données de test.
Comme si ce seul état était déterministe, et que l'état du terrain n'entrait pas en ligne de compte.
Fourbement, ça suffit avec les données de test.
L'idée donc c'est générer des blocs en enregistrant à chaque itération la hauteur, on en aura besoin de quelques-unes à la fin.
Mais aussi on enregistre l'historique de l'état (n°block, n°instruction) et l'itération où elle s'est produite.
Dès qu'on a le sentiment de cycler, c'est à dire que notre état est déjà passé, on note l'itération où ça s'est produit la première fois, et la seconde.
La différence c'est la durée de notre cycle.
On a donc :
la base non cyclique ;
la durée d'un cycle ;
la portion finale : (10**12-base)//cycle ;
le nombre de cycle complet à inclure : (10**12-base)%cycle ;
la hauteur ajoutée par un cycle hauteur[base+cycle] - hauteur[base] ;
En données de test ça fait une base de 14 blocs, un cycle de 35, une hauteur par cycle de 53.
Là on va simuler une tour complète en enlevant un maximum de cycles entiers au milieu, soit une hauteur de base + 2 cycles + fin, parce que avec un seul cycle on a des effets de bords.
Et on continue si nécessaire jusqu'à une hauteur de 2022 pour le premier exercice.
Là on a la hauteur à 2022, la hauteur ajoutée par un cycle, et la hauteur des extrémités avec deux cycles, on multiplie, on ajoute, on mélange à la bave de crapaud et hop, 1514285714288 sur les données de test.
En données réelles j'ai ce résultat :
Base de 39 blocs (?!?), cycle de 1725 (mais non c'est 1705 !!), et score final de 1555942028979 au lieu de 1553665689155.
L'idée est bonne, mais la réalisation craint un peu, la supposition de départ est fausse, je rappelle :
Comme si ce seul état était déterministe, et que l'état du terrain n'entrait pas en ligne de compte.
En pratique, je stocke comme état (n°block, n°instruction, représentation des X dernières lignes du terrain).
Et avec 995 lignes, j'atteins la vraie stabilité, la vraie base non cyclique, même si 14 suffisent pour trouver le résultat avec mes données.
Donc encore un peu de travail pour trouver vraiment le résultat sans le connaître à l'avance.
Par contre une unique construction de tour de 4995 blocs !
# Le Jour du Tetris
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 17. Évalué à 2.
Suite à mes messages précédents, j'ai avancé dans la résolution efficace du problème, mais en réalité pas terminé.
Mon idée c'était qu'on cycle dès qu'on revient à un couple
(n°block, n°instruction)qui est déjà passé, n°block c'est de 1 à 5, et n°instruction de 0 à 10091 chez moi (taille des données en entrée), et 0 à 39 pour les données de test.Comme si ce seul état était déterministe, et que l'état du terrain n'entrait pas en ligne de compte.
Fourbement, ça suffit avec les données de test.
L'idée donc c'est générer des blocs en enregistrant à chaque itération la hauteur, on en aura besoin de quelques-unes à la fin.
Mais aussi on enregistre l'historique de l'état
(n°block, n°instruction)et l'itération où elle s'est produite.Dès qu'on a le sentiment de cycler, c'est à dire que notre état est déjà passé, on note l'itération où ça s'est produit la première fois, et la seconde.
La différence c'est la durée de notre cycle.
On a donc :
(10**12-base)//cycle;(10**12-base)%cycle;En données de test ça fait une base de 14 blocs, un cycle de 35, une hauteur par cycle de 53.
Là on va simuler une tour complète en enlevant un maximum de cycles entiers au milieu, soit une hauteur de
base + 2 cycles + fin, parce que avec un seul cycle on a des effets de bords.Et on continue si nécessaire jusqu'à une hauteur de 2022 pour le premier exercice.
Là on a la hauteur à 2022, la hauteur ajoutée par un cycle, et la hauteur des extrémités avec deux cycles, on multiplie, on ajoute, on mélange à la bave de crapaud et hop, 1514285714288 sur les données de test.
En données réelles j'ai ce résultat :
Base de 39 blocs (?!?), cycle de 1725 (mais non c'est 1705 !!), et score final de 1555942028979 au lieu de 1553665689155.
L'idée est bonne, mais la réalisation craint un peu, la supposition de départ est fausse, je rappelle :
En pratique, je stocke comme état
(n°block, n°instruction, représentation des X dernières lignes du terrain).Et avec 995 lignes, j'atteins la vraie stabilité, la vraie base non cyclique, même si 14 suffisent pour trouver le résultat avec mes données.
Donc encore un peu de travail pour trouver vraiment le résultat sans le connaître à l'avance.
Par contre une unique construction de tour de 4995 blocs !