Advent of Code 2018

Entraînement · Advent of Code 2018 · Python

Cours : Graphes · Algorithme de Dijkstra · Arbres · Interprète · Automates cellulaires

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Sommes partielles, première valeur répétée	ensemble des sommes vues	Ensembles	— (Entraînement)
2	Lettres répétées, puis deux identifiants presque égaux	comptages, comparaison de toutes les paires	Boucles imbriquées	Python
3	Rectangles superposés sur un tissu	dictionnaire de compteurs par case	Dictionnaires	Python
4	Journal horodaté : quel garde dort, et à quelle minute	tri lexicographique, histogramme par minute	Dictionnaires, expressions régulières	Python
5	Réduire une chaîne par annulation de paires voisines	pile	Piles	— (Entraînement)
6	Partage d'une grille entre points (distance de Manhattan)	force brute sur une grille bornée	Force brute	— (Entraînement)
7	Ordonner des tâches dépendantes, puis avec plusieurs ouvriers	compteurs de prédécesseurs (Kahn), simulation seconde par seconde	Tri topologique	Python
8	Arbre sérialisé dans une suite d'entiers	lecture récursive avec indice	Arbres, descente récursive	Python
9	Jeu de billes placées dans un cercle	deque avec rotations	Rotation d'une file	Python
10	Points mobiles qui finissent par écrire un message	simulation, affichage quand la boîte englobante est petite	Simulation	Python
11	Carré de somme maximale dans une grille calculée	sommes des carrés construites taille par taille	Programmation dynamique, complexité	Python
12	Automate cellulaire sur une ligne infinie, à très long terme	dictionnaire creux, régime linéaire observé	Automates cellulaires	Python
13	Wagonnets sur un réseau de rails, collisions	rails décomposés en rectangles, simulation	Simulation, grilles	Python
14	Suite de chiffres engendrée, recherche d'un motif	tableau d'octets, comparaison de la fin	Tableaux dynamiques, recherche dans un texte	Python
15	Combat d'unités sur une grille	BFS pour chaque déplacement, recherche du bonus d'attaque	Parcours en largeur	Python
16	Identifier les codes d'opération à partir d'exemples	intersections d'ensembles, propagation des singletons	Ensembles, couplage	Python
17	Écoulement d'eau dans un sol argileux	remplissage itéré avec pile explicite	Flood fill	Python
18	Automate cellulaire sur un milliard d'étapes	détection de cycle, réduction modulo la période	Automates cellulaires, dictionnaires	Python
19	Programme trop lent pour un processeur à six registres	interprète, puis traduction à la main	Interprète	Python
20	Plan décrit par une expression régulière	descente récursive, BFS sur les préfixes reconnus	Expressions régulières, descente récursive, parcours en largeur	Python
21	Valeurs qui font s'arrêter un programme	traduction à la main, détection de cycle	Interprète, problème de l'arrêt	Python
22	Grotte calculée, puis trajet avec changements d'outil	mémoïsation, Dijkstra sur (case, outil)	Mémoïsation, Dijkstra	Python
23	Zones octaédriques (distance de Manhattan en 3D)	comptage direct, puis heuristique sur les sommets	Force brute, géométrie	Python (partie 2 incomplète)
24	Combat entre deux armées de groupes	simulation par classes, dichotomie sur le bonus	Recherche dichotomique	Python
25	Regrouper des points 4D proches	composantes connexes par parcours avec pile	Composantes connexes	Python

Jour 8 — Memory Maneuver

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

Jour 18 — Settlers of The North Pole

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

Jour 20 — A Regular Map

Énoncé : adventofcode.com/2018/day/20

Jour 22 — Mode Maze

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