Advent of Code 2024

Entraînement · Advent of Code 2024 · Python (OCaml pour le jour 7)

Cours : Graphes · Programmation dynamique · Force brute · Dictionnaires · Arbres

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Comparer deux listes d'entiers, puis compter des occurrences	Tri puis appariement	Tri, complexité quadratique	Python
2	Suites presque monotones, avec droit à une suppression	Force brute sur la suppression	Exploration exhaustive	Python
3	Extraire des instructions valides d'un texte bruité	Expression régulière et drapeau	Expressions régulières, drapeau	Python
4	Mots cachés dans une grille de lettres	Balayage des 8 directions	Boucles imbriquées	Python
5	Listes soumises à des contraintes d'ordre	Tri à bulles avec comparateur	Tri à bulles, tri topologique	Python
6	Marcheur qui tourne devant les obstacles ; obstacles créant une boucle	Simulation, détection de cycle sur (position, direction)	Ensembles, grilles	Python
7	Placer des opérateurs pour atteindre une cible	Exploration exhaustive avec élagage	Construction de candidats, élagage	Python, OCaml
8	Points alignés avec des paires d'antennes	Regroupement par clé, marche le long d'une droite	Dictionnaires, ensembles	Python
9	Compacter un disque, bloc par bloc puis fichier par fichier	Deux indices qui se rapprochent ; liste de zones libres	Boucles tant que, complexité	Python
10	Chemins à pente constante dans une carte de hauteurs	Parcours en profondeur avec pile, avec puis sans marquage	Parcours de graphe, piles	Python
11	Suite de nombres qui se dédoublent pendant de nombreuses étapes	Mémoïsation sur (valeur, étapes restantes)	Mémoïsation	Python
12	Aire, périmètre et nombre de côtés des régions d'une grille	Inondation, puis composantes connexes des bords	Flood fill, composantes connexes	Python
13	Combinaison entière positive de deux vecteurs atteignant une cible	Force brute, puis système 2×2 (Cramer)	Exploration exhaustive, arithmétique	Python
14	Robots se déplaçant sur un tore ; repérer une image	Arithmétique modulaire, heuristique « aucune collision »	Dictionnaires, arithmétique modulaire	Python
15	Pousser des caisses, puis des caisses de largeur 2	Simulation, parcours des caisses entraînées	Parcours de graphe, grilles	Python
16	Labyrinthe avec coût de rotation ; cases des chemins optimaux	Dijkstra sur (position, direction)	Dijkstra, file de priorité	Python
17	Petite machine à 3 bits, puis programme qui s'affiche lui-même	Interprète avec arrêt anticipé	Interprète	Python
18	Grille qui se bouche : premier obstacle qui coupe le chemin	Test d'accessibilité répété	Parcours en largeur, connexité	Python
19	Décomposer des mots en motifs, compter les décompositions	Mémoïsation sur le suffixe restant	Mémoïsation	Python
20	Raccourcis sur un circuit ; compter ceux qui font gagner du temps	Deux BFS (départ, arrivée) puis paires à distance de Manhattan bornée	Parcours en largeur	Python
21	Claviers imbriqués : séquence de touches minimale	Expansion des plus courts chemins niveau par niveau (partie 1 seulement)	Plus courts chemins, mémoïsation	Python (brouillon)
22	Générateur pseudo-aléatoire ; meilleure séquence de variations	Fenêtre glissante et dictionnaire de scores	Dictionnaires, hachage	Python
23	Plus grande clique d'un graphe non orienté	Retour sur trace par extension de clique	Graphes complets, exploration exhaustive	Python
24	Circuit booléen ; réparer un additionneur aux fils échangés	Évaluation récursive, unification avec un additionneur modèle	Arbres d'expressions, formules	Python
25	Compatibilité de motifs en colonnes	—	—	—

Jour 7 — Bridge Repair

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

Jour 11 — Plutonian Pebbles

Énoncé : adventofcode.com/2024/day/11

Jour 16 — Reindeer Maze

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

Jour 19 — Linen Layout

Énoncé : adventofcode.com/2024/day/19

Jour 23 — LAN Party

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