Jour 1 - Des cycles

On commence en douceur. Pour la première partie de ce puzzle, on a un document avec une série d’instructions pour faire tourner le code d’un coffre-fort:

On démarre de 50, les codes vont de 0 à 99, et chaque ligne nous indique une direction et un nombre de pas de rotations à effectuer. L, à gauche, va vers les négatifs; R vers les positifs. Ici, on commence donc de 50 et on tourne de 68 pas vers la gauche, dépassant le 0 pour revenir sur 100-18 = 82. Puis on va encore de 30 à gauche, pour arriver à 52. Puis on va 48 pas à droite pour arriver au 100.

On doit compter le nombre de fois qu’on passe par le 100 durant le processus.

Comment aborder le problème ?

Dès qu’on a un système cyclique comme ça, où on “revient à 0” tous les 100 pas, on pense immédiatement à un modulo. En fait, si on reformule le problème, il n’y a pas vraiment besoin de contraindre les chiffres à rester entre 0 et 99: on peut se contenter de sommer les valeurs (négatives pour L, positives pour R), et puis de compter le nombre de fois que le modulo %100 nous donne 0.

Pour commencer, il nous faut récupérer correctement les données d’entrée. Comme tous les puzzles d’Advent of Code commencent un peu de la même manière, j’ai fait des fonctions un peu génériques que je vais pouvoir réutiliser pour parser les fichiers d’input.

# ./src/utils/inputs.py
import pathlib
from typing import Any, Callable

CWD = pathlib.Path(__file__).parent

def load_input(day: int, suffix: str, transformer: Callable[[str], Any]) -> Any:
    """Get the raw data and transform it into the desired format.
    
    :param day: challenge day.
    :param suffix: suffix if multiple files in the day.
    :param transformer: function to parse the raw data into desired format.
    
    :return: transformed data (ex. list of tuples)
    """
    raw_data = load_raw(day, suffix)
    return transformer(raw_data)


def load_raw(day: int, suffix: str) -> str:
    """Get the raw data.
        
    :param day: challenge day.
    :param suffix: suffix if multiple files in the day.

    :return: string with the raw content of the file.
    """
    with open(CWD.joinpath(f"../../data/day{day}{suffix}.txt"), "r", encoding="utf-8") as fp:
        raw_data = fp.read()
    return raw_data

load_raw me permet de charger juste les données brutes dans une chaîne de caractères. Je stocke les inputs dans le dossier data, avec toujours par convention le nom dayX{suffix}.txt: par exemple, pour le premier jour, day1_sample.txt contiendra les données d’exemple, et day1.txt les données “réelles” à utiliser pour résoudre le puzzle.

load_input me permet de rajouter en plus une fonction de transformation, qui va être spécifique à chaque puzzle, et qui va me permettre de mettre les données dans un format utilisable.

Ici, j’aimerais bien avoir une liste d’entiers, positifs pour les instructions commençant par R et négatifs pour celles commençant par L. Je vais mettre ça dans un générateur:

# ./src/day1.py
from typing import Generator
from utils.inputs import load_input

def prepare_data(data: str) -> Generator[int, None, None]:
    lines = data.split('\n')        # couper par ligne
    for l in lines:                 
        if l == '':                 # ignorer ligne vide à la fin
            continue
        n = int(l[1:])              # partie "chiffres" de l'input -> integer
        if l[0] == 'L':             # si L, on multiplie par -1
            n *= -1
        yield n                     # pour faire un générateur

def main():
    data = load_input(1, '_sample', prepare_data)
    print(list(data))

if __name__ == "__main__":
    main()

Vérification sur les données de test ci-dessus: [-68, -30, 48, -5, 60, -55, -1, -99, 14, -82]. Tout ça m’a l’air correct.

Accumuler, modulo, compter

Étape suivante: faire la somme cumulée des différents éléments. Pour ce genre d’opérations, itertools a généralement ce qu’il nous faut, ici sous la forme de itertools.accumulate. Je peux juste faire:

