Advent of Code 2021

Entraînement · Advent of Code 2021 · C, OCaml, Python

Cours : Graphes · Arbres · Grammaires non contextuelles · Programmation dynamique

Dépôt : advent-of-code-2021

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Comparaisons entre valeurs successives, puis sur une fenêtre glissante	Parcours unique, somme glissante mise à jour	Boucles et accumulateurs	C, OCaml, Python
2	Suivre une position au fil d'une liste de commandes	Simulation avec deux ou trois variables d'état	Simulation, programmation impérative	C, OCaml, Python
3	Statistiques bit à bit sur des mots binaires, puis filtrages successifs	Comptage par colonne, filtrage récursif par bit	Représentation binaire, tableaux	C, OCaml, Python
4	Simulation d'un jeu sur des grilles	Marquage en place, test lignes/colonnes après chaque tirage	Tableaux à deux dimensions	C, OCaml, Python
5	Segments sur une grille : compter les points de recouvrement	Tracé point par point dans un dictionnaire de compteurs	Dictionnaires, tableaux	C, OCaml, Python
6	Croissance d'une population : passer des individus aux effectifs par classe	Histogramme à 9 cases décalé à chaque jour	Complexité, récurrence linéaire	Python
7	Choisir une position minimisant une somme de coûts	Essai de toutes les positions candidates	Force brute, médiane	OCaml, Python
8	Retrouver une permutation cachée à partir d'observations	Essai des 5040 permutations ; variante par invariant d'intersections	Force brute, ensembles	Python
9	Minima locaux d'une grille, puis taille des régions qui les entourent	DFS sur grille depuis chaque minimum	Composantes connexes, remplissage	OCaml, Python
10	Vérifier le bon parenthésage de lignes, compléter les lignes inachevées	Pile des fermantes attendues	Piles	Python
11	Automate cellulaire avec propagation en cascade	Simulation, cascade gérée par une pile de cases à traiter	Jeu de la vie, parcours	OCaml, Python
12	Dénombrer les chemins d'un graphe sous contrainte de visite	Retour sur trace avec ensemble des petits sommets et booléen « joker »	Graphes, retour sur trace	C, OCaml, Python
13	Pliages successifs d'un ensemble de points	Ensemble de points, symétrie par rapport à l'axe	Ensembles	Python
14	Règles de réécriture appliquées de nombreuses fois : compter les paires plutôt que construire le mot	Compteur de paires, puis puissance d'une matrice de transition	Dictionnaires, grammaires, exponentiation rapide	Python
15	Plus court chemin pondéré dans une grille	Dijkstra avec file de priorité, grille dupliquée pour la partie 2	Algorithme de Dijkstra	Python
16	Décoder un flux binaire de paquets imbriqués puis évaluer l'expression obtenue	Descente récursive sur un flux de bits, évaluation de l'arbre	Descente récursive, arbres d'expressions	OCaml, Python
17	Trajectoires balistiques discrètes atteignant une cible	Simulation de toutes les vitesses initiales dans une boîte bornée	Force brute	Python
18	Arithmétique sur des arbres binaires avec règles de réduction	Arbre immuable et chemin vers la racine (zipper) ; en Python, travail sur la chaîne	Arbres binaires, filtrage	OCaml, Python
19	Recaler des nuages de points 3D vus dans des repères inconnus	24 rotations × empreintes de vecteurs différences, propagation depuis le scanner 0	Force brute, dictionnaires	Python
20	Automate cellulaire sur une image infinie	Ensemble des cases allumées, fond codé par un drapeau d'inversion	Jeu de la vie, ensembles	Python
21	Jeu de plateau, puis dénombrement de toutes les parties possibles	Mémoïsation sur (joueur, scores, positions), lancers groupés par somme	Mémoïsation	Python
22	Volume d'une union et différence de pavés	Liste de pavés disjoints, soustraction par découpage en au plus 27 morceaux	Force brute, découpage en pavés disjoints	Python
23	Puzzle de déplacements : plus court chemin dans un espace d'états	Dijkstra sur les configurations codées en chaînes	Algorithme de Dijkstra	Python
24	Comprendre un programme pour une petite machine à registres afin d'en trouver les entrées valides	Exécution symbolique, contraintes entre chiffres deux à deux (pile en base 26)	Interprète, piles	OCaml
25	Automate cellulaire sur une grille torique	Simulation synchrone en deux demi-pas jusqu'au point fixe	Jeu de la vie	Python

Jour 9 — Smoke Basin

Énoncé : adventofcode.com/2021/day/9

Jour 12 — Passage Pathing

Énoncé : adventofcode.com/2021/day/12

Jour 15 — Chiton

Énoncé : adventofcode.com/2021/day/15

Jour 16 — Packet Decoder

Énoncé : adventofcode.com/2021/day/16

Jour 18 — Snailfish

Énoncé : adventofcode.com/2021/day/18

Jour 14 — Extended Polymerization

Énoncé : adventofcode.com/2021/day/14