En consultant d'autres forums, je suis tombé sur une idée que j'ai trouvé astucieuse et élégante.
L'idée est que la position horizontale des robots cycle chaque 101 secondes et celle verticale chaque 103 secondes.
Donc, le nombre de robots par colonne est le même pour deux instants qui ont le même module 101.
De même , le nombre de robots par ligne est le même pour deux instants qui ont le même modulo 103.
Si on peut détecter si un instant t fait apparaître l'image juste en consultant le nombre de robots par ligne ou juste le nombre de robots par colonne alors il suffit de faire ce test seulement pour les instants de 0 à 101 (pour les colonnes) et de 0 à 103 (pour les lignes).
A partir de ça, on est capable d'extrapoler le moment t où l'image apparaît en utilisant le théorème des restes chinois.
Plus précisément, notons t le moment où l'image apparait
si t1 est le moment entre 0 et 101 qui a le même modulo 101 que t
et t2 est le moment entre 0 et 103 qui a le même modulo 103 que t.
Alors t = (t1 * 51 * 103 + t2 * 51 * 101) % (101 * 103)
Pour tester si l'image apparaît en regardant les colonnes, j'ai vu plusieurs approches notamment calculer la variance mais c'est un peu long à calculer.
J'ai essayé de calculer la somme des carrés des nombres de robots qui apparaissent sur chaque colonne mais c'est également un peu long à calculer.
Finalement, j'ai utilisé l'approche suivante.
Je divise mes colonnes en 4 parties Q1 | Q2 | Q3 | Q4 et comme l'image est assez dense et qu'elle fait moins de la moitié des colonnes, j'en déduis que le nombre de robots dans Q1 ou dans Q4 sera assez faible. Donc, je cherche l'instant t entre 0 et 101 qui minimise ce nombre.
Je fais de même pour les lignes.
[^] # Re: 14ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 1.
En consultant d'autres forums, je suis tombé sur une idée que j'ai trouvé astucieuse et élégante.
L'idée est que la position horizontale des robots cycle chaque 101 secondes et celle verticale chaque 103 secondes.
Donc, le nombre de robots par colonne est le même pour deux instants qui ont le même module 101.
De même , le nombre de robots par ligne est le même pour deux instants qui ont le même modulo 103.
Si on peut détecter si un instant t fait apparaître l'image juste en consultant le nombre de robots par ligne ou juste le nombre de robots par colonne alors il suffit de faire ce test seulement pour les instants de 0 à 101 (pour les colonnes) et de 0 à 103 (pour les lignes).
A partir de ça, on est capable d'extrapoler le moment t où l'image apparaît en utilisant le théorème des restes chinois.
Plus précisément, notons t le moment où l'image apparait
si t1 est le moment entre 0 et 101 qui a le même modulo 101 que t
et t2 est le moment entre 0 et 103 qui a le même modulo 103 que t.
Alors
t = (t1 * 51 * 103 + t2 * 51 * 101) % (101 * 103)Pour tester si l'image apparaît en regardant les colonnes, j'ai vu plusieurs approches notamment calculer la variance mais c'est un peu long à calculer.
J'ai essayé de calculer la somme des carrés des nombres de robots qui apparaissent sur chaque colonne mais c'est également un peu long à calculer.
Finalement, j'ai utilisé l'approche suivante.
Je divise mes colonnes en 4 parties Q1 | Q2 | Q3 | Q4 et comme l'image est assez dense et qu'elle fait moins de la moitié des colonnes, j'en déduis que le nombre de robots dans Q1 ou dans Q4 sera assez faible. Donc, je cherche l'instant t entre 0 et 101 qui minimise ce nombre.
Je fais de même pour les lignes.
50 microsecondes pour mon implémentation.