Jour 7 - Laser de Pascal

Premier puzzle de l’année pour lequel j’ai mis du temps à bien comprendre l’énoncé, et où j’ai eu besoin de faire des petites notes pour suivre ce qu’il se passait et m’assurer de ne pas me planter. Je préfères vraiment ce type de puzzle par rapport à celui d’hier.

On tire un laser depuis le point marqué par S, tout en haut de notre input. Dans l’exemple:

Ce laser est tiré vers le bas. Chaque fois qu’il rencontre un “diviseur” ^, il est séparé en deux, à gauche et à droite du diviseur. Ces deux parties continuent alors leur chemin vers le bas. À la fin, on a:

La question pour la première partie est: combien de fois le laser est-il divisé?

Ou, en reformulant très légèrement: combien de fois le laser rencontre-il un diviseur? Ou en retournant la question: combien de diviseurs sont touchés par un laser?

Préparation des données

C’est typiquement le genre de problèmes où l’input n’est pas nécessairement difficile à parser, mais il faut bien choisir la structure de données qu’on va utiliser pour stocker les valeurs et se faciliter la vie. Ici, ce qui nous intéresse, c’est la colonne dans laquelle se trouvent chaque diviseur (et le point de départ). On n’a pas besoin de connaître un numéro de ligne, mais on doit par contre garder les lignes dans le bon ordre. Je vais donc ignorer les lignes où il n’y a pas de ^, et faire une fonction qui renvoie la colonne du S, ainsi que, pour chaque ligne avec diviseurs, une liste de numéros de colonnes.

La méthode liste.index(valeur) permet de renvoyer l’index d’une valeur dans une liste, et nous sert à trouver la position de S dans la première ligne. Pour les autres, on peut parcourir les éléments, et ajouter les index de chaque ^:

def prepare_data(data: str) -> tuple[int, list[list[int]]]:
    rows = data.split('\n')
    start = rows[0].index('S')
    splitters = []
    for row in rows[1:]:
        splitters_in_row = [i for i,v in enumerate(row) if v == '^']
        if len(splitters_in_row) > 0:
            splitters.append(splitters_in_row)
    return start, splitters

Première partie: diviseurs activés

Un diviseur est activé lorsqu’un rayon se trouve sur la même colonne que lui. On va donc traquer, ligne par ligne, la position des rayons. Chaque fois qu’un rayon touche un diviseur de la colonne c, on sait qu’à la ligne suivante il faudra un rayon dans les colonnes c-1 et c+1, et que le rayon de la colonne c disparaîtra. On n’a pas besoin de traquer chaque rayon individuellement: lorsque plusieurs rayons arrivent sur la même colonne, ils peuvent être rassemblés en un seul. J’utilise donc un set pour garder ma liste de rayons actifs, ainsi je suis sûr de ne pas garder de doublons. Et je vais garder un compteur du nombre de diviseurs activés. Au début, on a un rayon (dans la colonne start) et 0 diviseurs actifs.

def count_activated_splitters(start: int, splitters: list[list[int]]) -> int:
    active_beams = {start}
    active_splitters = 0
    # ...

Ensuite, on parcourt ligne par ligne les diviseurs. Pour chaque ligne, on regarde si les rayons actifs touchent un diviseur. Si c’est le cas, on les ajoute dans un set:

def count_activated_splitters(start: int, splitters: list[list[int]]) -> int:
    # ...
    for row in splitters:
        activated_splitters = set()
        for beam in active_beams:
            if beam in row:
                activated_splitters.add(beam)
    # ...

On peut alors rajouter les diviseurs activés. Comme on a utilisé un set aussi pour les conserver, on peut utiliser les opérations ensemblistes entre active_beams et activated_splitters: pour retirer les colonnes des diviseurs activés de l’ensemble des colonnes des rayons actifs, on peut utiliser difference. Et on rajoute ensuite les colonnes à gauche et à droite des diviseurs activés avec add.

def count_activated_splitters(start: int, splitters: list[list[int]]) -> int:
    # ...
    for row in splitters:
        # ...
        active_splitters += len(activated_splitters)
        active_beams = active_beams.difference(activated_splitters)
        for s in activated_splitters:
            active_beams.add(s-1)
            active_beams.add(s+1)
    return active_splitters

def main():
    start, splitters = load_input(7, '_sample', prepare_data)
    print(f"Part 1: {count_activated_splitters(start, splitters)}")

Deuxième partie: c’est quantique ?

J’ai mis un peu de temps à comprendre exactement ce qu’on cherchait dans la seconde partie, qui essaye un peu de couvrir quelque chose de pas si compliqué que ça dans un discours quantique. On doit compter maintenant le nombre de chemins différents que notre laser peut parcourir, en imaginant que chaque diviseur fait maintenant un “choix” plutôt que de séparer le rayon en deux. Cette fois-ci, lorsque des rayons sont superposés, ils doivent donc être comptés séparément, car ils ne représentent pas le même chemin complet.

On a au bout quatre chemins uniques: un qui arrive à gauche, deux chemins au milieu, et un à droite.

Reprenons l’exemple complet, en supprimant les lignes vides pour condenser un peu:

Ce qui au bout nous donne 1+2+10+11+11+2+1+1+1 = 40 chemins, qui est bien la réponse qu’on nous donne dans l’exemple. Outre le fait que ça forme un beau sapin de Noël, on a aussi une similarité avec le principe du triangle de Pascal, qui m’a fait espéré un instant de pouvoir l’utiliser pour la réponse, ce qui aurait été très classe. Mais Pascal n’interviendrait que si les diviseurs étaient placés de manière bien régulière. Ici, on a donc un Pascal dégénéré.

Une fois le problème compris, cependant, la solution est relativement simple. Maintenant, en plus de traquer la position des rayons, on doit compter combien de rayons différents sont “superposés” sur chaque position. Au set de colonnes dans lesquelles se trouve un rayon, je dois donc maintenant associer une valeur, soit le nombre de rayons. Associer les éléments d’un set à des valeurs, c’est exactement ce que fait un dictionnaire en Python. Je vais utiliser un defaultdict, qui est un dictionnaire auquel on donne un générateur de valeurs par défaut (ici, je vais donner une fonction lambda qui renvoie juste toujours 0). L’avantage est de ne pas devoir vérifier si un élément existe avant de l’utiliser. Si, par exemple, je veux ajouter n à la valeur de l’élément e, dans un dictionnaire normal d je devrais faire:

if e in d:
    d[e] += n
else:
    d[e] = n

d[e] = d.get(e, 0) + n

Alors que si on crée d comme un defaultdict avec d = defaultdict(lambda: 0), on peut juste faire d[e] += n avec le même effet. Pratique!

On ne doit plus garder trace des diviseurs eux-mêmes, donc notre fonction devient assez simple. On initialise un chemin sur la colonne start, puis on parcourt les diviseurs ligne par ligne. Pour chaque diviseur, s’il se trouve sur un chemin, on récupère le nombre de superpositions et on les ajoute à gauche et à droite. Sur la colonne du diviseur, le nombre de chemins devient 0.

def count_paths(start: int, splitters: list[list[int]]) -> int:
    active_paths = defaultdict(lambda: 0)
    active_paths[start] = 1

    for row in splitters:
        for s in row:
            if s in active_paths:
                n = active_paths[s]
                active_paths[s] = 0
                active_paths[s-1] += n
                active_paths[s+1] += n
    
    return sum(active_paths.values())

def main():
    start, splitters = load_input(7, '_sample', prepare_data)
    # ...
    print(f"Part 2: {count_paths(start, splitters)}")