Skip to main content

Advent of Code 2021 Day 1

Le problème

Ça y est ! L’Advent of Code est de retour avec cette édition 2021 ! Pour cette année, je vais tenter de tenir un peu mieux le rythme avec la rédaction des billets de blog revenant sur chaque exercice. Voyons donc sans plus attendre les énoncés des exercices de ce premier jour.

Partie 1

Dans cette première partie, on nous explique que l’on fait une tournée en sous-marin pour récupérer les clés de Noël qu’un elfe aurait fait tomber d’un bateau. Pour éviter que ce sous-marin ne se cogne contre le plancher océanique, un sonar mesure la profondeur en permanence. Les données en entrée sont donc des entiers positifs qui correspondent à une mesure de profondeur.

L’exemple proposé de données en entrée est le suivant :

199
200     # Augmente
208     # Augmente
210     # Augmente
200
207     # Augmente
240     # Augmente
269     # Augmente
260
263     # Augmente

Notre travail consiste désormais à compter le nombre de fois que la différence entre deux mesures successives est positive (celles-ci sont indiquées dans l’exemple précédent).

Pour cette partie, il n’y a pas de grande difficulté dans la conception de l’algorithme. On compare les données deux à deux, et on incrémente un compteur (c’est plus ou moins ce que j’ai fait dans ma solution ci-après).

def solve_part_one():
    data = open('input-small', 'r')
    lines = [int(x) for x in data.read().splitlines()]
    increases = [1 for i in range(len(lines[:-1])) if lines[i] < lines[i+1]]
    print(len(increases))

Partie 2

Dans la seconde partie, on nous indique désormais que les comparaisons deux à deux ne sont pas suffisantes. À la place, on va utiliser une fenêtre glissante pour comparer deux à deux non plus chaque élément mais la somme de trois mesures successives.

Dans la même idée, il faut désormais créer une structure de données qui pourra stocker toutes les valeurs vues par cette fenêtre glissante. Puis, on va comparer ces valeurs comme dans la partie précédente.

def solve_part_two():
    data = open('input-large', 'r')
    lines = [int(x) for x in data.read().splitlines()]
    threes = [lines[i] + lines[i+1] + lines[i+2] for i in range(len(lines[:-2]))]
    increases = [1 for i in range(len(threes[:-1])) if threes[i] < threes[i+1]]
    print(len(increases))

Les difficultés

Ici, on reste sur de la difficulté de premier jour. Mais il y a tout de même un point de vigilance : il faut bien penser à cast les données en int.

En effet, il est tout à fait possible de comparer des chaînes de caractères en Python. Mais il faut faire attention à bien comprendre ce qu’il se passe lorsque l’on effectue ce genre de comparaison. Prenons l’exemple dans mon jeu de données qui peut causer le principal problème pour cette journée :

...
990
1011
...

Ici, si l’on évalue l’expression '990' < '1011', le résultat obtenu est False. Cela s’explique par le fait que Python va comparer ces deux chaînes de caractères en procédant caractère par caractère. Ainsi, on va commencer par évaluer l’expression '9' < '1' qui vaut False. La suite de la comparaison n’est plus évaluée, et le résultat est tout de suite renvoyé.

Cela explique les erreurs de type off by one que j’ai vues chez les collègues qui participent également cette année avec moi !

comments powered by Disqus