Advent of Code 2016

Entraînement · Advent of Code 2016 · Python

Cours : Graphes · Files · Récursivité · Recherche par force brute

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Marche sur une grille avec virages, premier point revisité	direction modulo 4, liste des positions	Grilles, arithmétique modulaire	Python
2	Déplacements sur un clavier, carré puis en losange	position bornée dans une grille de caractères	Tableaux à deux dimensions	Python
3	Compter les triplets qui forment un triangle	inégalité triangulaire, lecture par colonnes	Instruction conditionnelle	Python
4	Vérifier une somme de contrôle, puis déchiffrer des noms	expression régulière, tri par fréquence, chiffre de César	Expressions régulières	Python
5	Construire un code à partir de hachés MD5	force brute sur MD5	Force brute	Python
6	Caractère le plus ou le moins fréquent par colonne	comptage par colonne et tri	Dictionnaires	Python
7	Motifs à l'intérieur et à l'extérieur de crochets	découpage récursif, fenêtres glissantes	Récursivité, recherche dans un texte	Python
8	Rotations de lignes et colonnes d'un petit écran	simulation, indices modulo la taille	Rotation d'une file	Python
9	Longueur d'un texte décompressé, puis décompression imbriquée	pile de caractères, puis longueur récursive sans décompresser	Piles, récursivité	Python
10	Robots qui se passent des jetons selon des règles	propagation jusqu'au point fixe	Graphes orientés, simulation	Python
11	Transporter des objets entre étages sous contrainte	BFS sur les états du casse-tête	Parcours en largeur	Python
12	Exécuter un programme pour une machine à quatre registres	interprète	Interprète	Python
13	Plus court chemin dans un labyrinthe défini par une formule	BFS sur grille implicite	Parcours en largeur	Python
14	Clés repérées par des motifs dans des hachés successifs	fenêtre glissante de 1000 hachés dans une file	Files	Python
15	Instant où des disques tournants sont tous alignés	recherche linéaire sur des congruences	Arithmétique modulaire	Python
16	Courbe du dragon, puis somme de contrôle par réductions	doublement de chaîne, réduction par paires	Complexité	Python
17	Chemins dans une petite grille dont les portes dépendent d'un haché	BFS sur (position, chemin)	Parcours en largeur	Python
18	Lignes successives d'un automate cellulaire à une dimension	règle locale sur trois cases	Automate cellulaire	Python
19	Élimination en cercle (variante de Josèphe)	deux files pour les deux moitiés du cercle	Files	Python
20	Entiers non couverts par une liste d'intervalles	soustraction d'intervalles	Droite de balayage	Python
21	Brouiller une chaîne par des opérations, puis défaire le brouillage	simulation, inversion des opérations	Listes	Python
22	Déplacer une donnée dans une grille de nœuds de stockage	taquin : BFS successifs sur la case vide	Parcours en largeur	Python
23	Assembleur auto-modifiant	interprète avec raccourci de multiplication	Interprète	Python
24	Visiter tous les points marqués d'un plan	BFS entre points, puis permutations	Parcours en largeur, optimisation exhaustive	Python
25	Plus petite entrée pour laquelle un programme émet un signal alterné	interprète et essais successifs	Interprète, problème de l'arrêt	Python

Jour 9 — Explosives in Cyberspace

Énoncé : adventofcode.com/2016/day/9

Jour 11 — Radioisotope Thermoelectric Generators

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

Jour 19 — An Elephant Named Joseph

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

Jour 24 — Air Duct Spelunking

Énoncé : adventofcode.com/2016/day/24