Jour 10, encore

Advent of Code 2025

Adrien Foucart

2025-12-14

Puzzle: https://adventofcode.com/2025/day/10

Je n’ai pas encore baissé les bras. Je suis même, je pense, proche d’une solution. Mais pas encore tout à fait.

J’ai d’abord eu ce que je pensais être un “Eureka” qui s’est avéré un flop. Puis j’ai lu le début d’un post sur Reddit, en m’arrêtant avant de voir l’algorithme complet, mais qui m’a remis sur une voie que j’avais déjà envisagé mais pas assez exploré, et j’ai enfin obtenu une solution.

Malheureusement, ce n’est pas la bonne. Reprenons.

Eureka? Ah, non.

Après le jour 12, je me suis dit que peut-être ici aussi il y avait une simplification à trouver en observant mes vraies données d’input. J’ai donc passé un peu de temps à regarder les définitions de “mes” machines, et je me suis rendu compte que je pouvais déceler certaines tendances. Par exemple, il y avait souvent une dimension avec un nombre beaucoup plus petit à atteindre que les autres. Il semble aussi souvent y avoir un lien entre le fait qu’un nombre à atteindre soit petit, et qu’il y ait peu de boutons qui l’incrémente, ce qui est relativement logique pour que toutes les machines soient solvables.

En regardant une de mes machines simples, je me suis soudain rendu compte que je pouvais la résoudre “de tête”.