data = accumulate(data)

Attention, je ne tiens pas ici encore compte du fait qu’on commence à 50. L’option la plus simple, c’est de rajouter un “50” au début de ma liste pour amener l’accumulateur au bon point de départ. Je vais juste rajouter un yield 50 au début de mon prepare_data. Ainsi, le générateur commence par envoyer 50, puis il parse la suite du fichier pour voir les instructions suivantes.

Bien, il ne reste plus qu’à compter les passage par le 0, c’est-à-dire tous les éléments qui, modulo 100, nous donnent 0. Pour tester si un élément doit être compté, je peux donc faire d%100==0, à sommer pour tous les éléments de data:

c = sum(d%100==0 for d in data)

sum va convertir les booléens en entier, donc tous les True compteront pour 1. J’obtient 3 pour la séquence de test, ce qui est la valeur attendue. Sur le vrai input, j’obtient également le bon résultat (964 dans mon cas, mais ça change pour chaque participant!). Code complet de day1.py jusqu’à présent:

# ./src/day1.py
from itertools import accumulate
from typing import Generator
from utils.inputs import load_input

def prepare_data(data: str) -> Generator[int, None, None]:
    yield 50
    lines = data.split('\n')
    for l in lines:
        if l == '':
            continue
        n = int(l[1:])
        if l[0] == 'L':
            n *= -1
        yield n

def main():
    data = load_input(1, '', prepare_data)
    data = accumulate(data)
    c = sum(d%100==0 for d in data)
    print(c)


if __name__ == "__main__":
    main()

Deuxième partie: on passe et on repasse

Tous les puzzles Advent of Code sont présentés en deux parties: une première généralement assez facile, et puis la deuxième partie vient modifier un peu le problème pour le rendre plus compliqué. Parfois un peu, parfois beaucoup plus compliqué.

Ici, on nous demande maintenant de ne plus seulement compter lorsqu’on arrive sur le 0 après une instruction, mais chaque fois qu’un instruction nous fait passer par 0. Donc si on passe de 50 à -18, on passe par zéro, et on doit le compter. Et si on passe plusieurs fois par le 0 sur la même opération (donc qu’on fait plus de 100 pas, à gauche ou à droite, il faut compter chaque passage).

Seul problème: lorsqu’on arrive exactement sur 0, on peut avoir des problèmes. Si je viens de 55 à 0, par exemple, je suis sur le même tour, mais je dois compter un passage. Si ensuite je passe de 0 à -5, par contre, je ne veux pas recompter un passage alors que j’ai déjà compté que j’étais arrivé sur 0!

Pour pouvoir passer sur deux éléments successifs à la fois, on peut utiliser itertools.pairwise. Je sens que, comme l’an dernier, itertools va être très utile pour tous ces puzzles.

# ...
data = load_input(1, '', prepare_data)
data = list(accumulate(data))
c = sum(d%100==0 for d in data)
print(f"Part 1: {c}")

acc = 0
for prev, cur in pairwise(data):
    turn_prev = prev//100   # "tour" sur lequel se trouve prev
    turn_cur = cur//100     # "tour" sur lequel se trouve cur 
    d_turn = abs(turn_cur-turn_prev) # différence entre les deux = nb de fois qu'on passe par 0
    acc += d_turn
    # attention: si on partait de zéro et qu'on ve à gauche, 
    # on ne doit pas compter le premier changement
    if prev%100 == 0 and cur < prev:
        acc -= 1
    # attention: si on arrive à 0 et qu'on venait de la droite, 
    # on doit compter même si on reste sur le même tour
    if cur%100 == 0 and cur < prev:
        acc += 1
    
print(f"Part 2: {acc}")

Sur les données de test, j’ai bien 6 passages. Et sur les vraies données, j’arrive à 5872, ce qui pour moi est le bon mot de passe qui me donne ma deuxième étoile.