Miximum
J'ai participé à l'AdventOfCode 2021
Cette année, j'ai participé pour la première fois à l'AdventOfCode (AoC pour les intimes). En voici un petit compte-rendu un peu en vrac.
Le calendrier de l'avent des gens qui codent
L'AoC est un site existant depuis 2015 et étonnamment porté par une seule personne. Chaque année, du 1er au 25 décembre, un nouveau « puzzle algorithmique » est proposé, qu'il faut résoudre en écrivant un petit programme.
Chaque puzzle consiste en fait à trouver la solution à un problème nécessitant la mise en œuvre de calculs ou d'algorithmes plus ou moins complexes à effectuer sur une source de donnée textuelle.
La difficulté augmente graduellement et si les premiers problèmes restent relativement triviaux, ils peuvent devenir vraiment ardus et nécessiter la mise en œuvre de compétences avancées sur la fin.
Un des aspects sympathique de l'AoC est que les puzzles sont scénarisés. Cette année, l'on suivait un sous-marin parti dans les abysses à la recherche des clés du traîneau du père Noël, en rencontrant toute une faune aquatique. C'est anecdotique mais ça rende l'exercice plus convivial.
Cette année, j'ai réussi à participer de manière à peu près régulière en négligeant mon hygiène personnelle et mes obligations familiales et domestiques gérant mon temps de manière efficace.
L'intérêt des deux puzzles
Chaque puzzle est en fait constitué de deux parties. Il faut résoudre la première pour débloquer la seconde, mais l'entrée du problème reste la même dans les deux cas.
L'intérêt est qu'on ne sait jamais à l'avance sur quoi va porter la seconde partie.
Parfois, il s'agira de complexifier l'algorithme mis en place pour la partie une, ou bien les contraintes plus importantes invalideront complètement la première solution et nécessiteront la mise en place d'un algorithme complètement différent.
Ainsi, une solution brute, algorithmiquement inefficace mais rapide à coder permettra de résoudre la partie 1, mais pas la partie 2… ou parfois si.
Ce qui conduit parfois à bien se poser la question sur l'approche à employer pour résoudre un problème. Faut-il perdre du temps à implémenter une solution plus élégante pour la partie une, sachant que peut-être la solution brute ne fonctionnera pas pour la partie deux ?
Soumission des solutions
Contrairement à d'autres systèmes similaires (Prologin, Codingame), les joueurs ne soumettent pas du code qui sera compilé par la plateforme mais directement la solution, généralement sous forme de nombre.
Il est donc possible de résoudre les problèmes dans le langage qui vous chante, même le plus exotique. Certains puzzles se prêtent même parfois à une résolution à la main sur papier.
Cela signifie aussi que votre algo n'est pas contraint par des ressources en temps ou en mémoire. Il est ainsi possible de coder un programme relativement inefficace qui tournera toute la nuit pour trouver la bonne solution.
Participer à plusieurs
L'intérêt de l'événement est de participer à plusieurs.
Ainsi, on trouve sur le Reddit dédié une importante communauté de passionnés qui postent leur solution du jour, ainsi que des visualisations des problèmes assez impressionnantes, des questions, des blagues, etc.
C'est très enrichissant — une fois qu'on a résolu un problème parfois de manière assez crade — d'aller consulter les solutions des autres.
Quand certains font en trois lignes brillantes d'élégance ce que tu fais en cinquante, eh bien ! c'est enrichissant, quoique douloureux pour l'égo.
Cette année, j'ai pu échanger sur un forum avec quelques membres de la communauté Beta.gouv.fr et c'était très sympa pour se motiver.
D'ailleurs, je ne dis pas merci à Agnès de m'avoir motivé à participer, m'amenant ainsi à perdre d'innombrables heures de temps libre ce mois-ci.
Le leaderboard
L'AoC présente un leaderboard présentant un classement des participants. Ce classement s'effectue sur un seul critère : le temps de résolution du problème du jour.
C'est encore une fois très douloureux pour l'égo de constater qu'il existe des humains capables de résoudre un problème de code complexe en moins de temps qu'il ne t'en faut simplement pour lire et comprendre l'énoncé.
Au delà de ça, je n'aime pas le concept de classement. Comme si notre monde n'était pas assez compétitif.
Par ailleurs, quitte à établir un classement, je trouverais plus pertinent de prendre en compte d'autres critères comme la lisibilité du code.
Trivial pour quelqu'un, impossible pour d'autres
En consultant les forums, on s'aperçoit vite qu'un problème qui s'avère trivial pour quelqu'un peut s'avérer insoluble pour d'autres.
De fait, parfois, certains puzzles nécessitent une bonne dose de réflexion, mais d'autres fois, il faut simplement appliquer un algo existant, et si on ne le connaît pas, eh bien… Tout le monde ne peut pas être Dijkstra.
Heureusement, de nombreux participants rédigent des compte-rendus détaillés de leurs solutions, et c'est une bonne façon de progresser.
Quelques problèmes particulièrement intéressants
Voici une petite sélection en vrac des problèmes, concepts, algorithmes et solutions intéressants que j'ai pu repérer cette année. Tout ça est un peu en vrac, j'espère que vous ne m'en voudrez pas.
Programmation fonctionnelle et expressivité du code
J'ai travaillé avec Python, langage dont j'apprécie l'expressivité et la richesse fonctionnelle.
Python permet de mettre en œuvre différentes approches pour résoudre un même problème.
Par exemple, le problème du jour 1 nécessitait de parcourir une liste de nombres et de compter combien d'éléments de la liste étaient supérieurs à la valeur précédente.
Il est possible d'utiliser une approche traditionnelle à base de boucle.
numbers = [199, 200, 208, …, 250]
numbers_length = len(numbers)
counter = 0
for i in range(1, numbers_length):
if numbers[i] > numbers[i - 1]:
counter += 1
print(counter)
On peut aussi tirer partie de la richesse de la librairie standard et adopter une approche plus fonctionnelle.
from itertools import pairwise
numbers = [199, 200, 208, …, 250]
pairs = pairwise(numbers)
increasing_pairs = filter(lambda pair: return pair[1] > pair[0], pairs)
counter = len(list(increasing_pairs))
print(counter)
En fonction des cas, exprimer une solution d'une manière fonctionnelle peut être plus élégant… ou complètement illisible.
Je remercie également Agnès (encore elle) de m'avoir fait découvrir le très riche module more-itertools.
Calculs d'écoulement et Parcours en largeur
Anecdote : le problème du jour 9 m'a amené à mettre très exactement en œuvre l'algorithme sur lequel je travaillais côté boulot.
Le problème du jour 9 était constitué d'une grille de nombres représentant des mesures d'élévations sur un découpage de terrain :
2199943210
3987894921
9856789892
8767896789
9899965678
L'entrée est construite de telle manière que le terrain ainsi modélisé était constitué de différents bassins séparés par des murs (valeur 9). Voici, pour aider à la visualisation, la même entrée mais en ne gardant que les « murs », et en ajoutant des 9 pour représenter les bordures de terrain.
999999999999
9 999 9
9 9 9 9 9
99 9 9 9
9 9 99
99 999 9
999999999999
Chaque « bassin » ainsi formé comportait un (et un seul) « point le plus bas » qu'il fallait trouver dans la partie 1. La partie 2 nécessitait de calculer la taille de chaque bassin.
Ce problème pouvait être résolu en mettant en place deux algorithmes notables : un calcul d'écoulement, et un parcours en largeur.
1/ Le calcul d'écoulement est fréquemment mis en œuvre dans les calculs hydrologiques au sein des applications cartographiques, par exemple pour répondre aux questions suivantes : s'il pleut dans une région, ou va s'écouler l'eau, quelles zones seront inondées, etc ?
Il existe plusieurs façons d'estimer les directions d'écoulement en partant de modèles topologiques. L'algorithme le plus trivial s'appelle « D8 » : on découpe le terrain en « grille » d'élévation et pour chaque case, on considère que l'eau tombant sur cette case s'écoulera vers l'une des 8 cases adjacentes présentant la plus forte pente descendante.
2/ En combinant D8 avec un parcours en largeur (Breadth-First Search, ou BFS en anglais), on peut calculer les bassins versants de manière approximative.
De manière résumée, le parcours en largeur consiste à considérer une zone constituée d'un point unique. Puis, on explore la zone itérativement en considérant tous les points adjacents à la zone répondant à un certain critère.
Tant qu'on trouve de nouveaux points, on les ajoute au bassin en cours, puis on recommence à chercher de nouveaux points, etc.
On s'arrête quand il n'y a plus de points à ajouter.
En ne gardant que les portions de code utile, voici un exemple d'implémentation en Python.
def expand_basin(points):
"""À partir d'une liste de coordonnées, considère les points aux alentours qui remplissent un certain critère."""
new_points = []
for x, y in points:
# Pour tous les points autour de (x,y), si le point
# remplit la condition, on l'ajoute à new_points
# …
return new_points
def compute_basin(x, y):
"""Calcule un passin en appliquant un parcours en largeur sur un point de départ."""
basin = [(x, y)]
new_points = [(x, y)]
while len(new_points) > 0:
new_points = expand_basin(new_points)
# On ne considère que les points qui ne faisaient
# pas déjà partie du bassin.
new_points = list(set(new_points) - set(basin))
# On ajoute les nouveaux points à la zone du bassin
basin += new_points
return basin
low_points = find_low_points()
basins = {}
for x, y in low_points:
basins[(x, y)] = compute_basin(x, y)
Numpy, le bon génie
De nombreux problèmes nécessitent de travailler sur des grilles, ou tableaux à deux dimensions.
C'est le cas du jour 9, comme on vient de le voir, ou du jour 11.
Le jour 11 nécessitait de travailler sur une grille représentant des pieuvres dont le niveau d'énergie augmente. Chaque « case » de la grille représente le niveau d'énergie (entre 0 et 9) d'une pieuvre.
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526
Chaque jour, le niveau d'énergie de chaque pieuvre augmente de 1.
En python standard, on pourrait ranger les nombres dans un tableau d'entiers à deux dimensions (une liste de listes, en fait), et incrémenter chaque valeur dans une double boucle.
values = […] # tableau à deux dimensions
for x in range(0, 10):
for y in range(0, 10):
values[y][x] += 1
Numpy est une bibliothèque issue du monde scientifique optimisée pour le calcul matriciel, et permet donc d'effectuer des opérations groupées sur des tableaux à n dimensions.
On peut par exemple extraire des lignes, des colonnes ou des sous-ensembles arbitraires, avec des fonctions d'indexation très pointues).
Ainsi, incrémenter chaque valeur du tableau devient trivial.
import numpy as np
data = '''
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526
'''.strip().splitlines()
values = np.array(list(map(list, data)), dtype=int) # Frime totale, ne faites pas ça à la maison
values += 1
print(values)
[[6 5 9 4 2 5 4 3 3 4]
[3 8 5 6 9 6 5 8 2 2]
[6 3 7 5 6 6 7 2 8 4]
[7 2 5 2 4 4 7 2 5 7]
[7 4 6 8 4 9 6 5 8 9]
[5 2 7 8 6 3 5 7 5 6]
[3 2 8 7 9 5 2 8 3 2]
[7 9 9 3 9 9 2 2 4 5]
[5 9 5 7 9 5 9 6 6 5]
[6 3 9 4 8 6 2 6 3 7]]
Numpy est un outil très technique, à la documentation parfois très cryptique, mais l'AoC fut une très bonne occasion pour moi d'en apprendre plus.
Autre exemple : dans le problème qui nous occupe, les pieuvres dont l'énergie atteint 10 flashent. Combien de pieuvres flashent à un instant donné ?
Encore une fois, Numpy rends cette tâche triviale, en proposant les fonctions d'indexation qui ressemblent presque à de la magie.
>>> values += 1
array([[ 7, 6, 10, 5, 3, 6, 5, 4, 4, 5],
[ 4, 9, 6, 7, 10, 7, 6, 9, 3, 3],
[ 7, 4, 8, 6, 7, 7, 8, 3, 9, 5],
[ 8, 3, 6, 3, 5, 5, 8, 3, 6, 8],
[ 8, 5, 7, 9, 5, 10, 7, 6, 9, 10],
[ 6, 3, 8, 9, 7, 4, 6, 8, 6, 7],
[ 4, 3, 9, 8, 10, 6, 3, 9, 4, 3],
[ 8, 10, 10, 4, 10, 10, 3, 3, 5, 6],
[ 6, 10, 6, 8, 10, 6, 10, 7, 7, 6],
[ 7, 4, 10, 5, 9, 7, 3, 7, 4, 8]])
>>> # Compare toutes les valeurs de la grille d'un seul coup
>>> values == 10
array([[False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, True],
[False, False, False, False, False, False, False, False, False, False],
[False, False, False, False, True, False, False, False, False, False],
[False, True, True, False, True, True, False, False, False, False],
[False, True, False, False, True, False, True, False, False, False],
[False, False, True, False, False, False, False, False, False, False]])
>>> # Combien de pieuvres sont en train de flasher ?
>>> np.count_nonzero(values == 10)
13
Poursuivons : quand une pieuvre flashe, les pieuvres qui l'entourent voient leur niveau d'énergie augmenter de 1.
Encore une fois, Numpy rends la tâche triviale grâce à ses fonctions d'indexation qui permettent d'extraire des « portions » d'un tableau, et qui sont en fait des « vues » sur le tableau d'origine. Il devient ainsi très facile de manipuler des sous-ensembles de tableau.
>>> # Soient x, y les coordonnées d'une pieuvre qui flashe
>>> x, y = 1, 7
>>> window = values[y - 1:y + 2, x - 1:x + 2]
array([[ 4, 3, 9],
[ 8, 10, 10],
[ 6, 10, 6]])
>>> # On incrémente toutes les valeurs de la sélection
>>> window += 1
array([[ 5, 4, 10],
[ 9, 11, 11],
[ 7, 11, 7]])
>>> # Ce faisant, nous avons incrémenté les valeurs d'origine
>>> values
array([[ 7, 6, 10, 5, 3, 6, 5, 4, 4, 5],
[ 4, 9, 6, 7, 10, 7, 6, 9, 3, 3],
[ 7, 4, 8, 6, 7, 7, 8, 3, 9, 5],
[ 8, 3, 6, 3, 5, 5, 8, 3, 6, 8],
[ 8, 5, 7, 9, 5, 10, 7, 6, 9, 10],
[ 6, 3, 8, 9, 7, 4, 6, 8, 6, 7],
[ 5, 4, 10, 8, 10, 6, 3, 9, 4, 3],
[ 9, 11, 11, 4, 10, 10, 3, 3, 5, 6],
[ 7, 11, 7, 8, 10, 6, 10, 7, 7, 6],
[ 7, 4, 10, 5, 9, 7, 3, 7, 4, 8]])
Oui mais attendez ! Si la pieuvre se trouve en bordure, nous allons avoir des problèmes ?!?
Numpy.pad à la rescousse ! Pad est une fonction permettant de compléter certaines dimensions du tableau avec des valeurs. D'une manière triviale, on peut ajouter une « bordure » de constante autour de notre grille, et ainsi se débarrasser des exceptions qu'elles constituent.
>>> # Ajoute une bordure de constante adéquante
>>> padded = np.pad(values, pad_width=1, constant_values=11)
[[11 11 11 11 11 11 11 11 11 11 11 11]
[11 7 6 10 5 3 6 5 4 4 5 11]
[11 4 9 6 7 10 7 6 9 3 3 11]
[11 7 4 8 6 7 7 8 3 9 5 11]
[11 8 3 6 3 5 5 8 3 6 8 11]
[11 8 5 7 9 5 10 7 6 9 10 11]
[11 6 3 8 9 7 4 6 8 6 7 11]
[11 4 3 9 8 10 6 3 9 4 3 11]
[11 8 10 10 4 10 10 3 3 5 6 11]
[11 6 10 6 8 10 6 10 7 7 6 11]
[11 7 4 10 5 9 7 3 7 4 8 11]
[11 11 11 11 11 11 11 11 11 11 11 11]]
>>> # On peut utiliser les valeurs d'indexation pour récupérer les valeurs d'origine
>>> padded[1:-1,1:-1]
array([[ 7, 6, 10, 5, 3, 6, 5, 4, 4, 5],
[ 4, 9, 6, 7, 10, 7, 6, 9, 3, 3],
[ 7, 4, 8, 6, 7, 7, 8, 3, 9, 5],
[ 8, 3, 6, 3, 5, 5, 8, 3, 6, 8],
[ 8, 5, 7, 9, 5, 10, 7, 6, 9, 10],
[ 6, 3, 8, 9, 7, 4, 6, 8, 6, 7],
[ 4, 3, 9, 8, 10, 6, 3, 9, 4, 3],
[ 8, 10, 10, 4, 10, 10, 3, 3, 5, 6],
[ 6, 10, 6, 8, 10, 6, 10, 7, 7, 6],
[ 7, 4, 10, 5, 9, 7, 3, 7, 4, 8]])
Enfin, lorsque les pieuvres flashent, leur niveau d'énergie retombe à zéro.
Franchement, Numpy rends cette tâche tellement aisée que c'en est presque injuste.
>>> # RaZ les pieuvres qui flashent
>>> values[values == 10] = 0
array([[7, 6, 0, 5, 3, 6, 5, 4, 4, 5],
[4, 9, 6, 7, 0, 7, 6, 9, 3, 3],
[7, 4, 8, 6, 7, 7, 8, 3, 9, 5],
[8, 3, 6, 3, 5, 5, 8, 3, 6, 8],
[8, 5, 7, 9, 5, 0, 7, 6, 9, 0],
[6, 3, 8, 9, 7, 4, 6, 8, 6, 7],
[4, 3, 9, 8, 0, 6, 3, 9, 4, 3],
[8, 0, 0, 4, 0, 0, 3, 3, 5, 6],
[6, 0, 6, 8, 0, 6, 0, 7, 7, 6],
[7, 4, 0, 5, 9, 7, 3, 7, 4, 8]])
Numpy est tellement riche que si vous manipulez régulièrement des tableaux ou matrices, ça vaut le coup d'y jeter un œil.
Éviter les exponentielles et explosions combinatoires
Le problème du jour 6 nécessitait de compter une population de poissons-lanternes se reproduisant exponentiellement.
Chaque poisson se reproduit tout les 7 jours. Chaque bébé poisson nécessite 9 jours pour sa première reproduction, ensuite il est considéré comme un poisson adulte et se reproduit également tous les 7 jours.
La tâche consiste à compter le nombre de poissons au delà d'une certaine durée.
La description du problème se focalise sur le cycle de vie du poisson. Il serait donc tentant de simuler chaque poisson individuellement.
# Quelque chose comme ça
class Fish:
def __init__(self, initial_counter):
self.counter = initial_counter
…
fishes = [Fish(counter) for counter in … ] # données d'entrée du problème
for day in range(0, 80):
fishes = simulate(fishes)
print(len(fishes))
Cette approche, quoique peu efficace, fonctionne à peu près pour la partie 1 ou la simulation s'effectue sur peu d'itérations (80 jours). En revanche, la même simulation, sur les 256 jours de la partie 2, est tout bonnement impossible car elle nécessiterait des péta-octets de mémoire.
C'est le problème avec les exponentielles : quand ça augmente, ça augmente vite !
La clé du problème consiste à changer de point de vue : au lieu de compter les poissons individuellement, il « suffisait » de remarquer que rien ne distingue deux poissons, sauf la durée avant leur prochaine reproduction.
Par conséquent, plutôt que de compter les poissons, on pouvait compter les « nombres de poissons à tel stade du cycle de reproduction ».
# Il y a trois poissons à zéro jours de l'accouchement,
# 5 poissons à 1 jour, etc.
fishes = [3, 5, 2, …]
for day in range(0, 256):
# la taille du tableau n'augmente jamais
# (mais les nombres à l'intérieur, oui)
fishes = simulate(fishes)
print(sum(fishes))
Le problème du jour 14 était très similaire dans son principe.
Il s'agissait de simuler une chaîne de caractères augmentant de manière exponentielle.
Ainsi, la chaîne est constituée de lettres (e.g « NNCB ») et il faut la faire grandir selon un ensemble de règles à base de paires.
Par exemple, chaque paire de caractères « NN » devient « NCN », « NC » devient « NCB », etc.
La solution naïve consiste à construire la nouvelle chaîne autant d'étapes qu'il est nécessaire en appliquant les règles à chaque fois.
val = 'NNCB'
rules = … # données d'entrée du problème
for i range(0, 10): # nombre d'itérations requises par le problème
val = apply_rules(val, rules)
Malheureusement, la chaîne grossit alors de manière exponentielle et au bout d'un très petit nombre d'étapes, la mémoire de la machine n'est plus capable de la contenir.
L'astuce consistait à se rendre compte qu'il était inutile de conserver la trace de la chaîne complète, puisqu'on ne s'intéressait qu'aux paires, et qu'il n'existait qu'un nombre de paires distinctes limitées.
Ainsi, 150 paires « NN » disparaîtraient pour donner 150 paires « NC » et 150 paires « CN », etc.
from collections import Counter
pairs = ['NN', 'NC', 'CB']
counter = Counter(pairs)
for i in range(0, 10):
counter = apply_rules(counter, rules)
En évitant de compter les valeurs individuelles, mais en se concentrant sur ce qui les distingue, on évite ainsi les explosions combinatoires.
C'est aussi l'occasion de découvrir la classe Counter de python, une sous-classe de dict dédiée au comptage des éléments contenus.
Minimiser la somme des distances avec la médiane
Jour 7 : des crabes sont répartis sur une ligne horizontale. L'objectif est de trouver la position « x » telle qu'il faut minimiser la somme des déplacements des crabes vers cette position.
De manière naïve, on peut effectuer une boucle très inefficace :
crab_positions = [0, 5, 0, 18, 50, …]
def compute_cost(x):
cost = sum(abs(p - x) for p in crab_positions)
return cost
costs = [compute_cost(x) for x in range(0, 100)]
min_cost = min(costs)
best_position = costs.index(min_cost)
print(best_position)
On peut aussi, comme je l'ai fait trop tard, se rappeler que la médiane est la valeur qui permet de minimiser la somme des différences.
from statistics import median
crab_positions = [0, 5, 0, 18, 50, …]
best_position = median(crab_positions)
print(best_position)
Duh !
Files et piles, l'algo c'est parfois utiliser la bonne structure de données
L'algorithmie, parfois, c'est simplement utiliser la bonne structure de données pour résoudre un problème.
Ainsi, durant le jour 10, il fallait implémenter un vérificateur syntaxique de parenthèses, crochets, chevrons… enchevêtrés.
Par exemple, la chaîne [({(<(())[]>[[{[]{<()<>> est elle « correcte », c'est à dire que chaque symbole ouvrant est-il associé à un symbole fermant dans le bon ordre ?
C'est un problème qui est très facile, si on utilise la bonne structure de données, à savoir une pile.
En algorithmie, une pile est une structure qui permet de stocker et récupérer des données. Quand une donnée est ajoutée, elle est ajoutée à la fin (en haut de la pile) et quand une donnée est récupérée, elle est supprimée à la fin (ou en haut) de la pile.
C'est ce qu'on appelle le Last-in, First-out, ou LIFO. À ne pas confondre avec les files, ou l'on récupère les données dans leur ordre d'insertion (First-in, First-out, ou LIFO).
OPENING = ('(', '[', '{', '<')
CLOSING = (')', ']', '}', '>')
PAIRS = dict(zip(OPENING, CLOSING))
def find_illegal_char(line):
"""Retourne le premier caractère invalide."""
stack = []
for c in line:
if c in OPENING:
stack.append(c) # ajoute à la fin
else:
last_char = stack.pop() # récupère et supprime depuis la fin
if PAIRS[last_char] != c:
return c
return None
Quand on trouve un symbole ouvrant, on l'ajoute en haut de la pile. Quand on trouve un caractère fermant, en revanche, on vérifie qu'il correspond bien au caractère ouvrant du haut de la pile, qu'on « dépile » dans la foulée.
Récursivité ou pile maison
Jour 12. On arrive tranquillement aux problèmes un peu plus complexes, voire carrément retors.
Le jour 12 consistait à récupérer une liste de caves connectées entre elles, et de compter le nombre de chemins reliant une cave de départ et une cave d'arrivée. Il fallait prendre en compte le fait que certaines caves étaient empruntables une seule fois ou plusieurs fois.
Exemple de représentation d'un réseau de cavernes :
start
/ \
c--A-----b--d
\ /
end
Comment approcher ce problèmes ?
1/ La structure idéale pour travailler sur ce type de données est le graphe. Un graphe est constitué de nœuds (les caves) et d'arêtes (les chemins reliant les caves).
J'ai appris qu'il existait une lib python pour gérer les graphes, mais je me suis contenté d'une implémentation maison somme-toutes assez triviale.
from collections import defaultdict
class Graph:
def __init__(self):
self._neighbours = defaultdict(list)
def connect(self, n1, n2):
"""Connecte deux caves entre elles."""
self._neighbours[n1].append(n2)
self._neighbours[n2].append(n1)
def neighbours(self, n):
"""Renvoie la liste des caves accessibles depuis une cave."""
return self._neighbours[n]
def is_big(self, n):
"""Grosse ou petite cave ?
Le problème nécessite de distinguer les grande caves
(indiquées en majuscules) des petites.
"""
return n.upper() == n
data = '''
start-A
start-b
A-c
A-b
b-d
A-end
b-end
'''.strip().splitlines()
graph = Graph()
for line in data:
n1, n2 = line.split('-')
graph.connect(n1, n2)
Ensuite, il faut construire et compter la liste complète de chemins reliant start à end.
Pour cela, nous allons utiliser un parcours en profondeur, associé à une pile.
Contrairement au parcours en largeur, que nous avons déjà vu plus haut, le parcours en profondeur (Depth-First Search, ou DFS) consiste à explorer un graphe en allant le plus loin possible avant de revenir sur ses pas.
La stratégie est la suivante : quand je me trouve dans une cave, je considère toutes les caves que je peux visiter. Je les mets dans ma pile de caves à visiter. Ensuite, je vais vers la première cave, et je recommence.
C'est à dire que tant que je peux avancer, je ne reviens pas en arrière. Quand je ne peux plus avancer (parce que j'ai atteint la destination, ou que je suis dans une impasse), je reviens en arrière en dépilant.
(Le code suivant n'est sûrement pas le plus propre, mais j'ai bien galéré sur cette journée.)
current_path = []
next_caves = ['start']
nb_paths = 0
while len(next_caves) > 0:
# J'emprunte la première caverne que je peux visiter
current = next_caves[-1]
current_path.append(current)
new_nexts = []
if current == 'end':
nb_paths += 1
else:
# J'ajoute à ma pile toutes les cavernes que je peux
# visiter d'ici
for next in graph.neighbours(current):
if graph.is_big(next) or next not in current_path:
new_nexts.append(next)
if len(new_nexts) > 0:
next_caves += new_nexts
else:
# Je suis dans une impasse
# Je reviens en arrière en dépilant
while(len(current_path) > 0 and len(next_caves) > 0 and current_path[-1] == next_caves[-1]):
current_path.pop()
next_caves.pop()
print(nb_paths)
Recherche de plus court chemin, Dijkstra et PriorityQueues
Le jour 15 est un pur problème de recherche de plus court chemin.
On travaille avec une grille de nombre, qui représente une caverne à traverser.
Chaque nombre indique le coût nécessaire pour traverser la case.
Il faut trouver un chemin qui permet d'aller d'en haut à gauche jusqu'en bas à droite en minimisant le coût de la traversée.
Trouver un chemin en minimisant un coût de déplacement ? Il n'y a pas à réfléchir, c'est tout de suite l'algorithme de Dijkstra qui doit venir à l'esprit.
L'algorithme de Dijkstra (après toutes ces années, je ne sais toujours pas comment ça se prononce) est un parcours en largeur mais en intégrant une notion de coût de déplacement.
J'ai vu des participants résoudre le problème en 3 ou 4 lignes en utilisant des bibliothèques existantes, mais j'ai codé une solution maison (pas de quoi en être fier, d'ailleurs).
from queue import PriorityQueue
data = '''
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
'''.strip().splitlines()
costs = np.array(list(map(list, data)), dtype=int)
# Les points de départ et d'arrivée
start = (0, 0)
goal = (9, 9)
# Notre frontière d'exploration actuelle (une liste de coordonnées)
# C'est une liste ordonnée, avec les coordonnées les moins coûteuses en premier
frontier = PriorityQueue()
frontier.put((0, start))
# Pour chaque case explorée, on conserve la direction
# et le coût qui nous ont permis de l'atteindre
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
# Tant qu'il reste des cases à explorer
while not frontier.empty():
# On va toujours explorer la case la plus accessible en premier
_, current = frontier.get()
if current == goal:
break
# On considère les cases aux alentours
for next in neighbours(costs, current):
# Pour chaque voisin, on calcule le coût d'exploration
new_cost = cost_so_far[current] + cost(costs, current, next)
# Si on n'a jamais exploré le voisin…
# ou si on peut l'explorer à un coût moindre,
# on le rajoute à la frontière
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put((priority, next))
came_from[next] = current
result = cost_so_far[goal]
print(result)
C'était pour moi l'occasion de découvrir les PriorityQueue, fournie par la bibliothèque standard de Python, et qui constituent une file ordonnée.
La meilleure ressource pour comprendre le fonctionnement de Dijkstra.
Gestion des nombres binaires
Le jour 16 nécessitait de manipuler des nombres binaires.
Par exemple, il fallait récupérer une chaîne hexadécimale, la convertir en bits, effectuer une certaine opération en fonction de la valeur décimale des trois premiers bits, etc.
Une fois ces opérations réalisées, le problème en lui-même n'avait pas beaucoup d'intérêt.
Par conter, manipuler des chaînes de bits n'est pas si facile.
Heureusement, j'ai découvert l'excellente librairie bitstring qui rends la chose triviale.
>>> from bitstring import BitArray
>>> bits = BitArray(hex='C200B40A82')
>>> bits
BitArray('0xc200b40a82')
>>> bits.bin
'1100001000000000101101000000101010000010'
>>> bits[0:3]
BitArray('0b110')
>>> bits[0:3].uint
6
Les nombres triangulaires
Plusieurs problèmes cette année impliquaient de calculer la somme des x premier nombre entiers.
Si on ne le sait pas, on fait ainsi, et c'est très inefficace :
def somme_des_premiers_nombres(x):
return sum(range(1, x + 1))
On peut aussi savoir que ce type de nombre porte un nom : ce sont des nombres triangulaires. On peut calculer trivialement le n-ième nombre triangulaire grâce à la formule : n * (n + 1) / 2.
Les arbres binaires
Le problème du jour 18 était tout bonnement insoluble si l'on n'utilisait pas la structure de données adéquate.
Le problème consistait à réaliser des opérations arbitraires sur des valeurs farfelues constitués de paires, chaque côté d'une paire pouvant être constituée d'un nombre, ou d'une nouvelle paire.
Exemples de paires avec des niveaux d'imbrications plus ou moins importants :
[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]
Additionner deux paires revenait à constituer une nouvelle paire contenant les deux sous-paires, sachant qu'au delà d'un certain niveau d'imbrication, la paire trop profonde devait être éclatée et ses valeurs réparties sur les paires précédentes ou suivantes.
Pour de telles opérations, rien ne vaut un arbre binaire.
Un arbre binaire est une espèce de graphe constitué d'un nœud racine, et chaque nœud est relié à deux sous-nœuds, chaque sous-nœud lui-même relié à deux enfants, etc. jusqu'aux extrémités qu'on appelle les feuilles.
(De manière pas très avisée, un arbre est généralement représenté avec la racine vers le haut et les feuilles vers le bas.)
En stockant la donnée du problème dans un arbre binaire, on rends les opérations plus faciles grâce à la récursivité. Par exemple, comment calculer la profondeur d'un arbre ? Eh bien, c'est la profondeur du sous-arbre + 1…
class Leaf:
def __init__(self, val):
self.val = val
def depth(self):
return 0
class Pair:
def __init__(self, left, right):
# Leaf or Pair
self.left = left
self.right = right
def depth(self):
left_depth = self.left.depth()
right_depth = self.right.depth()
return 1 + max(left_depth, right_depth)
Voici un lien vers le code complet de ma solution, si ça vous intéresse.
Programmation dynamique
Le problème du jour 21 était un cas type d'un type de problème relevant de la programmation dynamique.
(Le nom est un peu historique, il n'y a pas grand-chose de particulièrement « dynamique » là-dedans, n'y faites pas trop gaffe.)
Résumé du problème : deux joueurs lancent successivement des dès pour faire avancer leur pion sur un plateau circulaire, gagnant ainsi des points. Le jeu s'arrête dès qu'un joueur atteint un certain score (21).
Parmi toutes les combinaisons possibles et imaginables de lancer de dès sur toute la durée de la partie, combien permettaient au joueur 1 de gagner ?
La perversité du problème est ici : chaque tour, au lieu de lancer un dé-9 (un dé avec des valeurs de 1 à 9), les joueurs lancent 3 fois un dé-3 (valeurs de 1 à 3).
Chaque tour, chaque joueur génère 3 *3 * 3 = 27 combinaisons uniques possibles de lancers de dés. Si l'on considère qu'il faut en moyenne 10 tours pour finir une partie, cela nous donne un nombre de parties uniques tout bonnement invraisemblable : aux alentours de 27^20 = 4,239115828×10²⁸.
Cela semble tout bonnement impossible d'évaluer chacune des ces possibilités unique, alors comment approcher le problème ?
Il fallait remarquer deux choses :
1/ de manière théorique, on peut résoudre le problème en le découpant en sous-problèmes.
2/ s'il existe un nombre quasi-infini de parties uniques possibles, il y a en revanche un nombre très limité d'états distincts dans lequel peut se retrouver le plateau de jeu.
Voyons cela plus en détail.
Découper le problème en sous-problèmes
Comment calculer le nombre de parties uniques possibles permettant au joueur 1 de gagner à partir d'un état de plateau donné ? (par exemple l'état de départ)
On peut le faire « facilement » : c'est la somme des combinaisons gagnantes pour chacune des 27 possibilités uniques de lancers de dés. On peut le calculer grâce à une fonction récursive (qui s'appelle elle-même).
from itertools import product
def play(pos, score, roll):
"""Compute the new score depending on the dice roll."""
new_pos = ((pos - 1 + roll) % 10) + 1
new_score = score + new_pos
return new_pos, new_score
def count_wins(player, pos0, score0, pos1, score1):
"""Pour un état donné, combien de combinaisons uniques permettent à chaque joueur de gagner ?"""
# Si un jouer dépasse 21, il n'y a qu'une possibilité
# puisqu'il a déjà gagné.
if score0 >= 21:
return 1, 0
elif score1 >= 21:
return 0, 1
# Le nombre de parties uniques gagnantes est égal
# au total des parties uniques gagnantes pour chaque lancer
# de dé possible.
wins = [0, 0]
for rolls in product(range(1, 4), repeat=3):
# À qui le tour de jouer ?
if player == 0:
# Calcule le nouveau score du joueur
new_pos, new_score = play(pos0, score0, sum(rolls))
# Calcule les parties gagnantes pour le sous-état
wins0, wins1 = count_wins(1, new_pos, new_score, pos1, score1)
else:
new_pos, new_score = play(pos1, score1, sum(rolls))
wins0, wins1 = count_wins(0, pos0, score0, new_pos, new_score)
# On additionne le tout et basta
wins[0] += wins0
wins[1] += wins1
return wins
# Les positions de départ des deux joueurs
starts = [10, 4]
# Le joueur 0 commence, les deux scores sont à zéro
wins = count_wins(0, starts[0], 0, starts[1], 0)
print(max(wins))
Cet algorithme va simuler toutes les combinaisons possibles et renverra la bonne réponse. Il faudra simplement attendre quelques petits millions d'années !
Comme nous n'avons pas ce temps libre devant nous, attardons-nous sur la deuxième observation…
Les états possibles du plateau
Si vous observez bien le code ci-dessus, vous remarquez que la fonction count_wins va être appelée un nombre invraisemblable de fois avec les mêmes paramètres.
En effet, la fonction prends en paramètres le joueur dont c'est le tour de jouer, ainsi que le score et la position de chaque joueur.
Chaque joueur ne peut se trouver que sur une case allant de 1 à 10 et avoir un score de 0 à 30. La fonction ne peut donc être appelée qu'avec 2 * 10 * 31 * 10 * 31 = 192200 combinaisons de paramètres possibles ! Une paille !
De fait, lorsqu'un joueur, en lançant les dés, obtient par exemple les combinaisons uniques suivantes : (1, 2, 3), (3, 2, 1), (2, 1, 3), (3, 1, 2), (2, 2, 2), etc. toutes ces possibilités « s'effondrent » en un même résultat, puisque le score obtenu ne dépend que de la somme des trois dés, et pas de la valeur individuelle de chaque dé.
Par conséquent, une optimisation évidente est de mettre en cache le résultat de la fonction count_wins en fonction de ses paramètres. Étant donnée la typologie du problème, cela permet de faire passer la résolution de millions d'années à quelques millisecondes. Pas mal, non ?
from itertools import product
from functools import lru_cache
def play(pos, score, roll):
"""Compute the new score depending on the dice roll."""
new_pos = ((pos - 1 + roll) % 10) + 1
new_score = score + new_pos
return new_pos, new_score
# Mise en cache du résultat de la fonction
# Même pas besoin de gérer le cache nous-mêmes, python le
# fait pour nous.
@lru_cache(maxsize=None)
def count_wins(player, pos0, score0, pos1, score1):
"""Pour un état donné, combien de combinaisons uniques permettent à chaque joueur de gagner ?"""
# Si un jouer dépasse 21, il n'y a qu'une possibilité
# puisqu'il a déjà gagné.
if score0 >= 21:
return 1, 0
elif score1 >= 21:
return 0, 1
# Le nombre de parties uniques gagnantes est égal
# au total des parties uniques gagnantes pour chaque lancer
# de dé possible.
wins = [0, 0]
for rolls in product(range(1, 4), repeat=3):
# À qui le tour de jouer ?
if player == 0:
# Calcule le nouveau score du joueur
new_pos, new_score = play(pos0, score0, sum(rolls))
# Calcule les parties gagnantes pour le sous-état
wins0, wins1 = count_wins(1, new_pos, new_score, pos1, score1)
else:
new_pos, new_score = play(pos1, score1, sum(rolls))
wins0, wins1 = count_wins(0, pos0, score0, new_pos, new_score)
# On additionne le tout et basta
wins[0] += wins0
wins[1] += wins1
return wins
# Les positions de départ des deux joueurs
starts = [10, 4]
# Le joueur 0 commence, les deux scores sont à zéro
wins = count_wins(0, starts[0], 0, starts[1], 0)
print(max(wins))
Résumé
En résumé, la programmation dynamique consiste à :
- résoudre un problème récursivement comme une composition de sous-problèmes ;
- optimiser en évitant de résoudre plusieurs fois un même sous-problèmes.
Note : ce type de technique n'est utile que lorsque le nombre de sous-problèmes distincts est très inférieur au nombre de combinaisons qu'ils constituent.
Conclusion
Voilà pour ma conclusion sur l'AoC 2021. Je vais aller dormir quelque jours. Bonnes fêtes !