Advent of code 2024
Cette année, je me motive pour participer à l'Advent of Code 2024. L'idée n'est pas de réaliser des performances particulières, mais plutôt d'apprendre une nouvelle chose chaque jour.
Voici un petit compte rendu des différents aspects des problèmes qui m'ont semblé dignes d'intérêt, et quelques astuces utilisées pour les résoudre.
Jour 1 : compter les occurrences d'une valeur
Dans ce problème, on nous donne deux colonnes de nombres. Il faut compter, pour chaque valeur de la colonne de gauche, le nombre d'apparition dans la colonne de droite.
Le score à retrouver est calculé en additionnant, pour chaque ligne, la multiplication entre le nombre de gauche et son nombre d'occurence à droite.
3 4
4 3
2 5
1 3
3 9
3 3
L'argorithme extrêmement brutal et basique pourrait s'écrire ainsi :
left, right = parse_data()
score = 0
for l in left:
counter = 0
for r in right:
if l == r:
counter += 1
score += l * counter
print(score)
Ce code fonctionne très bien, surtout que la taille des données d'entrée reste raisonnable.
Toutefois, c'est l'occasion de se rappeler que Python fournit de nombreux outils pour faciliter les tâches les plus courantes.
Ainsi, il existe un objet Counter dans la bibliothèque standard de Python.
from collections import Counter
left, right = parse_data()
counter = Counter(right)
score = 0
for l in left:
count = counter[l]
score += l * count
print(score)
On peut aussi décider d'utiliser un peu de programmation fonctionnelle et de tirer partie de la syntaxe python et des list comprehensions
.
from collections import Counter
left, right = parse_data()
counter = Counter(right)
score = sum([l * counter[l] for l in left])
print(score)
En vérité, le problème est trop trivial pour que l'usage de Counter
soit intéressant, dans la mesure ou les objets list
ont déjà une fonction count
…
left, right = parse_data()
score = sum([l * right.count(l) for l in left])
print(score)
Un dernier petit mot sur la préparation des données. En effet, les données sont… données… sous formes de colonnes. Or, toutes les primitives de lectures de fichier fonctionnent par lignes.
raw_data = """
3 4
4 3
2 5
1 3
3 9
3 3
""".strip().splitlines()
# À ce stade, on obtient une liste de chaînes de
# caractères qui contiennent les deux nombres.
# raw_data = ["3 4", "4 3", …, "3 3"]
# La ligne suivante se comprend ainsi :
# for line in raw_data Pour chaque ligne `line` dans `raw_data`
# - line.split()
# découpe la ligne aux espaces donc retourne deux
# entiers sous forme de chaîne
# - map(int, …)
# appelle la fonction `int` sur chaque valeur ainsi
# obtenue, e.g transforme "5" (str) en 5 (int)
# - list(map…
# consomme l'itérable pour obtenir une liste
pairs = [list(map(int, line.split())) for line in raw_data]
# À ce stade, la variable `numbers` vaut :
# [[3, 4], [4, 3], …, [3, 3]]
# Pour obtenir les colonnes, on utilise la primitive
# `zip` qui sert à agréger différents itérables
# `*pairs`: on « déplie » la liste `pairs` en X éléments
# indépendants qu'on passe à zip
# zip combine tous les premiers éléments entre eux, puis
# tous les seconds éléments, etc.
left, right = zip(*pairs)
# On obtient bien le résultat escompté
# left = [3, 4, 2, …, 3]
# right = [4, 3, 5, …, 3]
Jour 2 : pentes montantes ou descendantes
On travaille avec une liste de rapports, chacun constitué d'une séquence d'entiers.
Il faut compter les séquences strictement ascendantes ou descendantes.
Pour récupérer une liste d'entiers à partir d'une chaîne de caractère :
ints = list(map(int, numbers_str.split()))
On peut donc traiter les données d'entrées facilement :
with open("inputs/day_02.txt") as f:
data = f.read().strip().splitlines()
reports = [list(map(int, line.split())) for line in data]
# >>> data
# ["7 6 4 2 1", "1 2 7 8 9", …, "9 7 6 2 1"]
# >>> reports
# [[7, 6, 4, 2, 1], [1, 2, 7, 8, 9,], …, [9, 7, 6, 2, 1]]
On veut compter le nombre de lignes qui répondent à une certaine propriété. Ça se fait très facilement avec les outils de la bibliothèque standard python.
reports = … # parse data
safe_reports = filter(is_safe, reports)
print(len(safe_reports))
La méthode filter
applique une fonction à chaque élément d'un itérable, et ne conserve que les éléments pour lesquelles la fonction renvoie une valeur vraie.
Il nous reste à écrire la méthode is_safe
.
En pseudo-code :
- pour chaque paire de deux valeurs successives
- vérifie si la direction est systématiquement croissante / décroissante
- (et si la différence est <= 3)
On pourrait écrire une boucle, quelque chose comme ça :
for i in range(report - 1):
n1, n2 = report[i], report[i + 1]
# vérifie si la propriété est respectée
Mais c'est un peu trop rustique à mon goût.
Pour frimer, nous allons préférer utiliser les deux méthodes pairwise
et starmap
.
def is_safe(report):
# Les deux méthodes qui valident la contrainte
# entre deux nombres successifs
checks = {
"inc": lambda v1, v2: v2 > v1 and 0 < abs(v2 - v1) <= 3,
"dec": lambda v1, v2: v2 < v1 and 0 < abs(v2 - v1) <= 3,
}
# On évacue le cas particulier ou les deux
# premiers items ne sont ni ascendants ni descendants
if report[0] == report[1]:
return False
# On compare les deux premières valeurs pour
# déterminer la direction et récupérer la bonne
# fonction de validation
direction = "inc" if report[1] > report[0] else "dec"
check = checks[direction]
# Admirez la magie !
pairs = pairwise(report)
safe = all(starmap(check, pairs))
return safe
La partie magique, si elle reste assez triviale, nécessite quelques explications.
La méthode pairwise
créé une liste de toutes les paires successives d'éléments dans un itérable.
>>> report = [1, 2, 3, 4, 5]
>>> print(pairwise(report))
[(1, 2), (2, 3), (3, 4), (4, 5)]
Ensuite, on vérifie que chaque paire valide la propriété. Pour ça, on applique la méthode check
grâce à la méthode starmap
.
starmap
fonctionne comme map
: elle applique une fonction à chaque élément d'un itérable. La seule différence est que starmap
« unpack » l'élément avant de le passer en paramètre.
On pourrait recoder ces deux fonctions ainsi :
def map(function, iterable):
return [function(element) for element in iterable]
def starmap(function, iterable):
return [function(*element) for element in iterable]
Ces deux codes sont donc équivalents :
safe = all(starmap(check, pairs))
safe = all([check(pair[0], pair[1]) for pair in pairs])
Cela nous permet d'avoir une lambda à deux paramètres. Très élégant !
Jour 3 : multiplier des nombres
Le problème du jour 3 consiste à retouver des instructions perdues dans de la soupe de caractère.
xmul(2,4)&mul[3,7]!^don't()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))
Ainsi, dans la chaîne précédente, il faut extraire les instructions :
- mul(2, 4)
- mul(5, 5)
- mul(11, 8)
- mul(8, 5)
Et retourner la somme de toutes ces multiplications.
La solution est triviale si l'on utilise les expressions régulières.
muls = re.findall(r"mul\((\d{1,3}),(\d{1,3})\)", data)
res = sum([int(a) * int(b) for a, b in muls])
print(res)
La seule chose que je peux suggérer d'améliorer ici, c'est la lisibilité de l'expression régulière. En effet, les regex sont notoirement très utiles mais difficile à relire et modifier une fois écrites.
Le complexité limitée de l'expression utilisée ici ne le justifie pas, mais on peut néanmoins utiliser une syntaxe alternative pour améliorer la lisibilité.
mul_re = re.compile(
r"""
mul\( # Ouverture de l'instruction mul
(\d+), # premier entier
(\d+) # deuxième entier
\) # fermeture de la parenthèse
""",
re.VERBOSE,
)
instructions = re.findall(mul_re, data)
muls = [int(a) * int(b) for a, b in instructions]
res = sum(muls)
print(res)
Jour 4 : Xmas dans une grille
Le jour 4, il fallait compter le nombre d'apparition du mot « XMAS » dans une grille de lettres. Le mot peut apparaître en horizontal, en vertical, en diagonal, à l'endroit et à l'envers.
Pour ça, la solution naïve fonctionne relativement bien ; On considère chaque lettre de la grille, on extrait les mots de 4 lettres dans les 8 directions, et on compte le nombre de « XMAS » obtenus.
with open("inputs/day_04.txt") as f:
data = f.read().strip().splitlines()
# Prenez quelques secondes pour admirer la ligne suivante
grid = np.array(list(map(list, data)))
count = 0
height, width = grid.shape
for y in range(height):
for x in range(width):
if grid[y, x] == "X":
words = get_words(padded, x, y)
nb_xmas = words.count("XMAS")
count += nb_xmas
La méthode get_words
est un peu bourrine mais efficace :
def get_words(grid, x, y):
letters = [
[grid[y, x], grid[y + 1, x], grid[y + 2, x], grid[y + 3, x]],
[grid[y, x], grid[y - 1, x], grid[y - 2, x], grid[y - 3, x]],
[grid[y, x], grid[y, x + 1], grid[y, x + 2], grid[y, x + 3]],
[grid[y, x], grid[y, x - 1], grid[y, x - 2], grid[y, x - 3]],
[grid[y, x], grid[y + 1, x + 1], grid[y + 2, x + 2], grid[y + 3, x + 3]],
[grid[y, x], grid[y + 1, x - 1], grid[y + 2, x - 2], grid[y + 3, x - 3]],
[grid[y, x], grid[y - 1, x - 1], grid[y - 2, x - 2], grid[y - 3, x - 3]],
[grid[y, x], grid[y - 1, x + 1], grid[y - 2, x + 2], grid[y - 3, x + 3]],
]
words = ["".join(letter for letter in word) for word in letters]
return words
Le problème avec ce code est qu'il ne fonctionne pas aux limites de la grille. En effet, lorsque l'index est négatif, numpy considère qu'on compte à partir de la fin de la dimension.
grid[-1, -1] # renvoie la lettre à la dernière ligne de la dernière colonne
On pourrait barder notre méthode get_words
de conditions mais ce serait fastidieux. Une alternative est de tout simplement « rembourrer » notre grille avec des valeurs pour ne jamais avoir d'indexs négatifs.
grid = np.array(list(map(list, data)))
# On ajoute une « couche » de « . » de 3 d'épaisseur
padded = np.pad(grid, pad_width=3, mode="constant", constant_values=".")
count = 0
height, width = padded.shape
for y in range(3, height - 3):
for x in range(3, width - 3):
…
Enfin, une solution alternative pour ne plus du tout s'embarrasser d'indexs serait de « simplement » utiliser des fenêtres glissantes pour directement extraire toutes les séquences de 4 lettres consécutives (horizontales, verticales, diagonales) existantes.
import numpy as np
from numpy.lib.stride_tricks import sliding_window_view
with open("inputs/day_04.txt") as f:
data = f.read().strip().splitlines()
grid = np.array(list(map(list, data)))
# Créé une fenêtre glissante horizontale de longueur 4
# Ainsi, on obtient toutes les séquences existantes
# de 4 caractères consécutif en ligne !
# Note : `sliding_window_view` retourne un tabeau dont
# la dimension dépend
# 1/ de la dimension de la grille originale et
# 2/ de la dimension de la fenêtre
# Ici, on obtient un tableau à 4 dimensions
# windows.shape = (140, 137, 1, 4)
# Or on veut juste une liste « plate » de séquences de
# 4 caractères.
# On obtient ce qu'on veut via la méthode `reshape`
h_windows = sliding_window_view(grid, (1, 4)).reshape(-1, 4)
h_words = ["".join(window) for window in h_windows]
# Toutes les séquences verticales de 4 caractères
# consécutifs
v_windows = sliding_window_view(grid, (4, 1)).reshape(-1, 4)
v_words = ["".join(window) for window in v_windows]
# Ici, on créé une fenêtre glissante de 4x4 pour
# obtenir les deux diagonales
d_windows = sliding_window_view(grid, (4, 4)).reshape(-1, 4, 4)
d1_words = ["".join(window.diagonal()) for window in d_windows]
d2_words = ["".join(np.fliplr(window).diagonal()) for window in d_windows]
words = h_words + v_words + d1_words + d2_words
# Les mots peuvent s'écrire dans les deux sens
# donc on doit aussi prendre en compte les inverses
inverted = [word[::-1] for word in words]
all_words = words + inverted
count = all_words.count("XMAS")
print(count)
C'est très efficace mais pas très beau.
Jour 5 : tri avec règle spécifique
Le problème du jour 5 nous donne un ensemble de règles de tri ainsi qu'une liste de séries de nombre, et nous demande deux tâches :
- partie 1 : vérifier que les nombres sont triés en respectant l'ordre arbitraire indiqué par les règles ;
- partie 2 : trier les séries invalides.
L'entrée est constituée ainsi, avec les règles d'abord et les séries ensuite.
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
Ensuite, il faut additionner les sommes des valeurs au milieu de chaque série.
On initialise tranquillou avec le code qui parse les données, et renvoie le résultat.
with open("inputs/day_05.txt") as f:
data = f.read()
rules, series = parse_data(data)
res = sum_middle_numbers(rules, series)
print(res)
# On renvoie les données dans un format utilisable
def parse_data(data):
# Sépare les règles et les séries
top, bottom = data.split("\n\n")
# Pour chaque règle, extrait une liste de
# de paires d'entiers
# Les nombres à gauche doivent toujours apparaître
# avant les nombres à droite
rules = [tuple(map(int, rule.split("|"))) for rule in bottom.splitlines()]
# Je veux qu'il soit facile de récupérer la liste
# de tous les nombres qui doivent apparaître après un
# nombre donné
rules_dict = defaultdict(list)
for before, after in rules:
rules_dict[after].append(before)
series = [list(map(int, serie.split(","))) for serie in bottom.splitlines()]
return rules_dict, series
Le seul élément digne d'intérêt ici est l'utilisation de defaultdict
. Il s'agit d'un extension de dict
disposant d'une valeur par défaut. Ainsi, les deux codes suivants sont équivalents :
rules_dict = {}
for before, after in rules:
if before not in rules:
rules[before] = list()
rules_dict[before].append(after)
rules_dict = defaultdict(list)
for before, after in rules:
rules_dict[after].append(before)
Vous conviendrez que le second bloc est plus élégant et lisible.
Implémentons maintenant sum_middle_numbers
.
from functools import partial
def sum_middle_numbers(rules, series):
serie_valid = partial(is_serie_valid, rules=rules)
valid_series = list(filter(serie_valid, series))
middle_numbers = [serie[len(serie) // 2] for serie in valid_series]
return sum(middle_numbers)
L'élément intéressant ici est l'utilisation de partial
, qui permet de créer une nouvelle méthode à la volée en fixant à l'avance certains paramètres.
partial
est très souvent utilisé en conjonction avec filter
, map
, etc. En effet, par défaut, filter
ne passe qu'un paramètre à la fonction de filtre : l'élément de la liste en court de filtrage. Pour passer plusieurs paramètres à cette fonction, on créé une partial.
Ici, cela nous permet de faire en sorte que la méthode serie_valid
recevra en paramètre la série en cours et la liste des règles de validation.
def is_serie_valid(serie, rules):
need_to_print_before = set()
for page in serie:
if page in need_to_print_before:
return False
need_to_print_before |= set(rules[page])
return True
Le code ici n'a pas grand intérêt. Pour chaque élément de la série, on garde la liste de tous les éléments qui doivent apparaître avant d'après les règles. Si à un moment donné un élément de la série condredit les règles, on renvoie False.
Jetons un œil à la partie 2 : on nous demande de ne considérer que les listes initialement invalides, et de les ordonner en respectant les règles.
from itertools import filterfalse
def sum_middle_numbers(rules, series):
serie_valid = partial(is_serie_valid, rules=rules)
invalid_series = list(filterfalse(serie_valid, series))
valid_series = [make_valid(serie, rules) for serie in invalid_series]
middle_numbers = [serie[len(serie) // 2] for serie in valid_series]
return sum(middle_numbers)
La fonction make_valid
est quand à elle triviale si on se rappelle qu'on peut avec Python trier des éléments avec une méthode de comparaison arbitraire.
from functools import cmp_to_key
def make_valid(serie, rules):
cmp = cmp_to_key(lambda v1, v2: -1 if v2 in rules[v1] else 1)
valid_serie = sorted(serie, key=cmp)
return valid_serie
Jour 7 : un peu de récursif
Le problème du jour 7 est un jeu de « chiffres et des lettres ». On nous donne des suites de nombres, et une valeur cible. Il faut vérifier si on peut atteindre la valeur cible en combinant les nombres donnés.
Exemple avec la ligne : 3267: 81 40 27
.
Est-il possible d'atteindre 3267 en combinant ces nombres ? Oui, de cette façon : 81 + 40 * 27
.
Les combinaisons possibles sont simples : les seuls opérateurs utilisés sont l'addition et la multiplication, et toujours de gauche à droite.
Ce problème peut facilement être résolu si on tient compte de la propriété suivante :
On peut atteindre 3267 avec [81, 40, 27] SI :
- on peut atteindre 3267 avec [81 + 40, 27]
- OU avec [81 * 40, 27].
La solution peut donc être implémentée via une méthode récursive.
def solve(target, numbers):
current_value = numbers[0]
# On a déjà dépassé la cible, c'est mort
if current_value > target:
return False
# On a consommé tous les nombres
# A-t-on atteint la cible ?
if len(numbers) == 1:
return target == current_value
# Résoud récursivement en additionnant les deux premières valeurs
if solve(target, [numbers[0] * numbers[1]] + numbers[2:]):
return True
# Résoud récursivement en multipliant les deux premières valeurs
if solve(target, [numbers[0] + numbers[1]] + numbers[2:]):
return True
return False
def sum_test_values(data):
count = 0
for target, numbers in data:
if solve(target, numbers):
count += target
return count
calibration_data = parse_data(data)
res = sum_test_values(calibration_data)
print(res)
Jour 8 : antennes et antinodes
Une grille présente des antennes. Chaque paire d'antennes identiques génère des éléments appelés « antinodes ». Il suffit de compter le nombre d'antinodes sur la grille.
demo_data = """
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
""".strip().splitlines()
grid = np.array(list(map(list, demo_data)))
Mon intuition première était de procéder ainsi:
- je trouve les antennes
- je détermine les paires d'antennes uniques
- je génère les antinodes pour chaque paire d'antennes
- je les compte
- je reprends un café.
def count_antinodes(grid):
antinodes = []
pairs = find_pairs(grid)
for pair in pairs:
pair_antinodes = find_antinodes(grid, pair)
antinodes.extend(pair_antinodes)
return len(set(antinodes))
res = count_antinodes(grid)
print(res)
Rien de bien méchant. Quelques astuces numpy vont nous aider à trouver les antennes, qui sont tous les éléments qui ne sont pas un point « . ».
# Ici, on retourne une liste de tous les caractères
# qui ne sont pas un « . ».
# Sur les données de démo : ["0", "A"]
def find_unique_antennas(grid):
return set(np.unique(grid)) - {"."}
Maintenant qu'on a la liste d'antennes existantes, on veut trouver les coordonnées des antennes similaires, et déterminer les paires d'antennes uniques.
Pour cela, on va utiliser la méthode combinations
, une méthode standard qui génère les paires uniques à partir d'un iterable.
>>> list(combinations(['A', 'B', 'C'], 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]
Notez qu'ici, les paires ("A", "B") et ("B", "A") seraient identiques, et qu'il faut bien éviter les doublons.
from itertools import combinations
# Retourne une liste de paires de coordonnées d'antennes
# Attention, on ne veut pas de doublons
def find_pairs(grid):
antennas = find_unique_antennas(grid)
pairs = []
for antenna in antennas:
raw_coords = np.where(grid == antenna)
coords = list(zip(*raw_coords))
coord_pairs = list(combinations(coords, 2))
print(antenna, coords, coord_pairs)
pairs.extend(coord_pairs)
return pairs
Par exemple, on trouve des antennes « A » aux coordonnées [(5, 6), (8, 8), (9, 9)]
. Les paires distinctes sont [((5, 6), (8, 8)), ((5, 6), (9, 9)), ((8, 8), (9, 9))]
.
Déterminer les positions des antinodes à partir de paires d'antennes est juste de l'implémentation de définition du problème.
def find_antinodes(grid, pair):
a1, a2 = pair
dy, dx = a2[0] - a1[0], a2[1] - a1[1]
height, width = grid.shape
antinodes = [(a1[0] - dy, a1[1] - dx), (a2[0] + dy, a2[1] + dx)]
# Filtre les antinodes pour enlever ceux
# qui sortent de la grille
antinodes = [
node for node in antinodes if 0 <= node[0] < height and 0 <= node[1] < width
]
return antinodes
Jour 11 : Comptage de pierres
Le problème du jour 11 est le premier qui ne peut pas être résolu par une approche « bruteforce ».
On nous donne une suite de pierres (des nombres). À chaque itération, les pierres changent de valeur et se multiplient en fonction de règles très simples.
Il faut calculer le nombre de pierres au bout d'un certain nombre d'itérations : 25 pour la partie 1, 75 pour la partie 2.
Pour ce genre de problème, il est toujours très simple de coder une simulation, c'est à dire de simplement appliquer les règles bêtement et de voir ce qui se passe.
with open("inputs/day_11.txt") as f:
data = list(map(int, f.read().strip().split()))
demo_data = [125, 17]
# À chaque étape, on génère une nouvelle liste de nombres
# en appliquant bêtement les règles.
def solve(numbers, steps):
for step in range(steps):
new = []
for n in numbers:
str_n = str(n)
if n == 0:
new.append(1)
elif len(str_n) % 2 == 0:
middle = len(str_n) // 2
new.append(int(str_n[:middle]))
new.append(int(str_n[middle:]))
else:
new.append(n * 2024)
numbers = new
return len(numbers)
demo_res = solve(demo_data, 25)
assert demo_res == 55312, demo_res
res = solve(data, 25)
print(res)
Tout fonctionne parfaitement pour un nombre limité d'itérations. En revanche, mon ordi rend l'âme au bout de 30 ~ 35 itérations.
Si on analyse les règles, on constate que grosso-modo, les pierres se divisent fréquemment en deux, donc la liste double de taille à chaque itération (grosso-modo).
La taille de la liste à l'itération n a donc une taille d'un ordre de grandeur de 2^n. 225, c'est 33554432 (grosso-modo 33 Mo). 275 c'est 37778931862957161709568, bien plus que ce que peut gérer une machine même ultramoderne.
Pour résoudre de problème, il faut constater les propriétés suivantes :
- l'ordre des pierres n'a en fait aucune importance (contrairement à ce qui est sournoisement indiqué dans l'énoncé)
- les pierres peuvent avoir un nombre de valeurs distinctes limitées.
En effet, si j'analyse ma liste de pierre au bout d'une trentaine d'itérations, elle est longue de plusieurs millions, mais elle ne contient qu'environ 700 valeurs distinctes. On comprends donc que notre simulation passe un temps infini à effectuer les mêmes opérations.
Au lieu de simuler chaque pierre indépendemment, nous allons tout simplement grouper les pierres de même valeurs. Pour ça, nous allons nous aider de la classe Counter
de Python.
Counter
permet de créer un dictionnaire de comptage, avec une valeur par défaut de zéro pour les éléments manquants.
>>> counter = Counter([1, 1, 1, 2, 3])
>>> counter
Counter({1: 3, 2: 1, 3: 1})
>>> counter[1] += 1
>>> counter[4] += 1
>>> counter
Counter({1: 4, 2: 1, 3: 1, 4: 1})
Ainsi, les 750 pierres de valeur « 0 » deviendront 750 pierres de valeur « 1 », etc.
from collections import Counter
with open("inputs/day_11.txt") as f:
data = list(map(int, f.read().strip().split()))
demo_data = [125, 17]
def solve(numbers, steps):
counter = Counter(numbers)
for step in range(steps):
step_counter = Counter()
for n, count in counter.items():
str_n = str(n)
if n == 0:
step_counter[1] += count
elif len(str_n) % 2 == 0:
middle = len(str_n) // 2
step_counter[int(str_n[:middle])] += count
step_counter[int(str_n[middle:])] += count
else:
step_counter[n * 2024] += count
counter = step_counter
return counter.total()
demo_res = solve(demo_data, 25)
assert demo_res == 55312, demo_res
res = solve(data, 75)
print(res)
L'autre approche possible, toute aussi belle, est de réaliser que chaque pierre peut être considérée complètement indépendemment de manière récursive.
En effet :
- chaque pierre de la liste va se transformer en un nombre de pierre au bout d'un certain nombre d'itérations ;
- le nombre de pierres générées à l'itération n peut facilement être déduit du nombre de pierre à n - 1.
On redéfini notre interface ainsi :
from functools import cache
@cache
def count(number, step):
if step == 0:
return 1
if number == 0:
return count(1, step - 1)
str_n = str(number)
if len(str_n) % 2 == 0:
middle = len(str_n) // 2
n1 = count(int(str_n[:middle]), step - 1)
n2 = count(int(str_n[middle:]), step - 1)
return n1 + n2
return count(number * 2024, step - 1)
demo_res = sum(count(stone, 25) for stone in demo_data)
assert demo_res == 55312, demo_res
res = sum(count(stone, 75) for stone in data)
print(res)
Comme on l'a vu plus haut, le nombre de couple (number, step) étant limité, on a juste à mettre en cache la méthode count
pour passer de quelques millions d'années de calculs à quelques millisecondes.
Jour 13 : un peu d'algèbre linéaire
Décidément, l'AoC de cette année aime nous amener sur de fausses pistes.
Le problème du jour est rédigé de manière à nous laisser croire qu'il peut être résolu avec de la programmation dynamique (récursion + caching). On en sera pour ses frais avec les contraintes du jour 2.
On nous donne une série de lignes décrivant le fonctionnement de machines à grappins. Chaque machine dispose de deux boutons (A et B), chacun déplaçant le grappin sur une certaine distance sur deux axes (X, Y).
Il faut calculer combien de fois appuyer sur les boutons A et B pour déplacer le grappin jusqu'au prix.
Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400
import re
from itertools import starmap
from sympy import solve, Symbol
def parse(input):
entries = input.split("\n\n")
equations = [map(int, re.findall(r"\d+", entry)) for entry in entries]
return equations
def play(AX, AY, BX, BY, X, Y):
# ???
inputs = parse(open("inputs/day_13.txt").read())
res = sum(starmap(play, inputs))
print(res)
On peut très facilement implémenter une version récursive de la fonction.
@cache
def play(AX, AY, BX, BY, X, Y):
# Si on a dépassé le prix, pas la peine de continuer
if X < 0 or Y < 0:
return math.inf
# On a atteint le prix, on s'arrête
if X == 0 and Y == 0:
return 0
# On regarde ce qui nécessite le moins de boutons, une fois
# qu'on a appuyé successivement sur A ou B
minA = 1 + play(AX, AY, BX, BY, X - AX, Y - AY)
minB = 1 + play(AX, AY, BX, BY, X - BX, Y - BY)
result = min([minA, minB])
return 0 if result == math.inf else result
Mais dès que la taille de X et Y augmente démesurément, cette approche n'est plus possible, car le nombre de combinaisons uniques est trop important, et le fait de mettre le résultat en cache ne suffit pas à récupérer un temps raisonnable.
Il faut donc une autre approche.
Le problème devient raisonnablement simple si on se rend compte qu'on peut le ramener à un problème d'algèbre linéaire. Il s'agit ici de résoudre un système de deux équations à deux inconnues.
En effet on veut calculer les nombres a
et b
tels que :
a * AX + b * BX == X
a * AY + b * BY == Y
On peut effectuer le calcul sur un papier pour simplifier l'équation et implémenter directement le résultat. Ou on peut être fainéant et utiliser une bibliothèque dédiée (numpy, scipy, z3, sympy).
from sympy import solve, Symbol
def play(AX, AY, BX, BY, X, Y):
a = Symbol("a", integer=True)
b = Symbol("b", integer=True)
roots = solve(
[a * AX + b * BX - X, a * AY + b * BY - Y],
[a, b],
)
return roots[a] * 3 + roots[b] if roots else 0
Le code ci-dessus fonctionne à l'identique sur la partie 2, il suffit d'appliquer l'énoncé du problème en ajoutant 10000000000000 à X et Y.
Jour 15 : à la recherche de l'easter-egg
Encore un énoncé doublement piégeux. Des robots se déplacent sur une grille à chaque itération. Il faut calculer les positions de tous les robots au bout de X itérations. Le premier réflexe est d'effectuer une simulation, mais nooooon, la partie 2 va sûrement rendre ce processus obsolète. Mieux vaut calculer le résultat plus efficacement.
L'entrée est constituée d'une liste de robots :
p=81,16 v=32,84
…
Chaque robot a des coordonnées de départ, et une vélocité par itération.
Il faut calculer le nombre de robots présents dans chaque quart de la grille à la 100e itération.
Dans la mesure où la grille est en fait un tore (gauche et droite sont connectés, de même que haut et bas), et où les robots n'interagissent pas entre eux, il est très facile de calculer les coordonnées d'un robot à la nième itération. C'est :
- posX(n) = (startX + speedX * n) % gridWidth
- posY(n) = (startY + speedY * n) % gridHeigth
On place alors chaque robot dans un quadrant [(0, 0), (1, 0), (1, 0), (1, 1)]
import re
from collections import defaultdict
import math
def safety_factor(robots, width, height, iterations):
quadrants = defaultdict(lambda: 0)
for x, y, vx, vy in robots:
final_x = (x + vx * iterations) % width
final_y = (y + vy * iterations) % height
if final_x != width // 2 and final_y != height // 2:
quadrant = round(final_x / width), round(final_y / height)
quadrants[quadrant] += 1
return math.prod(quadrants.values())
robots = [
list(map(int, re.findall(r"-?\d+", line))) for line in open("inputs/day_14.txt")
]
res = safety_factor(robots, 101, 103, 100)
print(res)
À la partie 2, coup de théâtre ! Il faut trouver à quelle itération les robots vont dessiner un sapin de noël ! Il faudra donc simuler chaque itération.
Par ailleurs, on ne sait pas comment sera le dessin : est-ce que tous les robots seront impliqués (ce que j'ai supposé à tort), est-ce que le sapin sera centré, etc. ?
Finalement, on peut supposer que la répartition des robots à l'itération qui nous intéresse présentera une anomalie statistique particulière. Après avoir tâtonné, je suis tombé sur la bonne réponse en comptant le nombre de clusters dans l'image.
import re
import numpy as np
from PIL import Image
from scipy.ndimage import label
def find_easter_egg(robots, width, height, max_iterations):
for i in range(max_iterations):
data = np.zeros((width, height))
for x, y, vx, vy in robots:
final_x = (x + vx * i) % width
final_y = (y + vy * i) % height
data[final_x, final_y] = 255
# Il y a 500 robots dans la liste
# La plupart du temps, les robots ne se touchent pas
# Le nombre de cluster est donc généralement proche de 500
# Ici, la valeur 250 est arbitraire et obtenue en
# tâtonnant
labels, n = label(data)
if n <= 250:
img = Image.fromarray(data)
img.show()
print("Iteration ", i)
input("Press enter")
robots = [
list(map(int, re.findall(r"-?\d+", line))) for line in open("inputs/day_14.txt")
]
res = find_easter_egg(robots, 101, 103, 10000)
print(res)
La méthode label
de scipy identifie les données contiguës > 0 dans une grille, permettant de les regrouper en « clusters ».
On affiche ensuite l'image pour vérifier visuellement que c'est bien ce qui nous intéresse.
Jour 17 : vous reprendrez bien un peu d'assembleur ?
À ce jour, peut-être mon puzzle préféré de cette édition (mais pas le plus facile).
La première partie est triviale (ce qui en soi est assez flippant à ce stade du mois) : il faut implémenter un mini-langage de programmation.
On nous donne un programme sous forme de suite de chiffres, chaque paire de chiffres successifs correspondant à une instruction et son argument.
Chaque chiffre correspond à une fonction qui s'applique sur son argument, et un pointeur avance sur l'instruction suivante (sauf lors de l'instruction spéciale « jump »).
Pour la première partie, il suffit d'implémenter bêtement les règles telles que définies dans le puzzle, de lancer la machine et récupérer la sortie.
A = 41644071
B = 0
C = 0
program = [2, 4, 1, 2, 7, 5, 1, 7, 4, 4, 0, 3, 5, 5, 3, 0]
pointer = 0
output = []
while pointer < len(program):
combo = {0: 0, 1: 1, 2: 2, 3: 3, 4: A, 5: B, 6: C, 7: None}
match (program[pointer], program[pointer + 1]):
case 0, operand: # adv
A = A // (2 ** combo[operand])
case 1, operand: # bxl
B = B ^ operand
case 2, operand: # bst
B = combo[operand] % 8
case 3, operand: # jnz
if A:
pointer = operand - 2
case 4, operand: # bxc
B = B ^ C
case 5, operand: # out
output.append(combo[operand] % 8)
case 6, operand: # bdv
B = A // (2 ** combo[operand])
case 7, operand: # cdv
C = A // (2 ** combo[operand])
pointer += 2
print(output)
# -> [3, 1, 5, 3, 7, 4, 2, 7, 5]
La partie 2 se complique : il faut trouver LA valeur de A telle que, quand on lance le programme, celui-ci génère son propre code. C'est à dire que le résultat de la fonction précédente soit égale à la variable initiale program
.
Comme le programme est très court, et d'exécution très rapide, on peut par acquis de conscience tenter une approche bruteforce. Génerer la sortie du programme pour les valeurs de A de 0 à 50000000 ne prends que quelques minutes. Mais ne permet pas d'obtenir la bonne valeur. On comprends alors que la démarche est vouée à l'échec, il va falloir être plus intelligent.
La première étape est d'inspecter notre programme pour mieux le comprendre. En effet, l'énoncé du problème nous a amené à coder une fonction générale, mais nous n'avons pas à traiter des milliers de programmes, juste un.
J'ai commencé par réécrire le programme en instructions telles que données par l'énoncé. On obtient ceci :
bst 4
bxl 2
cdv 5
bxl 7
bxc 4
adv 3
out 5
jnz 0
Ensuite, on convertit ce « code » en instructions Python compréhensibles.
B = A % 8
B = B ^ 2
C = A // (2 ** B)
B = B ^ 7
B = B ^ C
A //= 8
output.append(B % 8)
# if A != 0: goto première ligne
Il n'y a pas d'instruction « jump » en Python, mais puisque l'instruction est en dernière ligne, et saute à la première ligne, on émule efficacement ce fonctionnement avec une boucle. On obtient alors :
while A:
B = A % 8
B = B ^ 2
C = A // (2 ** B)
B = B ^ 7
B = B ^ C
A //= 8
output.append(B % 8)
(On pourrait sans doute encore simplifier en combinant ces opérations, mais j'ai eu la flemme et ça ne s'est pas avéré nécessaire.)
En analysant ces quelques lignes, on observes les caractéristiques suivantes :
- le programme est donc constitué d'une seule boucle ;
- on boucle sur la valeur de A, qu'on divise par 8 à chaque étape ;
- A décroit donc systématiquement d'un tour à l'autre ;
- on termine le programme quand A tombe à 0 ;
- chaque tour de boucle génère l'affichage d'un nouveau caractère ;
- les valeurs de B et C ne sont pas conservés d'un tour à l'autre, mais dépendent entièrement de A.
Puisque le programme affiche un caractère et divise A par 8 à chaque tour de boucle, on en déduit que pour afficher le programme, qui a une longueur de 16, il faut que A soit au moins égal à 816, ce qui est très très très supérieur aux 500000 que nous avons bruteforcé tout à l'heure :)
Tout cela ne nous aide pas à déterminer quelle valeur donner à A.
Une autre observation permet de débloquer la situation : on ne peut pas déterminer la valeur initiale de A, mais on peut peut-être trouver la valeur à la dernière itération.
En effet, à la dernière itération, on a forcément A > 0 (sinon le programme se serait arrêté) et A < 8 (sinon ça ne serait pas la dernière itération.)
On sait aussi que cette dernière itération ne dépend que de la valeur de A à ce moment là, et on sait quelle valeur on doit obtenir en sortie (la dernière valeur du programme).
On peut donc tester toutes les valeurs entre 0 et 7, et ne garder que celles qui génèrent la bonne valeur. Mais quelle est la valeur de A à l'avant-dernière étape ? On ne sait pas, toutefois, on sait que ce sera (A de la dernière étape * 8 + une valeur entre 0 et 7).
On peut ainsi construire récursivement les solutions possibles.
En procédant ainsi, on réduit l'espace de recherche à 8 * 16 au lieu de 816. Une sacré optimisation.
Hop ! on passe à l'implémentation.
program = [2, 4, 1, 2, 7, 5, 1, 7, 4, 4, 0, 3, 5, 5, 3, 0]
# On extrait le contenu de la boucle dans une fonction dédiée
# Cela va nous aider pour la suite.
def step(A):
B = A % 8
B = B ^ 2
C = A // (2**B)
B = B ^ 7
B = B ^ C
return B % 8
# Cette fonction fait tourner le programme complet pour
# une valeur de A donnée.
# Elle n'a aucun usage ici mais je la garde pour la pédagogie.
def run(A):
output = []
while A:
output.append(step(A))
A //= 8
return output
# Voici maintenant la méthode de recherche principale.
# On lui passe la valeur courante de A et l'index du programme qu'on veut obtenir
def find(A, index):
# On commence par vérifier que le résultat de la
# boucle à cette étape est bien celui attendu.
# Sinon pas la peine de continuer.
if step(A) != program[index]:
return
# Condition d'arrêt : on a généré tout le programme,
# on a donc une valeur de A valide.
if index == 0:
# Techniquement, la première valeur de A trouvée est
# la plus basse des valeurs possibles.
# On pourrait donc s'arrêter là.
As.append(A)
else:
# On poursuit la valeur en passant à l'index précédent
# du programme, et en testant les 8 valeurs possibles.
for B in range(8):
find(A * 8 + B, index - 1)
# Recherche toutes les valeurs de A
# pour les valeurs initiales de 0 à 7
# On pourrait sans doute faire beaucoup plus propre qu'avec
# une variable globale mais il est 21h et j'ai la flemme.
As = []
first_index = len(program) - 1
for a in range(8):
find(a, first_index)
print(min(As))
Ce programme crache la bonne réponse instantanément. J'ai encore les neurones qui chauffent.