Retour à l’index

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

Solution partie 1

Il me faut une nouvelle stratégie pour aborder la partie 2, parce que je n’arrive clairement à rien. Jusqu’à présent, j’essayais surtout de trouver un moyen de lister toutes les solutions possibles par ordre croissant de “nombre de boutons à pousser”, mais je n’arrive pas à avoir suffisamment de contraintes pour limiter le nombre de cas à tester dans un ordre de grandeur raisonnable. Essayons de voir le problème autrement.

Reprenons la machine d’exemple:

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}

Et voyons {3, 4, 5, 7} comme un point dans un espace à quatre dimensions. Mes boutons sont alors des vecteurs dans ce même espace.

(3) -> (0, 0, 0, 1)
(1, 3) -> (0, 1, 0, 1)
(2) -> (0, 0, 1, 0)
(2, 3) -> (0, 0, 1, 1)
(0, 2) -> (1, 0, 1, 0)
(0, 1) -> (1, 1, 0, 0)

Si on reformule le problème: on cherche à exprimer notre point final comme une combinaison linéaire de ces vecteurs, en cherchant la représentation telle que la somme des coefficients est minimale. Ces vecteurs ne forment pas une “base”, sinon on aurait une solution unique. Mais on a quelques propriétés possiblement intéressantes:

• Ils vont tous dans une direction positive.
• Ils ne permettent pas d’avancer de plus de “un” à la fois dans une dimension.

Quelles contraintes tout cela nous donne-t-il?

• Un coefficient maximal pour chaque vecteur:

Le vecteur (0, 1, 0, 1) (bouton (1, 3)), par exemple, ne peut pas avoir un coefficient supérieur à 5. Sinon j’arrive au-dessus de 5 pour la seconde dimension, et je n’ai aucun moyen de “revenir en arrière”.

• Des liens de dépendance entre certains vecteurs:

Comme (0, 0, 1, 1) est la somme de (0, 0, 1, 0) et (0, 0, 0, 1), je ne pourrai jamais pousser en même temps sur le bouton (2) et (3) si le bouton (2, 3) existe, car je pourrais alors remplacer deux appuis (un sur (2), un sur (3)) par un seul (sur (2, 3)), et je cherche la solution avec le moins de boutons appuyés.

Que faire avec tout ça…

Chercher un chemin?

Dijkstra?

Le problème de la recherche de chemin, c’est que sa complexité augmente d’autant plus qu’il y a de connexions possibles entre les noeuds. Et ici, on a pleins de connexions possibles. Essayons tout de même de faire un petit “pathfinding” à l’aide de mon vieil ami Dijkstra. Ce ne sera certainement pas efficace, mais à ce stade si je peux obtenir une réponse en quelques minutes ou même, honnêtement, quelques heures, je prends.

L’algorithme de Dijkstra, distillé à l’essentiel, c’est:

1. Choisir un noeud de départ (chez nous: l’origine à (0, 0..., 0), le nombre de dimensions variant par machine).
2. Marquer le noeud comme “visité”.
3. Pour tous les voisins (chez nous: tous les boutons à pousser):
   • Regarder où ça nous amène.
   • Regarder si on a déjà trouvé un chemin “plus court” (c’est-à-dire avec moins de poussage-de-bouton) pour y arriver, ou si on a déjà visité le noeud.
   • Si non: ajouter le voisin à une liste de “voisins à explorer”.
4. Sélectionner le voisin à explorer avec la plus petite distance au point de départ (le moins de boutons à pousser).
5. Revenir au point deux, sauf si on est à l’arrivée, auquel cas c’est gagné.

Pour mon implémentation, je rajoute une contrainte supplémentaire: je ne prends pas un noeud où au moins une des dimensions “dépasse” l’objectif (puisqu’on ne peut pas revenir en arrière), et je sélectionne de manière privilégiée les candidats les plus proches de l’arrivée.

Je découvre pour l’occasion heapq, qui est en gros une liste qui “reste triée” (plus ou moins) quand on ajoute des choses dedans. En tout cas, on est sûr que le premier élément est toujours le plus petit. Ca me permet de ne pas devoir retrier manuellement les candidats par distance à chaque fois.

def _hash(pos: list[int]) -> int:
    return hash(f"{pos}")

def _delta(a: list[int], b: list[int]) -> int:
    return sum([(t-p)**2 for t, p in zip(a, b)])

def solve_dijkstra(machine: Machine) -> int:
    end_pos = machine.reqs
    current = [0 for _ in machine.reqs]
    maxd = sum(end_pos)
    visited = set()
    min_distances = defaultdict(lambda: maxd+1)
    candidates = []
    heapq.heapify(candidates)
    current_dist = 0
    vectors = [[int(v) for v in button] for button in machine.buttons]
    
    while not all(c==t for c, t in zip(current, end_pos)):
        for v in vectors:
            node = [x+p for x, p in zip(v, current)]
            _node = _hash(node)
            if _node in visited or any(x>t for x, t in zip(node, end_pos)):
                continue
            if min_distances[_node] > 1 + current_dist:
                heapq.heappush(candidates, (_delta(node, end_pos), current_dist+1, node))
                min_distances[_node] = 1 + current_dist
        visited.add(_hash(current))
        delta, current_dist, current = heapq.heappop(candidates)
    
    return current_dist

Et… c’est lent. C’est très lent. Sur l’exemple, ça va toujours. Sur les données réelles… Ca ne se terminera pas dans un délais raisonnable.

Dernière tentative juste pour le fun: une version récursive, en utilisant functools.cache pour ne pas devoir recalculer les noeuds par lesquels on est déjà passés et qui ne mènent nulle part.

Cas de base:

• Si on dépasse le target dans une dimension, on s’arrête et on renvoie None (pas de chemin trouvé).
• Si on est au target, on renvoie 0.
• Sinon, on appelle récursivement la fonction sur les voisins et on rajoute 1 à celui qui a la distance minimale. Si tous les voisins renvoient None, on renvoie None aussi.

@functools.cache
def solve_recursive(current_pos: tuple,
                    target: tuple,
                    vectors: tuple[tuple]) -> int | None:
    if any(x>t for x, t in zip(current_pos, target)):
        return None
    if all(x==t for x, t in zip(current_pos, target)):
        return 0

    print(f"{current_pos} -> {target} ({_delta(current_pos, target)})", end="\r")
    next_nodes = [tuple([x+p for x, p in zip(v, current_pos)]) for v in vectors]
    next_nodes.sort(key=lambda x: _delta(x, target))
    results = [solve_recursive(n, target, vectors) for n in next_nodes]
    if all(r is None for r in results):
        return None

    return 1 + min(r for r in results if r is not None)

Ca marche toujours aussi bien sur l’exemple, et ça mouline toujours autant dans le vide sur les données réelles.

Je n’ai pas réussi à intégrer les dépendances entre boutons dans ma solution. Peut-être que ça permettrait de débloquer, mais j’en doute. Je pense que la “meilleure” solution que je pourrais trouver serait de faire appel à un résolveur algébrique, mais ça ne m’intéresse pas trop.

Tant pis, ce sera peut-être pour plus tard, mais je pense que je vais plutôt essayer d’aller regarder le “jour 11”, avec un peu de retard…