Un petit retour sur l'AOC 2021

Image de l'AoC
L'Advent of Code 2021, le concept est simple. Chaque jour du calendrier de l'avent vous devez résoudre un exercice de programmation (dit des puzzles) qui comporte deux niveaux de difficulté. Tout ceci est mis en contexte puisque vous aidez les lutins du père Noël (ici des elfes, mais on France on parle de lutin !) à récupérer les clés du traîneau ... Oui le traîneau du père Noël a des clés, et un lutin les a fait tomber dans l'océan. Ne vous arrêtez pas déjà à la narration car ça va devenir encore plus improbable !

Je vais donc écrire quatre relativement cours billets sur les exercices de chaque semaine.Avant de parler des exercices, je vous fais un retour rapide sur mon sentiment global après un petit mois.

Sommaire

  1. Ce que j'en aie pensé
  2. Jour 1: Un sous-marin ?!
  3. Jour 2 : Ben vus allez le conduire !
  4. Jour 3: Lire le diagnostic
  5. Jour 4: Bingo ?!
  6. Jour 5: Les fumées tuent
  7. Jour 6: Les poissons-lanternes
  8. Jour 7: Le prochain repas d'un cachalot
  9. Conclusion

Ce que j'en aie pensé

Tout d'abord, c'est très intéressant comme défi. C'est avant tout un défis personnel un peu comme l'Inktober (un défis d'un mois où chaque jour vous devez dessiner un dessin sur un thème “fixé” à l'avance). J'ai personnellement bien aimé et je recommencerais l'année prochaine si possible.

Je dis bien si possible car c'est quelque chose qui prend du temps. Beaucoup de temps. Certains exercice m'ont dérangé personnellement mais ça vient également peut-être de moi.

L'évènement se targue d'être accessible aux débutants. Ce n'est qu'à moitié vrai. Au fils du mois les exercices vont se complexifier et demander un temps déraisonnable pour un débutant. Cependant, il n'est pas interdit de se faire aider, l'ensentiel étant d'apprendre. Et en se sens ça devient plus abordable pour un débutant en programmation.

Une autre difficulté est que les exercices sont en anglais. Ça ne pose pas de problèmes de manière générale mais ça reste une difficulté puisque le vocabulaire n'est pas courant. C'est clairement un frein en tout cas pour quelqu'un qui ne maîtrise pas la langue.

Passons maintenant à la première semaine !

Jour 1: Un sous-marin ?!

Oui, vous embarquez dans un sous-marin pour allez chercher les clés. C'est parti pour le premier jour.

L'exercice du jour est de trouver le nombre de valeur supérieures à la précédente au sein d'une suite de nombres.

La solution est assez simple :

incr = 0 # La variable qui va compter le nombre que l'on cherche

with open("input") as f:
    a = int(f.readline()) # La valeur précédente
    for line in f:
        b = int(line)     # La valeur courante
        if b > a:
            incr += 1
        a = b             # La valeur courante deviant la prochaine précédente !

print(incr)

Mais j'ai vu d'autres codes que je traduis en Python :

with open("input") as f:
    input = list(map(int, f.read().strip().split()))
    # On compte 1 pour chaque paire d'éléments dont le premier est inférieur au second.
    print(sum(1 for
          prev, cur in zip(input, input[1:]) if prev < cur
    ))

La difficulté 2 est de faire ceci sur une fenêtre de trois valeurs. En premier lieux, on pense à sommer tous les triplets successifs puis d'appliquer l'algorithme précédent. Mais en fait, il y a plus simple. Un triplet est plus grand si la valeur qu'on lui retire est plus petite que celle qu'on ajoute.

Mon code est devenu un peu répétitif :

incr = 0

with open("input") as f:
    a = int(f.readline())
    b = int(f.readline())
    c = int(f.readline())

    for line in f:
        d = int(line)
        if d > a:
            incr += 1
        a, b, c = b, c, d

print(incr)

Là où celui d'autres personnes à été très peu adapté puisque qu'ils n'ont eu qu'à changer qu'un seul caractère de leur code :

with open("input") as f:
    input = list(map(int, f.read().strip().split()))
    print(sum(1 for
          prev, cur in zip(input, input[3:]) if prev < cur
    ))

