Sans surprise, j'ai fait quelque chose de similaire, mais ce sont surtout les pièges qui étaient intéressants à relever.
Première partie
En premier lieu, si on raisonne en termes de tachyons et pas de chemins entiers, il faut résister à l'envie de travailler « en profondeur d'abord ». Il est tentant de dépiler un tachyon d'une pile, d'en ré-empiler deux juste derrière s'il traverse un splitter, et de refaire un tour de boucle tant que la pile n'est pas vide. Seulement, cela nous empêche de détecter la coalescence des tachyons émis simultanément à une même position (par deux splitters distincts distants d'exactement deux positions horizontales).
Ensuite, la question était en fait « combien de fois le rayon a-t-il été divisé ? ». La subtilité était que si un tachyon voyage d'une position à l'autre, le « rayon », lui, est considéré unique du point de départ à celui d'arrivée. Et cela a de l'importance parce si deux tachyons se retrouvant à la même position s'écrasent mutuellement pour n'en former qu'un seul, ils peuvent aussi se suivre et faire en sorte qu'un même splitter soit franchi plusieurs fois.
Par conséquent, puisque seul un splitter peut diviser un rayon, il fallait penser à faire le bilan du nombre de splitters atteints au moins une fois et pas seulement incrémenter un compteur chaque fois que l'on en franchit un.
C'est important parce que j'obtiens respectivement 21 et 22 cas avec les données d'exemple, mais 13245 et 1607 avec les données réelles, ce qui est très différent... le premier nombre dépassant largement celui des splitters en jeu.
Deuxième partie
La tentation était grande d'écrire directement une fonction récursive et de la lancer à partir du point de départ. Bien sûr, comme chaque année, on fait face à une explosion combinatoire et c'est une bonne chose ici (c'est aussi l'un des rares intérêts à utiliser des langages lents).
D'abord, il était tentant également d'écrire quelque chose comme :
if splitter:
return fn((x-1,y)) + fn((x+1,y)
else:
return fn((x,y+1))
... en particulier parce que c'est propre et concis, mais cela encombre quand même la pile sur un trajet en ligne droite pour rien et il ne faut pas attendre ici du langage qu'il détecte et optimise automatiquement la récursivité terminale, donc il était intéressant de mettre une boucle quand même.
Ensuite, la solution consiste surtout à ne pas recalculer plusieurs fois ce qui est déjà long à obtenir, donc à associer à chaque splitter le nombre de chemins qui en dérivent dès qu'on l'obtient et le renvoyer directement si on repasse dessus par la suite.
Ce qui donne de mon côté (en faisant abstraction des inits) :
hit_splitters = {}
# Fonction récursive
def number_of_ways(tachyon):
x,y = tachyon
while True:
tachyon = (x,y)
if not ((0 <= x < width) and (0 <= y)):
return 0
if y >= height:
return 1
c = split_map[y][x]
if c == "^":
if tachyon not in hit_splitters:
hit_splitters[tachyon] = number_of_ways((x-1,y)) \
+ number_of_ways((x+1,y))
return hit_splitters[tachyon]
if c not in ".S":
print("Unknown character:", c)
raise("Unknown character")
y += 1
# Lancement des parcours
total = number_of_ways(point_de_depart)
print("Splitters atteints :", len(hit_splitters))
print(" Total des chemins :", total)
Avec deux petites remarques :
la décomposition « x,y = tachyon » m'a conduit à une petite erreur d'inattention : lors de la rencontre avec un splitter, j'utilise la variable tachyon comme index pour hit_splitters mais à cause de la boucle décrite plus tôt, j'avais oublié qu'elle n'était plus forcément à jour. Donc j'enregistrais les points de départ de chaque tachyon et pas la position des splitters...
J'ai l'habitude d'écrire le total final après toutes les autres sorties mais dans ce cas précis, j'appelais la fonction directement depuis le print. Je ne comprenais donc pas pourquoi le nombre de splitters atteints, donné juste avant, était toujours nul... :-)
Ce sont des broutilles, bien sûr, mais ça montre à quel point une erreur légère peut devenir critique en environnement sensible, aéronautique ou nucléaire par exemple, même lorsque l'on a de la pratique et que l'on porte du soin à son algorithme principal, et pourquoi les méthodes formelles et preuves de programmes sont utiles dans ce type de situation.
C'est une des choses que j'aime le plus dans l'AoC. Même quand les exercices sont « simples », on reçoit régulièrement ce genre de piqûre de rappel alors qu'il est plus difficile d'y être confronté en contexte professionnel.
[^] # Re: Jour 7
Posté par Obsidian . En réponse au journal Advent of Code 2025. Évalué à 2.
Sans surprise, j'ai fait quelque chose de similaire, mais ce sont surtout les pièges qui étaient intéressants à relever.
Première partie
En premier lieu, si on raisonne en termes de tachyons et pas de chemins entiers, il faut résister à l'envie de travailler « en profondeur d'abord ». Il est tentant de dépiler un tachyon d'une pile, d'en ré-empiler deux juste derrière s'il traverse un splitter, et de refaire un tour de boucle tant que la pile n'est pas vide. Seulement, cela nous empêche de détecter la coalescence des tachyons émis simultanément à une même position (par deux splitters distincts distants d'exactement deux positions horizontales).
Ensuite, la question était en fait « combien de fois le rayon a-t-il été divisé ? ». La subtilité était que si un tachyon voyage d'une position à l'autre, le « rayon », lui, est considéré unique du point de départ à celui d'arrivée. Et cela a de l'importance parce si deux tachyons se retrouvant à la même position s'écrasent mutuellement pour n'en former qu'un seul, ils peuvent aussi se suivre et faire en sorte qu'un même splitter soit franchi plusieurs fois.
Par conséquent, puisque seul un splitter peut diviser un rayon, il fallait penser à faire le bilan du nombre de splitters atteints au moins une fois et pas seulement incrémenter un compteur chaque fois que l'on en franchit un.
C'est important parce que j'obtiens respectivement 21 et 22 cas avec les données d'exemple, mais 13245 et 1607 avec les données réelles, ce qui est très différent... le premier nombre dépassant largement celui des splitters en jeu.
Deuxième partie
La tentation était grande d'écrire directement une fonction récursive et de la lancer à partir du point de départ. Bien sûr, comme chaque année, on fait face à une explosion combinatoire et c'est une bonne chose ici (c'est aussi l'un des rares intérêts à utiliser des langages lents).
D'abord, il était tentant également d'écrire quelque chose comme :
if splitter:
return fn((x-1,y)) + fn((x+1,y)
else:
return fn((x,y+1))
... en particulier parce que c'est propre et concis, mais cela encombre quand même la pile sur un trajet en ligne droite pour rien et il ne faut pas attendre ici du langage qu'il détecte et optimise automatiquement la récursivité terminale, donc il était intéressant de mettre une boucle quand même.
Ensuite, la solution consiste surtout à ne pas recalculer plusieurs fois ce qui est déjà long à obtenir, donc à associer à chaque splitter le nombre de chemins qui en dérivent dès qu'on l'obtient et le renvoyer directement si on repasse dessus par la suite.
Ce qui donne de mon côté (en faisant abstraction des inits) :
Avec deux petites remarques :
x,y = tachyon» m'a conduit à une petite erreur d'inattention : lors de la rencontre avec un splitter, j'utilise la variable tachyon comme index pour hit_splitters mais à cause de la boucle décrite plus tôt, j'avais oublié qu'elle n'était plus forcément à jour. Donc j'enregistrais les points de départ de chaque tachyon et pas la position des splitters...Ce sont des broutilles, bien sûr, mais ça montre à quel point une erreur légère peut devenir critique en environnement sensible, aéronautique ou nucléaire par exemple, même lorsque l'on a de la pratique et que l'on porte du soin à son algorithme principal, et pourquoi les méthodes formelles et preuves de programmes sont utiles dans ce type de situation.
C'est une des choses que j'aime le plus dans l'AoC. Même quand les exercices sont « simples », on reçoit régulièrement ce genre de piqûre de rappel alors qu'il est plus difficile d'y être confronté en contexte professionnel.