Advent of Code 2015

Entraînement · Advent of Code 2015 · Python

Cours : Programmation dynamique · Recherche par force brute · Récursivité · Dictionnaires et ensembles

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

Vue d'ensemble

Jour	Nature du problème	Méthode	Notions du cours	Solution
1	Suivre un niveau qui monte et descend au fil d'une chaîne	compteur, premier passage sous zéro	Accumulateur	Python
2	Surfaces et longueurs calculées sur des pavés	formules fermées, minimum de trois valeurs	Accumulateur	Python
3	Cases visitées par un ou deux marcheurs sur une grille	ensemble de coordonnées	Ensembles	Python
4	Chercher un entier dont le haché commence par des zéros	force brute sur MD5	Force brute	Python
5	Classer des chaînes selon des motifs	balayage de fenêtres de 2 ou 3 caractères	Recherche dans un texte	Python
6	Opérations sur des rectangles d'une grille de lampes	simulation case par case dans un dictionnaire	Boucles imbriquées, dictionnaires	Python
7	Évaluer un circuit logique sur 16 bits	évaluation récursive mémoïsée	Mémoïsation, arbres d'expressions	Python
8	Longueurs de chaînes avec séquences d'échappement	analyse caractère par caractère	Lecture de chaînes (entrées-sorties)	Python
9	Tournée la plus longue passant par toutes les villes	retour sur trace sur les chemins	Retour sur trace, chemins	Python
10	Itérer la suite « lire et dire »	codage par plages avec groupby	Complexité exponentielle	Python
11	Prochaine chaîne valide dans l'ordre alphabétique	incrémentation en base 26 avec sauts	Force brute	Python
12	Sommer les nombres d'un document JSON avec filtrage	parcours récursif d'un arbre	Types inductifs, arbres	Python
13	Placer des convives autour d'une table	toutes les permutations	Optimisation exhaustive	Python
14	Course entre coureurs alternant effort et repos	formule fermée, puis simulation seconde par seconde	Accumulateur, simulation	Python
15	Meilleure répartition d'une quantité entre ingrédients	énumération des compositions de 100	Optimisation exhaustive	Python
16	Trouver la fiche compatible avec des indices	filtrage avec contraintes d'égalité ou d'inégalité	Dictionnaires	Python
17	Compter les façons d'atteindre un volume avec des récipients	mémoïsation sur (indice, reste)	Programmation dynamique	Python
18	Automate cellulaire sur une grille, coins bloqués	double tampon de grilles	Jeu de la vie	Python
19	Réécriture de molécules : voisins, puis nombre minimal d'étapes	ensemble des réécritures, puis invariant linéaire résolu avec sympy	Grammaires, ensembles	Python
20	Plus petit entier dont une somme de diviseurs dépasse un seuil	crible, puis recherche linéaire sur les diviseurs	Arithmétique, force brute	Python
21	Choisir un équipement pour gagner (ou perdre) un duel	énumération des équipements, issue du combat par formule	Optimisation exhaustive	Python
22	Duel avec sorts et effets : dépense minimale	récursion mémoïsée sur l'état complet du combat	Mémoïsation, retour sur trace	Python
23	Exécuter un programme pour une machine à deux registres	interprète avec compteur ordinal	Interprète	Python
24	Répartir des paquets en groupes de même poids	combinaisons par taille croissante	Construction de candidats	Python
25	Valeur d'une suite à une case d'un tableau rempli en diagonales	numérotation de Cantor, itération modulaire	Arithmétique modulaire	Python

Jour 7 — Some Assembly Required

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

Jour 17 — No Such Thing as Too Much

Énoncé : adventofcode.com/2015/day/17

Jour 19 — Medicine for Rudolph

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

Jour 22 — Wizard Simulator 20XX

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