Ici, les paires sont en fait constitués d'éléments séparés, entre-eux, de 3 plutôt que 1.

Jour 2 : Ben vus allez le conduire !

Au jour deux vous apprenez à conduire le sous-marin !
Le sous-marin est contrôlé par un plan d'instruction que vous devez évaluer.

Le but est donc de simuler la course d'un sous-marin en fonction des instructions qu'on lui donne. C'est un sous-marin, il peut monter, descendre et avancer, c'est à peu près tout !

Exemple d'entrée :

forward 5
down 5
forward 8
up 3
down 8
forward 2

Là encore, c'est assez simple. On se rend bien compte qu'il n'y a que deux coordonnés importante pour le sous-marin, la profondeur et à quel point il a avancé.

horizon, detph = 0, 0

with open('input') as f:
    for line in f:
        cmd, num = line.split(' ')
        num = int(num)
        if cmd == "forward":
            horizon += num
        elif cmd == "down":
            detph += num
        elif cmd == "up":
            detph -= num

print( horizon *  detph) # On nous demande ce nombre pour vérifier la simultation

La difficulté 2 est peu différente. Cette fois-ci, on doit calculer la visée ? (aim en anglais) du sous-marin. Qui elle-même influe les actions du sous-marin.

aim = 0
horizon, detph = 0, 0

with open('input') as f:
    for line in f:
        cmd, num = line.split(' ')
        num = int(num)

        if cmd == "forward":
            horizon += num
            detph += aim * num
        elif cmd == "down":
            aim += num
        elif cmd == "up":
            aim -= num

print( horizon *  detph)

Ici, il n'y a pas de difficulté mais ça reste un puzzle peu optimisable. Un peu aussi dérangeant qu'un Fizz Buzz.

Jour 3: Lire le diagnostic

Le sous-marin vous donne un diagnostic dans un format binaire. Vous devez calculer le taux gamma et epsilon dont dépend la consommation du carburant.

Vous avez pour ça une suite de nombre binaire :

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

On doit chercher le bit le plus courant pour chiffre de cette liste de nombre binaire. Dans la première colonne cela nous donne 1 car c'est le nombre le plus courant. Pour chacun des indices ça donne 10110 soit 22 en décimal, cette valeur est le taux gamma. Le taux epsilon est similaire mais avec le bit le moins courant.

Bon ben c'est parti pour coder ça. J'ai d'abord fait un truc bien moche dont je suis pas fière.

Si je devais le ré-écrire ça donnerait plutôt ça :

from collections import Counter

count = Counter()
length = 0

with open("input") as f:
    for line in f:
        count.update(Counter(enumerate(line.strip())))
    length = len(line) - 1

gamma   = ['1' if count[(i, '1')] > count[(i, '0')] else '0' for i in range(length)]
epsilon = ['1' if count[(i, '0')] > count[(i, '1')] else '0' for i in range(length)]

# On convertit en décimal
gamma   = int("".join(gamma), 2)
epsilon = int("".join(epsilon), 2)

print(epsilon * gamma)

C'est-à-dire que Python propose des structures de données qu'on peut réutiliser pour les actions courantes comme compter. C'est exactement ce que je vais ici et on va voir que c'est quelques chose qu'on va souvent utiliser par la suite !

En avant pour la partie 2 !

