Posté par steph1978 .
En réponse au journal Advent of Code 2025.
Évalué à 2.
Dernière modification le 11 décembre 2025 à 16:16.
Bonne tranche de rigolade aujourd'hui. On est sur du parcours de graphes.
Première partie implémentée en deux minutes, sans erreurs, directement sur l'input et hop une étoile. On commence à être rôdé.
Partie deux, sur ce bon élan, j'adapte ma solution pour partir d'un autre nœud et ne compter que les chemins qui contiennent les nœuds imposés. Trivial. Je vais faire la journée 11 en moins de dix minutes.
Sauf que le script ne me rend pas la main. Et là, je me dis que je me suis fait avoir.
Je trace le graphe avec Graphviz et je vois l'étendue des dégâts. Le nœud de départ de la première partie est tout près du nœud de sortie. Mais pour la seconde partie, il est très très loin. Donc la combinatoire explose.
Je tente une mise en cache, mais ça ne semble rien améliorer.
J'ai donc exploité la structure du graphe proposé qui 1/ est acyclique, 2/ présente des "couches". J'ai donc calculé un graph plus simple avec seulement les nœuds qui matérialisent les couches et le cout pour passer de l'un à l'autre. Puis lancé le calcul du nombre de chemins sur ce graphe plus simple (18 nœuds versus 644).
Forcément, ça m'a pris une bonne paire d'heures.
Je ne sais pas s'il y avait plus malin à faire ; je lirai avec plaisir d'autres solutions.
# Jour 11
Posté par steph1978 . En réponse au journal Advent of Code 2025. Évalué à 2. Dernière modification le 11 décembre 2025 à 16:16.
Bonne tranche de rigolade aujourd'hui. On est sur du parcours de graphes.
Première partie implémentée en deux minutes, sans erreurs, directement sur l'input et hop une étoile. On commence à être rôdé.
Partie deux, sur ce bon élan, j'adapte ma solution pour partir d'un autre nœud et ne compter que les chemins qui contiennent les nœuds imposés. Trivial. Je vais faire la journée 11 en moins de dix minutes.
Sauf que le script ne me rend pas la main. Et là, je me dis que je me suis fait avoir.
Je trace le graphe avec Graphviz et je vois l'étendue des dégâts. Le nœud de départ de la première partie est tout près du nœud de sortie. Mais pour la seconde partie, il est très très loin. Donc la combinatoire explose.
Je tente une mise en cache, mais ça ne semble rien améliorer.
J'ai donc exploité la structure du graphe proposé qui 1/ est acyclique, 2/ présente des "couches". J'ai donc calculé un graph plus simple avec seulement les nœuds qui matérialisent les couches et le cout pour passer de l'un à l'autre. Puis lancé le calcul du nombre de chemins sur ce graphe plus simple (18 nœuds versus 644).
Forcément, ça m'a pris une bonne paire d'heures.
Je ne sais pas s'il y avait plus malin à faire ; je lirai avec plaisir d'autres solutions.