Posté par Guillaume.B .
En réponse au journal Advent of code 2024.
Évalué à 1.
Dernière modification le 18 décembre 2024 à 15:32.
La première était un juste un parcours en largeur classique.
Pour la seconde partie, j'ai plusieurs idées de plus en plus efficaces.
l'approche brute-force. Tester pour tous les moments t si on peut trouver un chemin alors que es t premiers bytes sont tombés. Ca fonctionne mais c'est assez long.
l'approche recherche binaire/dichotomique. On part d'un intervalle [0, nombre de bytes], on teste pour la valeur au milieu de l'intervalle et on divise à l'intervalle par deux à chaque itération.
Ca donne un algorithme en temps O(N log M) où N est la taille de la grille et M le nombre de bytes. 70 microsecondes pour mon implémentation.
l'approche union-find. On part de la grille complètement remplie par les bytes. On calcule les composantes connexes. On retire progressivement les bytes dans le sens inverse et on met à jour les composantes en utilisant une structure union-find. https://fr.wikipedia.org/wiki/Union-find
30 microsecondes pour mon implémentation.
La dernière approche consiste encore de partir de la grille complètement remplie par les bytes et de retirer progressivement les bytes dans le sens inverse.
Sauf que cette fois ci, on va faire un parcours en profondeur depuis le sommet de départ, noter les sommets visités.
Pour chaque byte (dans le sens inverse), si celui est adjacent à au moins un sommet déjà visité, on reprend le parcours en profondeur à partir de la position du byte en gardant les sommets déjà visités. On s'arrête dès que le sommet final est visité.
Ca donne un algorithme en temps linéaire.
14 microsecondes pour mon implémentation.
# 18ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 1. Dernière modification le 18 décembre 2024 à 15:32.
La première était un juste un parcours en largeur classique.
Pour la seconde partie, j'ai plusieurs idées de plus en plus efficaces.
l'approche brute-force. Tester pour tous les moments t si on peut trouver un chemin alors que es t premiers bytes sont tombés. Ca fonctionne mais c'est assez long.
l'approche recherche binaire/dichotomique. On part d'un intervalle
[0, nombre de bytes], on teste pour la valeur au milieu de l'intervalle et on divise à l'intervalle par deux à chaque itération.Ca donne un algorithme en temps
O(N log M)où N est la taille de la grille et M le nombre de bytes. 70 microsecondes pour mon implémentation.l'approche union-find. On part de la grille complètement remplie par les bytes. On calcule les composantes connexes. On retire progressivement les bytes dans le sens inverse et on met à jour les composantes en utilisant une structure union-find.
https://fr.wikipedia.org/wiki/Union-find
30 microsecondes pour mon implémentation.
La dernière approche consiste encore de partir de la grille complètement remplie par les bytes et de retirer progressivement les bytes dans le sens inverse.
Sauf que cette fois ci, on va faire un parcours en profondeur depuis le sommet de départ, noter les sommets visités.
Pour chaque byte (dans le sens inverse), si celui est adjacent à au moins un sommet déjà visité, on reprend le parcours en profondeur à partir de la position du byte en gardant les sommets déjà visités. On s'arrête dès que le sommet final est visité.
Ca donne un algorithme en temps linéaire.
14 microsecondes pour mon implémentation.