Cette fois-ci on doit itérer plusieurs fois sur les valeurs (c'est la première fois que l'on doit faire ça) et à chaque fois ne garder que les valeurs qui ont le plus n^ième^ bit le plus (le moins pour l'autre donnée) courant. On continue jusqu'à ce qu'il n'y en ait plus qu'un.

Bon ben là, j'ai dû tout refaire mon code. Mais j'ai quand même fait un code pas super propre. Ouais, y a un bon gros copier/coller. Bon si je devais le recoder j'aurais fait ça :

from collections import Counter

with open("input") as f:
    number = f.read().split()

number_oxy, number_co2 = list(number), list(number)
length, i = len(number_oxy[0]), 0

while len(number_oxy) > 1 or len(number_co2) > 1 and i < length:
    if len(number_oxy) > 1:
        oxy = Counter(map(lambda x: x[i], number_oxy))
        # On garde le bit le plus courant, si ex equo, on prend '1'.
        keep = '1' if oxy.most_common()[0][1] == oxy.most_common()[1][1] else oxy.most_common()[0][0]
        number_oxy = [ number for number in number_oxy if number[i] == keep]

    if len(number_co2) > 1:
        co2 = Counter(map(lambda x: x[i], number_co2))
        # On garde le bit le moins courant, si ex equo, on prend '0'.
        keep = '0' if co2.most_common()[0][1] == co2.most_common()[1][1] else co2.most_common()[1][0]
        number_co2 = [ number for number in number_co2 if number[i] == keep]
    i += 1

oxy_rate = int("".join(number_oxy[0]), 2)
CO2_rate = int("".join(number_co2[0]), 2)

print(oxy_rate * CO2_rate)

C'est là même pensé que mon précédant code mais en plus concis et plus claire. L'idée c'est vraiment de suivre l'algo décrit dans les consignes.

Jour 4: Bingo ?!

Je vous assure vous êtes pas prêt. Le sous-marin se fait attraper pas un calamar géant. Et ...

Peut-être veut-il jouer au Bingo ?
Jour 4 !

Ça tombe bien le sous-marin a un système permettant de jouer au Bingo pour occuper ses passagers. 🤦

Donc nous voilà entrain de jouer au Bingo. Le calamar à plusieurs tentacules et le risque de perdre est proportionnel au nombre de tentacule du calamar. Alors apparemment, on triche et on demande à l'ordinateur du sous-marin de nous donner à l'avance la liste des nombres qu'il va sortir. Comme ça après, on peut prendre la première grille qui gagne 🦹 !

Bon ben la stratégie ça va être de remplacer les nombres déjà sortis par des zéros et si on a une ligne de 0 alors la grille a gagné !

bingo_numbers, bingo_grid = [], []


def replaceByZero(number, grid):
    for i in range(5):
        for j in range(5):
            if grid[i][j] == number:
                grid[i][j] = 0
                return

def hasZeroRowOfCols(grid):
    for i in range(5):
        allZero_row, allZero_col = True, True

        for j in range(5):
            if grid[j][i] != 0:
                allZero_col = False
            if grid[i][j] != 0:
                allZero_row = False

        if allZero_row or allZero_col:
            return True

    return False


with open("input") as f:
    bingo_numbers = list(map(int, f.readline().split(',')))

    while True:
        line = f.readline()
        if not line:
            break
        bingo_grid.append([list(map(int, filter(lambda x: x != '', f.readline().strip().split(' ')))) for _ in range(5)])

i, number = 0, 0
for number in bingo_numbers:
    for grid in bingo_grid:
        replaceByZero(number, grid)

    for i in range(len(bingo_grid)):
        if hasZeroRowOfCols(bingo_grid[i]):
            break
    else:
        continue
    break

print(sum(sum(bingo_grid[i], [])) * number)

La deuxième partie, semble-t-il que le calamar est connu pour ne pas aimer perdre. Alors il vaudrait mieux être sûr qu'il ne perde sur aucune de ses tentacules. Pour cela, vous devez prendre la dernière grille qui gagne.

Le code est pas plus compliqué, on change juste la condition de sortie et on supprime les grilles au fur et à mesure.

number = 0
for number in bingo_numbers:
    for grid in bingo_grid:
        replaceByZero(number, grid)

    for i in reversed(range(len(bingo_grid))):
        if hasZeroRowOfCols(bingo_grid[i]):
            if len(bingo_grid) <= 1:
                break
            del bingo_grid[i]
    else:
        continue
    break

print(sum(sum(bingo_grid[0], [])) * number)

Voilà pour aujourd'hui !

Jour 5: Les fumées tuent

Les monts hydrothermaux créent d'épaisses fumerolles qu'il serait bon d'éviter. Le sous-marin produit une liste de lignes où il détecte trop de ces fumerolles. Pour mieux comprendre la mise en contexte, je vous invite à lire l'énoncé du jour 5.

Bon mon idée a été de créer une grille où on va tracer les lignes. Chaque case de la grille comptant le nombre de fois qu'on est passé par cette case.

Mais ça ne passe pas à l'échelle. Si la grille devient très grande alors on risque de stocker beaucoup de points à 0 qui seront inutiles. Il y a deux types de lignes, les lignes droites et les lignes diagonales qui forme un angle de 45° (par rapport à l'horizontal ou la verticale).

