Advent of Code 2022

Entraînement · Advent of Code 2022 · Python (C et OCaml pour les premiers jours)

Cours : Graphes · Arbres · Programmation dynamique · Récursivité

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Sommes par groupes, puis les trois plus grandes	Sommes par blocs, tri décroissant	Accumulateur, tri	C, OCaml, Python
2	Calcul de scores d'un jeu à trois coups	Coups codés 0, 1, 2 et différence modulo 3	Arithmétique modulo 3	C, Python
3	Trouver l'élément commun à plusieurs chaînes	Intersection d'ensembles	Ensembles	Python
4	Inclusion et chevauchement d'intervalles	Comparaisons d'extrémités	Instructions conditionnelles	C, OCaml, Python
5	Déplacements entre plusieurs piles	Listes Python comme piles, tranches pour la partie 2	Piles	Python
6	Première fenêtre de caractères tous distincts dans un flux	Fenêtre glissante et len(set(...))	Algorithmique du texte, ensembles	Python
7	Reconstruire une arborescence de fichiers à partir d'un journal de commandes	Dictionnaires indexés par chemin, cumul par profondeur décroissante	Arbres, dictionnaires	Python
8	Visibilité le long des lignes et colonnes d'une grille	Rayons dans les quatre directions depuis chaque case	Boucles imbriquées	Python
9	Simulation d'une chaîne de points qui se suivent	Simulation pas à pas, ensemble des positions	Ensembles, simulation	Python
10	Simulation d'un processeur cadencé et d'un écran	Interprète cycle par cycle	Interprète	Python
11	Simulation d'échanges, puis valeurs à réduire modulo un produit	Files deque, réduction modulo le ppcm des diviseurs	Arithmétique modulaire, files	Python
12	Plus court chemin non pondéré dans une grille sous contrainte de déplacement	BFS sur grille, relancé depuis chaque départ	Parcours en largeur	Python
13	Comparer et trier des listes imbriquées	Comparaison récursive à trois issues, cmp_to_key	Récursivité, arbres	Python
14	Simulation de chute de grains dans une grille	Simulation grain par grain, grille creuse defaultdict	Ensembles, simulation	Python
15	Zones en losange (distance de Manhattan) : union d'intervalles par ligne	Coupe de chaque losange par une ligne, soustraction d'intervalles	Droite de balayage	Python
16	Maximiser un gain en parcourant un graphe en temps limité	Floyd-Warshall, graphe compressé, mémoïsation sur (positions, temps, masque)	Floyd-Warshall, mémoïsation	Python
17	Simulation de chute de pièces, puis détection d'un cycle	Simulation sur grille, signature (pièce, instruction, profil), détection de cycle	Dictionnaires, simulation	Python
18	Surface d'un objet en voxels, puis surface extérieure seule	Comptage de faces, BFS de remplissage des poches d'air	Parcours en largeur, ensembles	Python
19	Planifier une production sous contraintes de ressources	Recherche mémoïsée avec élagages heuristiques, puis tirages aléatoires	Retour sur trace et élagage, Monte-Carlo	C, Python
20	Permutations successives d'une liste circulaire	deque d'indices et rotations	Listes chaînées, rotation d'une file	Python
21	Évaluer un arbre d'expression, puis résoudre une équation en une inconnue	Évaluation récursive, inversion des opérations, Fraction	Arbres d'expressions, récursivité	Python
22	Déplacement sur une carte dont les bords se recollent, puis sur un patron de cube	Simulation, recollements de faces codés à la main	Simulation, géométrie	Python
23	Automate cellulaire à règles de déplacement	Simulation synchrone avec compteur de propositions	Ensembles, jeu de la vie	Python
24	Plus court chemin dans une grille dont les obstacles bougent	BFS sur (position, temps), obstacles précalculés par période	Parcours en largeur dans l'espace-temps	Python
25	Conversion vers et depuis une base 5 à chiffres signés	Base 5 équilibrée : décalage de 2 avant % et //	Représentation des entiers	Python

Jour 7 — No Space Left On Device

Énoncé : adventofcode.com/2022/day/7

Jour 12 — Hill Climbing Algorithm

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

Jour 13 — Distress Signal

Énoncé : adventofcode.com/2022/day/13

Jour 16 — Proboscidea Volcanium

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

Jour 21 — Monkey Math

Énoncé : adventofcode.com/2022/day/21