Mon défi était d'avoir un temps d'exécution inférieur à 1ms.
Première approche, on calcule toutes les paires de sommets et leur distance euclidienne (en fait, on a pas besoin de faire la racine carrée qui est coûteuse en temps).
Ensuite, on fait un algorithme similaire à Kruskal. https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
On utilise une structure union-find https://fr.wikipedia.org/wiki/Union-find
et on rajoute progressivement chaque arête en faisant un join sur les deux extrémités de l'arête. Pour la partie 2, on a besoin de trier les arêtes ce qui est vraiment le goulot d'étranglement de l'algo. Pour la partie 1, on a juste besoin de garantir que les 1000 premières arêtes aient la distance euclidienne la plus petite. En Rust, cela peut être fait avec la méthode select_unstable(1000) et c'est beaucoup plus efficace que trier le tableau. Avec cette approche, 2ms pour la partie 1 et 15ms pour la partie 2.
Deuxième approche uniquement pour la partie 2.
On cherche un arbre couvrant de poids minimum mais cette fois, au lieu de se baser sur Kruskal qui est en temps O(m log n) = O(n2 log n) comme le graphe est dense, on se base sur l'algorithme de Prim qui est en temps O(n2).https://fr.wikipedia.org/wiki/Algorithme_de_Prim
Du coup, on réduit le temps à 3ms.
Dernière approche, on revient sur Kruskal mais cette fois, on ne va pas considérer toutes les arêtes.
On va diviser l'espace en blocs 8x8x8 et pour chaque sommet, on va regarder les sommets qui sont dans le même bloc ou dans un bloc voisin (diagonal compris).
On passe de (1000*999) / 2 ~ 500_000 paires d'arêtes à environ 10000.
En appliquant le même principe que la première méthode, on obtient un temps d'exécution de 650 microsecondes pour les deux parties.
Ca ne marche pas tout le temps, il ne faut pas qu'il y ait de gros trous dans l'espace de points mais ça semble être le cas dans les différentes inputs car les points sont uniformément répartis.
[^] # Re: Jour 8
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 3.
J'ai trouvé ce problème assez intéressant.
Mon défi était d'avoir un temps d'exécution inférieur à 1ms.
Première approche, on calcule toutes les paires de sommets et leur distance euclidienne (en fait, on a pas besoin de faire la racine carrée qui est coûteuse en temps).
Ensuite, on fait un algorithme similaire à Kruskal.
https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
On utilise une structure union-find
https://fr.wikipedia.org/wiki/Union-find
et on rajoute progressivement chaque arête en faisant un join sur les deux extrémités de l'arête. Pour la partie 2, on a besoin de trier les arêtes ce qui est vraiment le goulot d'étranglement de l'algo. Pour la partie 1, on a juste besoin de garantir que les 1000 premières arêtes aient la distance euclidienne la plus petite. En Rust, cela peut être fait avec la méthode
select_unstable(1000)et c'est beaucoup plus efficace que trier le tableau. Avec cette approche, 2ms pour la partie 1 et 15ms pour la partie 2.Deuxième approche uniquement pour la partie 2.
On cherche un arbre couvrant de poids minimum mais cette fois, au lieu de se baser sur Kruskal qui est en temps
O(m log n) = O(n2 log n)comme le graphe est dense, on se base sur l'algorithme de Prim qui est en tempsO(n2).https://fr.wikipedia.org/wiki/Algorithme_de_PrimDu coup, on réduit le temps à 3ms.
Dernière approche, on revient sur Kruskal mais cette fois, on ne va pas considérer toutes les arêtes.
On va diviser l'espace en blocs 8x8x8 et pour chaque sommet, on va regarder les sommets qui sont dans le même bloc ou dans un bloc voisin (diagonal compris).
On passe de
(1000*999) / 2 ~ 500_000paires d'arêtes à environ 10000.En appliquant le même principe que la première méthode, on obtient un temps d'exécution de 650 microsecondes pour les deux parties.
Ca ne marche pas tout le temps, il ne faut pas qu'il y ait de gros trous dans l'espace de points mais ça semble être le cas dans les différentes inputs car les points sont uniformément répartis.