Dans un premier temps on se concentre sur les lignes droites. C'est à dire, horizontales ou verticales. Ça donne ça :

from collections import defaultdict

segs = []
max_X, max_Y = 0, 0
pts = defaultdict(int)

with open('input') as f:
    for line in f:
        x1, y1, x2, y2 = map(int, line.strip().replace(' -> ', ',').split(','))
        segs.append((x1, y1, x2, y2))
        max_X, max_Y = max(max_X, x1, x2), max(max_Y, y1, y2)

for s in segs:
    x1, y1, x2, y2 = s
    # Si c'est une ligne droites
    if x1 == x2 or y1 == y2:
        x_min, x_max = min(x1, x2), max(x1, x2)
        y_min, y_max = min(y1, y2), max(y1, y2)
        for x in range(x_min, x_max + 1):
            for y in range(y_min, y_max + 1):
                pts[(x,y)] += 1

print(len(list(filter(lambda x: x > 1, pts.values()))))

L'idée c'est que soit range(x_min, x_max + 1) soit range(y_min, y_max + 1) sera réduit à un seul élément et on retrouvera donc bien une droite. Donc pour tracer un segment, on part du point du segment le plus en haut à gauche (celui qui minimise x et y) jusqu'à l'autre point.

Partie 2, il faut prendre en compte toutes les lignes. Et c'est un peu là qu'on regrette de ne pas avoir fait un code plus générique... Ou alors pas assez ad hoc.

for s in segs:
    x1, y1, x2, y2 = s
    pts[(x1, y1)] += 1

    while (x1, y1) != (x2, y2):
        # On se rapproche de 1 à chaque fois si on y est pas déjà

        if x1 < x2:
            x1 += 1
        elif x1 > x2:
            x1 -= 1

        if y1 > y2:
            y1 -= 1
        elif y1 < y2:
            y1 += 1

        pts[(x1, y1)] += 1

Oui, eh bien ça fait le taf. Peut-être que l'idée de l'exercice était d'utiliser l'algorithme de Bresenham. Mais au final il se fait très bien sans. Si on essaye de s'en inspirer tout de même on peut arriver à ce code :

from collections import defaultdict

segs = []
max_X, max_Y = 0, 0

with open('input') as f:
    for line in f:
        x1, y1, x2, y2 = map(int, line.strip().replace(' -> ', ',').split(','))
        segs.append((x1, y1, x2, y2))
        max_X, max_Y = max(max_X, x1, x2), max(max_Y, y1, y2)

pts = defaultdict(int)

for s in segs:
    x1, y1, x2, y2 = s
    # Le vecteur directeur “unitaire”
    dx, dy = 0, 0

    if x1 != x2:
        dx  = -1 if x1 > x2 else 1
    if y1 != y2:
        dy  = -1 if y1 > y2 else 1

    pts[(x1, y1)] += 1
    while (x1, y1) != (x2, y2):
        x1, y1 = x1 + dx, y1 + dy
        pts[(x1, y1)] += 1

print(len(list(filter(lambda x: x > 1, pts.values()))))

Que je trouve assez satisfaisant.

Jour 6: Les poissons-lanternes

On rencontre des poissons-lanternes ! Stupéfait par le nombre, on décide de modéliser leur taux de croissance que l'on imagine être exponentiel ! Pour vérifier ça, on va faire l'hypothèse que chaque poisons-lanternes donne un nouveau poisson lanternes tous les 7 jours. Pourquoi ? Ben pourquoi pas. Les clés du traineau peuvent bien attendre, la curiosité scientifique ne peut pas !

I heard you like lanternefish !
Jour 6

Un poisson lanterne