[#.#.] (0,3) (2,3) (1) (0,1) {22,119,1,7}

Un seul bouton incrément le compteur 2, qui doit arriver uniquement à 1, donc on sait qu’on doit appuyer une fois – et pas plus – sur le bouton (2, 3). Reste {22, 119, 0, 6}.
Le seul autre bouton qui touche le compteur 3 est le premier. Les 6 incréments restant doivent donc venir de lui. On a donc six poussées sur (0, 3) – et pas plus. Reste {16, 119, 0, 0}.
Le seul bouton restant qui touche au compteur 0 est le dernier bouton. On doit donc appuyer 16 fois sur (0, 1) pour arriver à {0, 103, 0, 0}. Reste 103 poussées sur le bouton (1) pour un total de 103+16+6+1=126 poussées.

Est-ce une procédure générale? J’ai essayé sur quelques machines faciles avec succès. Eureka! Reste à généraliser la procédure:

Trier les compteurs par valeur croissante.
Chercher le(s) bouton(s) qui affectent ce compteur. S’il y en a un seul: pousser autant que possible sur le bouton. S’il y en a plusieurs, privilégier le bouton qui touche un maximum de dimensions (pour minimiser le nombre total de boutons à pousser).
Une fois qu’on a éliminé une dimension: éliminer tous les boutons qui l’affectent.
Continuer jusqu’à arriver au bout!

J’ai codé tout ça, et ça marche… pour quelques machines. Mais la généralisation ne tient pas. J’ai bidouillé dessus quelques temps pour essayer de dompter les cas plus difficiles, sans succès.

De la parité

Quelque chose que j’avais remarqué mais que je ne voyais pas comment utiliser: si on connait le minimum de boutons à pousser pour arriver à une position x⃗ = (x₀, x₁..., x_n), alors cela nous donne aussi le minimum de boutons à pousser pour tous les multiples entiers de cette position, k ⋅ x⃗ = (k ⋅ x₀, ..., k ⋅ x_n).

Puis, en jetant un oeil au subreddit r/adventofcode, je suis tombé sur ce post de /u/tenthmascot. Vu le temps passé sur ce puzzle, je me suis dis qu’il était temps d’accepter un peu d’aide, sans lire tout le détail de sa solution. Mais son TLDR; au début m’a donné ce qu’il me fallait pour décoincer un peu mes idées:

tl;dr: find all possible sets of buttons you can push so that the remaining voltages are even, and divide by 2 and recurse.

Voilà où cette propriété pouvait m’être utile! Si, depuis la position à atteindre, je trouve comment me rendre à une position paire, je sais que le nombre de boutons à pousser pour arriver à cette position est égale au double du nombre de boutons à pousser pour arriver à la demi-position. Depuis la machine que j’ai pris en example toute à l’heure:

(0,3) (2,3) (1) (0,1) {22,119,1,7}
    -> appuyer sur (2, 3) et (1) donne {22, 118, 0, 6} (+ 2 boutons)
    -> diviser par deux donne {11, 59, 0, 3} (2 x boutons)
    -> appuyer sur (0, 3) et (1) donne {10, 58, 0, 2} (+ 2 boutons)
    -> diviser par deux donne {5, 29, 0, 1} (2 x boutons)
    -> appuyer sur (0, 3) et (1) donne {4, 28, 0, 0} (+ 2 boutons)
    -> diviser par deux donne {2, 14, 0, 0} (2 x boutons)
    -> diviser par deux donne {1, 7, 0, 0} (2 x boutons)
    -> appuyer sur (0, 1) donne {0, 6, 0, 0} (+ 1 bouton)
    -> diviser par deux donne {0, 3, 0, 0} (2 x boutons)
    -> appuyer sur (1) donne {0, 2, 0, 0} (+ 1 bouton)
    -> diviser par deux donne {0, 1, 0, 0} (2 x boutons)
    -> appuyer sur (1) donne {0, 0, 0, 0} (+ 1 bouton)

Pour calculer le nombre total, on remonte dans l’autre sens:

+1 -> 1 bouton
x2 -> 2
+1 -> 3
x2 -> 6
+1 -> 7
x2 -> 14
x2 -> 28
+2 -> 30
x2 -> 60
+2 -> 62
x2 -> 124
+2 -> 126

Soit la même chose que ce que j’ai trouvé manuellement avant. Formidable, ça me donne deux façons de résoudre la même machine. Mais on tient maintenant un début d’algorithme récursif, en partant de la position finale:

Si on a atteint l’origine, on s’arrête et on renvoie 0.
Si on est allé trop loin dans une dimension, on s’arrête et on renvoie None.
On cherche quelles dimensions sont impaires.
Si elles sont toutes paires: on divise par deux, et on renvoie le double du nombre renvoyé par l’appel récursif dans cette nouvelle position.
Sinon, on passe sur toutes les combinaisons possible de 0 ou 1 appui sur chaque bouton (soit 2ⁿ possibilités pour n boutons).
- Si la combinaison nous amène sur une position paire, on renvoie le nombre de boutons à pousser pour arriver à la dimension paire, plus le résultat de l’appel récursif à la nouvelle position.

J’ai codé tout ça, et j’ai fini par obtenir une solution pour toutes les machines!

Malheureusement, ce n’était pas la bonne.

Alors je suis repartis sur reddit et j’ai lu l’entièreté de l’algorithme, qui est très similaire à ce que j’avais fait. Je l’ai implémenté, et j’ai obtenu… ma réponse, moins 1. 1 bouton poussé en moins sur les 166 machines de mon input. Et ça marche. J’essaierai de comprendre d’où vient le bug une autre fois. En attendant, repassons sur la solution qui fonctionne.

D’abord: précalculer tous les “patterns” possibles obtenus avec toutes les combinaisons de 0 ou 1 bouton. C’est, en gros, ce qu’on avait fait à la partie 1 avec presses = list(itertools.product([False, True], repeat=len(machine.buttons))). Sauf que maintenant, au lieu de juste faire des xor quand on appuie sur le bouton, on va calculer les incréments que ça fait dans toutes les dimensions.

@functools.cache
def _get_patterns(machine: Machine) -> Sequence[tuple[Sequence[int], int]]:
    presses = list(itertools.product([False, True], repeat=len(machine.buttons)))
    patterns = []
    for buttons_to_press in presses:
        pattern = [0 for _ in machine.reqs]
        for button, press in zip(machine.buttons, buttons_to_press):
            if press:
                pattern = [v+b for v, b in zip(pattern, button)]
        pattern = tuple(pattern)
        patterns.append((tuple(pattern), sum(buttons_to_press))) # store #buttons to press to get a pattern
    return tuple(patterns)

Je stocke ici, pour chaque combinaison possible de boutons poussés 0 ou 1 fois, le “vecteur de déplacement” que cette combinaison crée, ainsi que le nombre de boutons pressés.

Fonction récursive:
- Pour chaque pattern, calculer la nouvelle position atteinte avec cette combinaison de boutons (en sens inverse: on part du target et on cherche à rejoindre l’origine).
- Si la position obtenue est impaire, on passe.
- Si elle est paire, on divise la position par deux et on fait l’appel récursif. Le total de boutons à pousser est égale à 2 fois le résultat de la récursion, plus le nombre de boutons qu’on vient de pousser.
- Après avoir testé tous les patterns, on renvoie celui qui donne le moins de boutons au total.

Avec les critères d’arrêt:

Si je suis à la position (0, 0, ..., 0), je renvoie 0.
Si je suis <0 dans une des dimensions, je renvoie None.

@functools.cache
def reddit_solve(position: Sequence[int], machine: Machine):
    if all(p==0 for p in position):
        return 0
    if any(p<0 for p in position):
        return None
    
    min_push = None
    for pattern, n_push in _get_patterns(machine):
        new_pos = [xpos-xpat for xpos, xpat in zip(position, pattern)]
        if not any(x%2 for x in new_pos): # all positions are pair
            new_pos = [x//2 for x in new_pos]
            n_rec = reddit_solve(tuple(new_pos), machine)
            if n_rec is None:
                continue
            tot_push = n_push + 2*n_rec
            if min_push is None or tot_push < min_push:
                min_push = tot_push
    
    return min_push

On assorti les deux fonctions d’un cache qui fait qu’on ne calcule les patterns qu’une fois par machine, et que dès qu’on arrive deux fois sur la même position, on ne doive pas recalculer toute la récursion derrière. Sur beaucoup de machines ça ne change rien, mais sur certaines c’est absolument nécessaire.

Bon, un peu déçu de n’avoir pas complètement résolu par moi-même, mais je suis quand même content de la solution, et j’étais arrivé pas trop loin. Ca me permet d’officiellement compléter l’Advent of Code 2025.