Advent of Code 2023

Entraînement · Advent of Code 2023 · Python

Cours : Graphes · Programmation dynamique · Dictionnaires et tables de hachage · Force brute et retour sur trace · Graphes avancés

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Extraire le premier et le dernier chiffre d'une ligne, écrits en chiffres ou en lettres	Balayage avec test de préfixe	Boucles, chaînes	Python
2	Vérifier des tirages contre des bornes, puis minimum nécessaire par couleur	Dictionnaires par tirage, all et max	Dictionnaires	Python
3	Nombres d'une grille adjacents à des symboles	Repérage des nombres puis examen du voisinage	Boucles imbriquées, grilles	Python
4	Compter des numéros communs, puis des copies en cascade	Comptage par effectifs (pas d'objets copiés)	Accumulateur, dictionnaires	Python
5	Composer des fonctions affines par morceaux sur d'immenses intervalles	Découpage d'intervalles avec une pile	Piles, intervalles	Python
6	Compter les entiers vérifiant une inégalité quadratique	Force brute, puis racines d'un trinôme	Force brute, calcul flottant	Python
7	Classer des mains de cartes, avec un joker en partie 2	Tri par clé (catégorie, valeurs), Counter	Dictionnaires, tri, ordre lexicographique	Python
8	Suivre des pointeurs selon une suite d'instructions, plusieurs marcheurs simultanés	Détection de cycles puis PPCM	Graphes, dictionnaires	Python
9	Extrapoler une suite d'entiers	Différences finies successives	Boucles, listes	Python
10	Trouver une boucle de tuyaux dans une grille, puis compter les cases enfermées	DFS avec détection de cycle, remplissage sur grille agrandie ×3	Détection de cycles, remplissage	Python
11	Somme des distances entre points d'une grille dont certaines lignes et colonnes sont dilatées	Dijkstra depuis chaque point, poids dilatés	Algorithme de Dijkstra	Python
12	Dénombrer les complétions d'un motif compatibles avec des longueurs de blocs	Mémoïsation sur (position, bloc, longueur courante)	Mémoïsation	Python
13	Trouver un axe de symétrie dans des motifs, puis à une erreur près	Lignes codées en entiers, XOR et popcount	Représentation binaire, boucles imbriquées	Python
14	Basculer une grille de cailloux un milliard de fois	Simulation et détection de cycle d'états	Ensembles, simulation	Python
15	Calculer une fonction de hachage, puis simuler une table de hachage	Table à 256 alvéoles avec listes de collisions	Tables de hachage	Python
16	Propagation de rayons dans une grille de miroirs	Parcours sur états (position, direction)	Parcours de graphe, ensembles	Python
17	Plus court chemin pondéré avec contraintes sur les lignes droites	Dijkstra sur (case, direction, nombre de pas)	Dijkstra, graphe d'états	Python
18	Aire d'un polygone rectilinéaire décrit par ses déplacements	Remplissage, puis formule de l'aire de Gauss et théorème de Pick	Remplissage, géométrie	Python
19	Faire passer des objets dans des règles de tri, puis compter tous les objets acceptés	Interprétation, puis propagation de pavés d'intervalles	Parcours de graphe, interprète	Python
20	Simuler un circuit d'impulsions, puis attendre un événement très lointain	Simulation avec file, observation de périodes, PPCM	Files, simulation	Python
21	Cases atteignables en un nombre exact de pas, puis sur une grille périodique infinie	BFS par couches, puis formule extrapolée	Parcours en largeur	Python
22	Empiler des briques qui tombent, puis mesurer les effondrements	Graphe de support et accessibilité depuis le sol	Tri topologique, parcours en profondeur	Python
23	Plus long chemin simple dans un labyrinthe	Contraction des couloirs puis retour sur trace	Retour sur trace, graphes	Python
24	Intersections de trajectoires rectilignes, puis une trajectoire qui les touche toutes	Systèmes 2×2 (numpy), puis résolution symbolique (sympy)	Algèbre linéaire, calcul formel	Python
25	Couper trois arêtes pour séparer un graphe en deux	Visualisation, coupe trouvée à l'œil, heuristiques	Coupe minimale, Karger, composantes connexes	Python

Jour 12 — Hot Springs

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

Jour 15 — Lens Library

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

Jour 17 — Clumsy Crucible

Énoncé : adventofcode.com/2023/day/17

Jour 22 — Sand Slabs

Énoncé : adventofcode.com/2023/day/22

Jour 23 — A Long Walk

Énoncé : adventofcode.com/2023/day/23