Aujourd'hui, j'ai pas trouvé de manière maligne de faire la partie 2.
Du coup, brute-force.
Pour chaque sommet u du chemin, je regarde tous les sommets v à distance au plus 20 et je teste si dist[u] <= dist[v] - 100 - manhattan(u, v). Si c'est le cas, j'incrémente le compteur représentant le nombre de cheats.
Une remarque cependant: le graphe de la grille est juste un chemin entre S et E.
Du coup, ça simplifie le calcul des distances. Pas besoin de BFS, DFS ou Dijkstra.
On part de S et on suit le chemin jusqu'à arriver à E.
Pour la partie 2, j'ai parallélisé en utilisant des threads. 640 microsecondes (et 4ms en séquentiel). Mon plus long temps d'exécution de cet AOC 2024 pour l'instant.
Jusqu'à présent, je suis un peu déçu de cet AOC par rapport aux années précédentes.
A quelques exceptions, tous les problèmes peuvent se résoudre par brute-force. J'ai l'impression que c'était moins le cas dans les années précédentes.
# 20ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 2.
Aujourd'hui, j'ai pas trouvé de manière maligne de faire la partie 2.
Du coup, brute-force.
Pour chaque sommet
udu chemin, je regarde tous les sommetsvà distance au plus 20 et je teste sidist[u] <= dist[v] - 100 - manhattan(u, v). Si c'est le cas, j'incrémente le compteur représentant le nombre de cheats.Une remarque cependant: le graphe de la grille est juste un chemin entre S et E.
Du coup, ça simplifie le calcul des distances. Pas besoin de BFS, DFS ou Dijkstra.
On part de S et on suit le chemin jusqu'à arriver à E.
Pour la partie 2, j'ai parallélisé en utilisant des threads. 640 microsecondes (et 4ms en séquentiel). Mon plus long temps d'exécution de cet AOC 2024 pour l'instant.
Jusqu'à présent, je suis un peu déçu de cet AOC par rapport aux années précédentes.
A quelques exceptions, tous les problèmes peuvent se résoudre par brute-force. J'ai l'impression que c'était moins le cas dans les années précédentes.