La partie 1 est assez facile car on peut calculer directement la position d'un robot à 100ème seconde sans avoir à calculer les précédentes secondes.
La partie 2 n'est pas très claire et il faut d'abord visualiser l'image.
En discutant un peu, il y a plein de manières différentes de détecter cette image mais pour ma part, j'ai utilisé l'heuristique suivante.
J'ai cherché le premier moment où toutes les positions de robots étaient distinctes.
Pour cela, j'ai utilisé un tableau grid de tailles 101x103 et pour savoir si les positions sont distinctes à la seconde i, je regarde pour chaque position (px, py) de robots, si grid[px*101+py] == i. Si c'est le cas, j'ai deux positions non distinctes.
Sinon, j'affecte grid[px*101+py] = i.
L'avantage de cette méthode est que je peux réutiliser mon tableau à chaque itération sans avoir à le réinitialiser ou en créer un autre.
J'ai également parallélisé le processus avec des threads.
Un thread va travailler sur un segment de 20 secondes. Si il trouve une solution, on s'arrête. Sinon, il va travailler sur le prochain segment de 20 secondes pas encore attribué à un thread.
# 14ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 3.
La partie 1 est assez facile car on peut calculer directement la position d'un robot à 100ème seconde sans avoir à calculer les précédentes secondes.
La partie 2 n'est pas très claire et il faut d'abord visualiser l'image.
En discutant un peu, il y a plein de manières différentes de détecter cette image mais pour ma part, j'ai utilisé l'heuristique suivante.
J'ai cherché le premier moment où toutes les positions de robots étaient distinctes.
Pour cela, j'ai utilisé un tableau
gridde tailles 101x103 et pour savoir si les positions sont distinctes à la seconde i, je regarde pour chaque position (px, py) de robots, sigrid[px*101+py] == i. Si c'est le cas, j'ai deux positions non distinctes.Sinon, j'affecte
grid[px*101+py] = i.L'avantage de cette méthode est que je peux réutiliser mon tableau à chaque itération sans avoir à le réinitialiser ou en créer un autre.
J'ai également parallélisé le processus avec des threads.
Un thread va travailler sur un segment de 20 secondes. Si il trouve une solution, on s'arrête. Sinon, il va travailler sur le prochain segment de 20 secondes pas encore attribué à un thread.
440 microsecondes pour les deux parties.