Une dernière supposition, un poisson lanterne arrive à maturité en 2 jours. Oui, c'est pris au pif mais ça semble pas trop mal. Le sous-marin nous donne l'age (enfin l'état du compteur interne de gestation) des poisson-lanternes des alentours. Par exemple 3,4,3,1,2. Chaque jour ce compteur diminue de 1 et dès qu'un poisson passe en dessous de 0, il crée un nouveau poisson et son compteur se remet à 6.

Bon ben modélisons ça ! On nous demande de compter pour le nombre de poisson après 80 jours.

with open('input') as f:
    list_fish = map(int, f.readline().split(','))

for _ in range(80):
    list_fish = [f - 1 for f in list_fish]
    numberUnderZero = len(list(filter(lambda x: x == -1, list_fish)))
    list_fish = [6 if x < 0 else x for x in list_fish] + [8] * numberUnderZero

print(len(list_fish))

Simple comme bonjour. C'est littéralement l'algorithme de l'énoncé.

Difficulté 2, ça se complique. On nous demande de faire pareil mais pour 256. Si comme on suppose le nombre de poisson croît de manière exponentielle, alors en 256 jours on aura beaucoup trop de boissons ! On ne peut plus se permettre de compter les poissons un par un.

Mais on a seulement 9 états différents de poisson. Comptons ça plutôt !

from collections import Counter, defaultdict

with open('input') as f:
    fish = Counter(map(int, f.readline().split(',')))

for i in range(256):
    fish = defaultdict(int, {j - 1: nb for j, nb in fish.items()})
    fish[6] += fish[-1]
    fish[8] += fish[-1]
    fish[-1] = 0

print(Counter(fish).total())

Ah oui ! On aurait dû commencer par là, c'était plus simple en fait. Mais le problème suggérait une autre méthode de résolution. C'est pas bien grave. Continuons !

Jour 7: Le prochain repas d'un cachalot

Un cachalot nous prend pour son prochain repas et fonce vers nous ! L'énoncé parle d'une whale, qu'on devrait traduire par baleine mais le lien wikipédia redirige vers Sperm whale qui est ce que nous appelons un (grand) cachalot1.

Des crabes dans des petits sous-marins viennent à notre secours. Ils peuvent nous pousser pour aller plus vite, mais ils ont besoin d'être alignés pour ça. Et ils ont une quantité d'énergie vraiment limité.

On aimerait bien les aider à nous aider !

Pour ce problème, on a une liste de nombre correspondant à l'abscisse des petits sous-marins. On doit calculer le coût minimum pour que tous les sous-marins soient alignés sur la même abscisse.

def align(i, l):
    return sum(map(lambda x: abs(i - x), l))

with open('input') as f:
    list_pos = list(map(int, f.readline().split(',')))

min_, max_ = min(list_pos), max(list_pos)
cout = [align(i, list_pos) for i in range(min_, max_)]

print(min(cout))

Le coût d'alignement est la valeur absolue de la différence entre l'abscisse où est le sous-marin et là où il doit s'aligner. Le code est assez clair je pense.

Difficulté 2 ! Les crabes sont pas super ravis. Ça ne leur sert à rien car leur sous-marin ne consomme pas de manière linéaire mais plutôt quadratique !

Pour aller de 16 à 5, un sous-marin à besoin de 66 unités de carburant. Pour le premier centimètre, ça ne coûte qu'un. Pour le deuxième ça en coûte deux. Et ainsi de suite jusqu'au onzième qui coûte 11.

Bon ça ne change pas énormément, on doit remettre à jour notre calcul du coût. Pour cela, on peut utiliser la formule :

i=0ni=n(n+1)2\sum_{i=0}^n i = \frac{n (n + 1)}{2}
def align(i, l):
    return sum(map(lambda x: abs(i - x) * (abs(i - x) + 1) // 2, l))

Et voilà ! Les crabes nous sortent de cette situation un peu délicate. 🦀

Conclusion

Voilà qui est fait pour la première semaine ! 🥳

Le niveau pour l'instant est tout à fait abordable pour un débutant et les exercices sont très ludiques. La mise en contexte est absurde mais rigolote.

On peut facilement comparer ces exercices à ceux de France-IOI ou de Prologin.

Je reviendrais dans quelques semaines pour vous parler de la semaine 2 de l'Advent of Code. Mon rythme de publication est très faible alors ne vous étonnez pas si vous n'avez pas de nouvelles avant le mois de Mars.

Divulgâchage, ça va se corser un peu !


  1. C'est tout de même plus classe que baleines à spermes ! Désolé d'utiliser une langue évoluée.