Jour 10 - J’appuie sur les boutons

Premier échec, pour l’instant en tout cas. On verra si le “pour l’instant” s’applique à “premier” ou à “échec” plus tard…

La première partie a déjà demandé un peu de boulot. La seconde partie, je ne vois pas pour l’instant comment la résoudre sans faire appel en restant dans mes contraintes auto-imposées d’utiliser les outils “built-in” de Python.

Chaque ligne décrit une machine et contient trois éléments. Le premier, avec les [.##.], représente des lumières à allumer. . signifie “éteint”, # allumé. Le second, avec les chiffres entre parenthèse, décrit des boutons qui agissent sur ces lumières. Si j’appuie sur le bouton (1, 3), cela change l’état des lumières situées aux indices 1 et 3 (on démarre à l’indice 0 pour ce problème-ci). On part toujours de [....] (toutes les lumières éteintes), et on cherche à atteindre l’état indiqué dans le premier élément. Pour la première machine, par exemple, la séquence la plus courte qui nous amène à l’état désiré est:

On veut calculer cette “séquence la plus courte” pour toutes les machines. Le troisième élément (les chiffres entourés par des {}) ne servent à rien pour l’instant, ils nous tortureront plus tard.

Première partie: une machinerie inutile

J’ai fait beaucoup de choses pas très utiles, ici. Dans les puzzles Advent of Code, il y a souvent deux approches pour démarrer, que j’appellerais coder le problème et coder la solution. Coder la solution, c’est ce que j’ai généralement essayé de faire les jours précédents: d’abord réfléchir à une méthode de résolution, puis la réaliser avec un code qui se focalise sur ce qui est nécessaire pour l’atteindre. Quand j’ai plus de mal à voir dans quelle direction partir, je vais souvent démarrer en codant le problème. C’est-à-dire: prendre les éléments qui nous sont donnés dans l’énoncé, tel quel, et essayer de les modéliser avec le code, puis à voir ce qu’il se passe.

Souvent, ça marche pour la première partie, et ça aide à mieux comprendre comment le problème fonctionne, même s’il faut parfois partir dans une direction très différente pour la seconde partie.

Ici, j’ai choisi de modéliser une “machine” dans une classe, avec un code franchement dégueulasse pour parser l’input. Je stocke le target (l’état final désiré des lampes) dans une liste de booléens. Pour les boutons, je transforme chaque bouton en liste de booléens aussi, indiquant quels lumières seront allumées. Par exemple, (0, 2) deviendrait (s’il y a quatre lampes) [True, False, True, False]. Je stocke tous les boutons dans une liste de listes de booléens. Et je garde les autres nombres qui ne servent provisoirement à rien dans une liste d’entiers.

J’initialise également un état de départ à False pour toutes pour les lumières.

class Machine:
    def __init__(self, target: list[bool], buttons: list[list[bool]], reqs: list[int]):
        self.target = target
        self.buttons = buttons
        self.reqs = reqs
        self.state = [False for _ in target]
    
    @classmethod
    def from_string(cls, s: str) -> Self:
        parts = s.split()
        target = []
        for c in parts[0]: #[ ] part
            if c == '.':
                target.append(False)
            elif c == '#':
                target.append(True)
        buttons = []
        for expr in parts[1:-1]: #( ) ( ) part
            button = [False for _ in target]
            idxs = expr[1:-1].split(',')  # remove parentheses
            for idx in idxs:
                button[int(idx)] = True
            buttons.append(button)
        reqs = [int(c) for c in parts[-1][1:-1].split(',')]
        return cls(target, buttons, reqs)

Pour terminer la modélisation, je fais des méthodes permettant d’appuyer sur un bouton, de remettre les lumières “à zéro”, et de vérifier si les lumières sont dans le bon état. “Appuyer sur le bouton” utilise le ^, soit le XOR, pour modifier l’état de toutes les lumières liées au bouton.

class Machine:
    # ...
    def press(self, button: int) -> None:
        self.state = [s ^ b for s, b in zip(self.state, self.buttons[button])]
    
    def reset(self) -> None:
        self.state = [False for _ in self.state]
    
    def check(self) -> bool:
        return all(s == t for s, t in zip(self.state, self.target))

Reste à “résoudre” la machine, c’est-à-dire trouver la plus petite combinaison de boutons à appuyer qui mette la machine dans le bon état. La chose importante à remarquer ici, c’est qu’appuyer deux fois sur un bouton n’a aucun effet (on va changer certains éléments, puis les re-changer et donc les remettre dans leur état initial). Même si l’énoncé essaie de nous induire en erreur en mettant dans les solutions possibles mais non-optimales de la première machine que “You could press (1,3) once, (2,3) once, and (0,1) twice, a total of 4 button presses”, on doit en réalité simplement regarder toutes les combinaisons de “appuyer” ou “ne pas appuyer” sur chaque bouton.

Pour lister toutes ces possibilités, je vais une nouvelle fois me tourner vers itertools, et plus spécifiquement cette fois-ci itertools.product. product réalise le “produit cartésien” entre des itérables. Par exemple, si je fais le produit entre [a, b] et [c, d], j’obtiendrai les paires [(a, c), (a, d), (b, c), (b, d)]. On peut spécifier un argument repeat pour ne fournir qu’un seul itérable qu’on répète plusieurs fois. Par exemple, product([1, 2], repeat=2) nous donnera [(1, 1), (1, 2), (2, 1), (2, 2)]. Pour une machine donnée, on veut toutes les combinaisons de True et False pour tous les boutons. On va donc utiliser itertools.product([False, True], repeat=len(machine.buttons)).

def solve_machine(machine: Machine) -> list[bool]:
    presses = list(itertools.product([False, True], repeat=len(machine.buttons)))
    # ...

Pour éviter de devoir tester toutes ces combinaisons, je vais d’abord les trier en fonction de leur somme (c’est-à-dire le nombre de boutons appuyés). Cela me permet ensuite d’être sûr que, dès que je trouve une combinaison qui fonctionne, c’est celle (ou une de celles) avec le moins de boutons à appuyer, et c’est donc une solution valide pour le problème.

def solve_machine(machine: Machine) -> list[bool]:
    # ...
    presses.sort(key=lambda x: sum(x)) # sort by smallest number of button presses
    # ...

On passe enfin sur chaque combinaison. On remet la machine à zéro, on appuie sur les boutons et, si la machine est dans le bon état, on renvoie la liste des boutons sur lesquels on a poussé.

def solve_machine(machine: Machine) -> list[bool]:
    # ...

    for pattern in presses:
        machine.reset()
        for i, p in enumerate(pattern):
            if p:
                machine.press(i)
        if machine.check():
            return list(pattern)
    raise ValueError(f"Machine couldn't be solved")

La réponse demandée est la somme de toutes les fois où on a appuyé sur un bouton: on calcule tout ça dans le main:

def main():
    data = load_input(10, '', prepare_data)
    patterns = [solve_machine(machine) for machine in data]
    ns = [sum(p) for p in patterns]
    print(f"Part 1: {sum(ns)}")

Deuxième partie: le troisième élément

Et maintenant, on revient au dernier élément de la machine, les chiffres entourés par les {}. À partir de maintenant, on ignore les petites lumières. Ce qu’on veut, ce n’est plus trouver un motif binaire, mais c’est arriver à ces nombres bien précis. Il y a autant de nombre qu’il y avait de “lumières” avant, et ils sont liés de la même façon aux boutons, si ce n’est que l’opération des boutons n’est plus maintenant de faire un xor, mais d’incrémenter un compteur. Si on reprend l’exemple initial, on va maintenant partir de l’état {0, 0, 0, 0}, et on cherche à arriver à {3, 5, 4, 7}, ce qu’on peut faire avec la séquence:

À nouveau, on cherche à arriver à ce résultat avec le moins de pressage de bouton possible.

Le problème ici est que, dans l’input réel, le nombre de boutons et les nombres à atteindre sont nettement plus importants, et que le nombre de combinaisons possibles à effectuer explose complètement, donc l’approche “lister les possibilités et les tester” ne fonctionne juste pas. J’ai essayé différentes manières d’ajouter des contraintes (par exemple: si un bouton est lié au premier nombre et que ce nombre est 10, on ne pourra jamais pousser ce bouton plus de 10 fois, parce qu’aucun bouton ne permet de “revenir en arrière”). Ici, l’approche coder le problème ne marche pas, il faut trouver d’abord une solution.

Mathématiquement, le problème est assez simple à exprimer. On a en fait une série d’équations avec des contraintes. Par exemple, reprenons la première machine, et donnons des lettres au “nombre de fois qu’on appuie sur le bouton” pour chaque bouton:

Soit quatre équations à six inconnues, où l’on cherche la solution qui minimise a+b+c+d+e+f. Il y a certainement des librairies de résolution numérique qui permettent de trouver le résultat rapidement, mais je n’ai pas trop envie d’y avoir recours. En général, dans les problèmes Advent of Code, il y a moyen d’arriver à la solution sans avoir besoin d’outils spécifiques.

J’ai encore quelques idées en réserve, mais je n’ai plus trop le temps ni l’envie de les tester aujourd’hui, donc on va en rester là pour l’instant.