Retour sur L'AoC 2021 : Semaine 1

Avant de parler des exercices, je vous fais un retour rapide sur mon sentiment global après un petit mois.

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 !

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.

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.

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 :

gamma, epsi = 0, 0
total = 1

with open("input") as f:
    final = f.readline().strip()
    final = list(map(lambda x: 1 if x == '1' else 0, final))
    print(final)

    for line in f:
        for i, c in enumerate(line):
            if c == '1':
                final[i] += 1
        total += 1

gamma = int("".join(list(map(lambda x: '1' if total - x > x else '0', final))), 2)
epsi = int("".join(list(map(lambda x: '0' if total - x > x else '1', final))), 2)


print(epsi, gamma, gamma * epsi)

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 :

total = 1
number = []

with open("input") as f:
    for line in f:
        number.append(line.strip())

number_oxy = list(number)
number_co2 = list(number)


i = 0
while len(number_oxy) > 1 and i < len(number_oxy[0]):
    number_1 = len(list(filter(lambda x: x[i] == '1', number_oxy)))
    total = len(number_oxy)
    if number_1 >= total - number_1 :
        keep = '1'
    else:
        keep = '0'
    number_oxy = [ number for number in number_oxy if number[i] == keep]
    i += 1

i = 0
while len(number_co2) > 1 and i < len(number_co2[0]):
    number_0 = len(list(filter(lambda x: x[i] == '0', number_co2)))
    total = len(number_co2)
    if number_0 > total - number_0 :
        keep = '1'
    else:
        keep = '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)

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.

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

Ç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 !

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.

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 !

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 !

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) cachalot¹.

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 :

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. 🦀