Posté par Yth (Mastodon) .
En réponse au message Avent du Code, jour 17.
Évalué à 2.
Dernière modification le 17 décembre 2022 à 19:23.
C'est plus compliqué que ça a priori.
Je n'ai pas de méthode de calcul du cycle, je le mesure en prenant des bornes assez grandes.
On a plusieurs problèmes :
Trouver en combien de blocs on cycle, c'est à dire qu'en partant de l'ajout du premier bloc avec la première instruction, on revient à l'ajout du premier bloc avec la première instruction. Dans mon cas c'est en 1705 blocs, dans les données de test c'est en 35 blocs.
Constater que le début de partie ne correspond pas du tout à un cycle répétitif, la situation est particulière, et le premier cycle commence... plus tard. Sur mes données il faut passer quelque chose entre 200 et 300 blocs pour démarrer le premier cycle.
mesurer la hauteur ajoutée par un cycle complet normal en milieu de tour (donc pas le début, pas la fin).
Et mesurer la fin, en haut, soit mille milliards modulo le cycle.
En pratique, il suffit de faire une tour de deux cycles plus la fin, on a un cycle normal et complet au milieu, donc on sait qu'on peut en rajouter autant qu'on veut, ça agrandira linéairement.
Le principe c'est ça, avec la fonction simulation() qui fait une simulation (ouais ouais ! Promis !), en paramètres les data, et le nombre de blocs à faire tomber. Elle retourne la hauteur finale. L'exercice 1 c'est l'appel avec 2022 blocs, et voilà.
Cas particulier, si je fournis un 3è paramètre, je laisse passer ce nombre de blocs, et je prend l'état (n° de bloc, n° d'instruction), et dès que je retrouve le même état, j'ai mon cycle, je sors la valeur !
Après on mesure, on calcule, ça marche.
data=sys.stdin.read().strip()h1=simulation(data,2022)print(f"Height of 2022 blocks: {h1}")# Finding cycle length, knowing this limits would be enoughcycle=simulation(data,1000000,2000)repeat,remain=divmod(1000000000000,cycle)# Measuring 1 cycle, and 2 cycles, to determine what is the height added by one cycle in the middle.h1c=simulation(data,cycle)h2c=simulation(data,cycle*2)# All extremities with full cycle in the middle# We can add any number of full cycles in the middle of this simulation, they'll add a fixed height.hr=simulation(data,cycle*2+remain)total=(h2c-h1c)*(repeat-2)+hrprint(f"Cycle of {cycle} blocks, 1 Cycle {h1c}, 2 Cycles {h2c}, Cycle height {h2c-h1c}, Extremities height {hr}")print(f"Total Height = {total}")
Yth, comme prévu le samedi, j'ai moins de temps, commencé tard, mais c'était pas trop long...
[^] # Re: Tetris style
Posté par Yth (Mastodon) . En réponse au message Avent du Code, jour 17. Évalué à 2. Dernière modification le 17 décembre 2022 à 19:23.
C'est plus compliqué que ça a priori.
Je n'ai pas de méthode de calcul du cycle, je le mesure en prenant des bornes assez grandes.
On a plusieurs problèmes :
En pratique, il suffit de faire une tour de deux cycles plus la fin, on a un cycle normal et complet au milieu, donc on sait qu'on peut en rajouter autant qu'on veut, ça agrandira linéairement.
Le principe c'est ça, avec la fonction
simulation()qui fait une simulation (ouais ouais ! Promis !), en paramètres lesdata, et le nombre de blocs à faire tomber. Elle retourne la hauteur finale. L'exercice 1 c'est l'appel avec 2022 blocs, et voilà.Cas particulier, si je fournis un 3è paramètre, je laisse passer ce nombre de blocs, et je prend l'état (n° de bloc, n° d'instruction), et dès que je retrouve le même état, j'ai mon cycle, je sors la valeur !
Après on mesure, on calcule, ça marche.