Advent of Code 2019

Entraînement · Advent of Code 2019 · Python

Cours : Graphes · Interprète · Algorithme de Dijkstra · Files · Dictionnaires et ensembles

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Appliquer une formule à chaque valeur, puis l'itérer jusqu'à épuisement	Boucle while et somme	Répéter tant que	Python
2	Premier interprète Intcode (addition, multiplication, arrêt)	—	Interprète	—
3	Croisements de deux chemins sur une grille	Intersection de segments deux à deux	Complexité quadratique	Python
4	Compter les nombres d'un intervalle vérifiant des règles sur leurs chiffres	Force brute, test sur la chaîne des chiffres	Exploration exhaustive	Python
5	Interprète Intcode : modes d'adressage, entrées-sorties, sauts	Interprète récursif	Interprète, récursivité terminale	Python
6	Arbre de dépendances : profondeurs, puis distance entre deux nœuds	Chemins depuis la racine, plus long préfixe commun	Arbres, récursivité	Python
7	Plusieurs copies d'un programme Intcode chaînées en boucle	Machines en coroutines reliées par des files, permutations	Files, threads coopératifs	Python
8	Image découpée en calques superposés	Découpage d'une chaîne, superposition	Tableaux	Python
9	Intcode complet : adressage relatif, mémoire non bornée	Mémoire creuse en dictionnaire	Interprète, dictionnaires	Python
10	Visibilité entre points d'une grille, puis balayage angulaire	Directions réduites par PGCD, tri par angle	PGCD, force brute	Python
11	Robot piloté par Intcode qui peint une grille	Simulation, grille en dictionnaire	Dictionnaires, interprète	Python
12	Système de points en interaction, retour à l'état initial	Cycle par coordonnée, PPCM des périodes	Ensembles, PGCD	Python
13	Jeu de casse-briques à faire jouer par un programme Intcode	Contrôle glouton : suivre la balle	Interprète	Python
14	Réactions chimiques : quantité de matière première nécessaire	Tri topologique, propagation de besoins rationnels	Tri topologique	Python
15	Explorer un labyrinthe inconnu en pilotant un robot	DFS avec retour physique du robot, puis BFS	Parcours en profondeur, parcours en largeur	Python
16	Transformation répétée d'une très longue suite de chiffres	Sommes suffixes sur la seconde moitié	Complexité	Python
17	Lire une grille produite par Intcode, puis envoyer un itinéraire compressé	Voisinage sur grille, compression faite à la main	Grilles	Python
18	Ramasser toutes les clés d'un labyrinthe à portes	BFS depuis chaque clé, Dijkstra sur (clé, masque)	Parcours en largeur, Dijkstra	Python
19	Sonder une zone en cône pour y loger un carré	Suivi incrémental des bords, colonne par colonne	Dictionnaires, interprète	Python
20	Labyrinthe à téléporteurs, puis à niveaux emboîtés	BFS, puis graphe réduit et Dijkstra sur (portail, côté, niveau)	Parcours en largeur, Dijkstra	Python
21	Écrire un petit programme booléen pour un robot sauteur	Programme booléen écrit à la main, envoyé en ASCII	Calcul propositionnel	Python
22	Mélanges de cartes répétés un nombre astronomique de fois	Applications affines modulo un nombre premier	Exponentiation rapide, PGCD	Python
23	Réseau de 50 machines Intcode qui s'échangent des paquets	Ordonnancement tour par tour, files, détection d'inactivité	Producteurs-consommateurs, files	Python
24	Automate cellulaire 5×5, puis sur des grilles emboîtées	État codé sur 25 bits, cycle détecté par ensemble	Jeu de la vie, ensembles	Python
25	Jeu d'aventure textuel exécuté par Intcode	Console interactive, essai des \(2^8\) sous-ensembles d'objets	Exploration exhaustive	Python

Jour 7 — Amplification Circuit

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

Jour 12 — The N-Body Problem

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

Jour 16 — Flawed Frequency Transmission

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

Jour 18 — Many-Worlds Interpretation

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

Jour 22 — Slam Shuffle

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