Advent of Code 2020

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

Cours : Graphes · Programmation dynamique · Grammaires non contextuelles · Dictionnaires et ensembles

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Trouver deux puis trois nombres d'une liste de somme donnée	boucles imbriquées (C), ensemble des compléments (Python)	Force brute, ensembles	C, Python
2	Valider des lignes selon une règle donnée sur chaque ligne	lecture formatée, comptage d'occurrences, ou exclusif	Lecture et découpage de chaînes (entrées-sorties)	C, OCaml, Python
3	Parcours en diagonale d'une grille périodique	pas constant, abscisse modulo la largeur	Tableaux à deux dimensions, modulo	C
4	Validation d'enregistrements champ par champ	masque de bits des champs (C), dictionnaire par fiche (Python)	Dictionnaires, analyse de chaînes	C, Python
5	Décodage d'un code qui est une écriture binaire déguisée	dichotomie, tableau de places occupées	Représentation des entiers en base 2, dichotomie	C, Python
6	Unions et intersections d'ensembles de lettres par groupe	compteur par lettre (C), ensembles (Python)	Ensembles	C, Python
7	Relation de contenance : accessibilité et dénombrement dans un graphe sans cycle	parcours récursif, mémoïsé en Python	Parcours de graphe, mémoïsation	C, Python
8	Interprète d'un mini-assembleur, détection de boucle infinie	simulation avec marquage des instructions exécutées, essai de chaque modification	Interprète, arrêt	C, Python
9	Sommes de paires sur une fenêtre glissante, puis sous-tableau contigu de somme donnée	fenêtre glissante, deux pointeurs	Force brute, complexité	C, Python
10	Écarts dans une liste triée, puis dénombrement de chaînes compatibles	tri, programmation dynamique ascendante (C) ou mémoïsée (OCaml)	Programmation dynamique	C, OCaml
11	Automate cellulaire sur une grille jusqu'à stabilisation	double tampon jusqu'au point fixe, rayons dans 8 directions	Jeu de la vie, tableaux	C, Python
12	Déplacement d'un navire avec rotations	état (position, direction), rotations d'un quart de tour	Simulation, programmation impérative	Python
13	Synchronisation de périodes : système de congruences	recherche linéaire, puis restes chinois par Euclide étendu	Arithmétique modulaire (restes chinois)	Python
14	Masques appliqués à l'écriture binaire d'entiers	—	—	—
15	Suite définie par le dernier rang d'apparition de chaque terme	—	—	—
16	Contraintes d'intervalles, puis attribution des champs par élimination	filtrage, puis élimination des candidats par ordre de taille	Couplage dans un graphe biparti	Python
17	Automate cellulaire en dimension 3 puis 4	dictionnaire par défaut sur une boîte englobante croissante	Ensembles, jeu de la vie	Python
18	Évaluer des expressions arithmétiques avec des priorités inhabituelles	descente récursive, un niveau par priorité	Descente récursive, arbres d'expressions	Python
19	Reconnaître les mots engendrés par une grammaire donnée	filtrage récursif de préfixes, comptage de blocs en partie 2	Grammaires, expressions régulières	Python
20	Assembler un puzzle de tuiles avec rotations et symétries, puis chercher un motif	retour sur trace case par case sur (tuile, symétrie, rotation)	Retour sur trace	Python
21	Déduire une correspondance par intersections d'ensembles et élimination	intersections, propagation des candidats uniques	Ensembles	Python
22	Jeu de cartes, puis version récursive avec détection de configurations répétées	files à double extrémité, historique des configurations, récursion sur copies	Files, ensembles, récursivité	Python
23	Millions de déplacements dans une liste circulaire	liste doublement chaînée circulaire et tableau valeur → maillon	Listes chaînées	Python
24	Coordonnées sur une grille hexagonale, puis automate cellulaire	coordonnées demi-entières, dictionnaire des cases noires	Dictionnaires, jeu de la vie	Python
25	Retrouver un exposant modulaire (logarithme discret)	recherche exhaustive de l'exposant	Force brute, arithmétique modulaire	Python

Jour 7 — Handy Haversacks

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

Jour 8 — Handheld Halting

Énoncé : adventofcode.com/2020/day/8

Jour 10 — Adapter Array

Énoncé : adventofcode.com/2020/day/10

Jour 18 — Operation Order

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

Jour 19 — Monster Messages

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