Défis Advent of Code#

Diviser pour régner

Défi 1 Report Repair#

la note de frais — parcours de listes et complexité

Jour 1

Fichiers à télécharger

Consignes

L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2020/day/1 . On peut le lire en anglais ou le faire traduire par le navigateur (clic droit, Traduire en français).
Avec un compte (GitHub, Google…), le bouton get your puzzle input donne votre fichier de données, à enregistrer sous input.txt à côté de votre programme. Sans compte : le dossier du défi (lien ci-dessus) contient des données maison (input.txt) et le programme verifier.py, qui dit si vos réponses sont justes.
La partie 2 n’apparaît qu’une fois la partie 1 validée sur le site.
L’IA peut aider à comprendre un message d’erreur, jamais à écrire la solution.

Ce défi fait comparer plusieurs méthodes et leur coût, comme dans ce chapitre : double boucle, ensemble, et tri suivi d’un parcours par les deux bouts. Ce tri coûte \(O(n\log n)\) grâce à un algorithme « diviser pour régner » comme le tri fusion du cours.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


expense report	note de frais	entry	ligne, valeur du fichier
accounting	comptabilité	sum to	avoir pour somme
fix up	corriger	multiply	multiplier
puzzle input	vos données (fichier personnel)	star	étoile (une par partie réussie)

Résumé de l’énoncé (partie 1)

Contexte. Avant de partir en vacances, vous devez régler un dernier problème : les elfes de la comptabilité ont une note de frais qui ne tombe pas juste et vous demandent de les aider à la corriger. Le fichier de données est cette note de frais : chaque ligne est une dépense, c’est-à-dire un entier positif.

Ce qu’il faut faire.

Parmi toutes les dépenses, exactement deux lignes ont des valeurs dont la somme vaut 2020. Autrement dit, il faut trouver la seule paire de lignes différentes qui « complètent » 2020.
La réponse à donner sur le site est le produit de ces deux valeurs.

Exercice 1 — Vérifier sa compréhension #

Si le fichier contient une seule fois la valeur 1010, peut-elle former la paire avec elle-même ?
L’ordre des lignes dans le fichier a-t-il une importance pour la réponse ?

Exercice 2 — À la main, sur un petit exemple #

On considère le fichier (inventé) suivant :

Trouver à la main la réponse attendue. Vérification : on doit obtenir 980896. Pourquoi la ligne 1010 ne donne-t-elle pas de solution à elle seule ?

Programmer la partie 1#

Exercice 3 — Lire le fichier #

Écrire les lignes qui lisent input.txt et construisent la liste nombres des entiers qu’il contient. Afficher sa longueur pour vérifier.

Outil Python : strip (nettoyer une ligne lue)

Chaque ligne renvoyée par readlines() se termine par le caractère de fin de ligne "\n" (sauf parfois la dernière). ligne.strip() renvoie une copie de la ligne sans les espaces ni les fins de ligne placés au début et à la fin.

ligne = "1721\n"
print(ligne.strip())                  # 1721
print(len(ligne), len(ligne.strip())) # 5 4

Intérêt. Comparer ou découper une ligne sans que la fin de ligne ne gêne : "abc\n" == "abc" vaut False.

Exercice 4 — Une première solution #

Écrire une fonction paire_2020(nombres) qui renvoie le produit des deux valeurs recherchées. Tester sur l’exemple du défi, puis sur vos données.

Coup de pouce

Deux boucles imbriquées sur les indices i et j, avec j > i pour ne jamais prendre deux fois la même ligne.

Exercice 5 — Combien d’opérations ? #

Le fichier contient environ \(200\) nombres. Combien de paires la fonction précédente examine-t-elle au pire ? Quelle est sa complexité en fonction de \(n\) ?

Partie 2#

Une fois la partie 1 validée, lire la suite de l’énoncé sur le site.

Résumé de la partie 2 (à lire après avoir validé la partie 1)

Les elfes sont ravis, mais il leur reste une ancienne note de frais à vérifier selon une autre règle. Même fichier : il faut cette fois trouver les trois lignes différentes dont les valeurs ont pour somme 2020, et donner le produit de ces trois valeurs.

Exercice 6 — La partie 2 #

Adapter le programme pour répondre à la nouvelle question. Sur l’exemple du défi, on doit trouver 24106500.

Coup de pouce

Une boucle de plus. Combien de triplets pour \(n = 200\) ? C’est encore rapide.

Approfondissement#

Outil Python : les ensembles (set) — rappel

Tout est présenté dans l’encadré « Outil Python : les ensembles » du défi Crab Combat (chapitre 4). On n’utilise ici que set() (ensemble vide), add, remove et le test x in ensemble, en temps constant (en moyenne). Les éléments doivent être non modifiables (nombres, chaînes, tuples).

À essayer. Avec vus = {812, 1208}, que valent 812 in vus et 2020 - 812 in vus ? Sur un million d’éléments, la différence de temps avec une liste est énorme.

★★ Exercice 7 — Approfondissement 1 : une seule boucle grâce à un ensemble #

Recopier puis exécuter le code de l’encadré du défi Crab Combat (chapitre 4). Que se passe-t-il si l’on ajoute deux fois 1208 à un ensemble ?
Écrire paire_rapide(nombres) qui résout la partie 1 avec une seule boucle et un ensemble vus. Quelle est sa complexité ?

Coup de pouce

Pour chaque nombre x, la seule valeur qui le complète est 2020 - x. Il suffit de savoir si on l’a déjà rencontrée.

Coup de pouce 2 (début de solution)

On parcourt les nombres un par un ; avant d’ajouter x à l’ensemble vus, on regarde si 2020 - x y est déjà. Tester avant d’ajouter évite d’utiliser deux fois la même ligne.
En déduire une solution de la partie 2 en \(O(n^2)\) au lieu de \(O(n^3)\).

Coup de pouce

Généraliser la fonction avec un paramètre cible : pour chaque x, chercher une paire de somme 2020 - x parmi les nombres suivants.

★★ Exercice 8 — Approfondissement 2 : trier puis rapprocher deux indices #

Une autre idée, sans ensemble, réinvestit le tri : avec le tri fusion de ce chapitre, il coûte \(O(n\log n)\). On trie la liste, puis on place un indice g au début et un indice d à la fin.

Sur la liste triée [33, 487, 812, 1010, 1208, 1500], on a g = 0 et d = 5 : la somme vaut \(33 + 1500 = 1533\), trop petite. Faut-il avancer g ou reculer d ? Justifier, puis dérouler la méthode à la main jusqu’à trouver la paire.
Écrire paire_triee(nombres, cible) qui applique cette méthode (on travaille sur une copie triée, obtenue avec votre fonction tri_fusion du cours, qui renvoie une nouvelle liste) et renvoie le produit, ou None s’il n’y a pas de paire.

Coup de pouce

Tant que g < d : si la somme est trop petite, la seule façon de l’augmenter est d’avancer g ; si elle est trop grande, reculer d.

Coup de pouce 2 (début de solution)

Si t[g] + t[d] < cible, alors t[g] associé à n’importe quel élément situé avant d donne aussi une somme trop petite : t[g] ne peut faire partie d’aucune paire, on peut l’écarter.
Quelle est la complexité totale (tri compris) ? Comparer avec les deux méthodes précédentes.
Utiliser paire_triee pour résoudre la partie 2 en \(O(n^2)\), sans ensemble.

Défi 2 Encoding Error#

la faille du chiffrement — fenêtre glissante et complexité

Jour 9

Fichiers à télécharger

dossier en ligne archive .zip

Consignes

L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2020/day/9 . On peut le lire en anglais ou le faire traduire par le navigateur (clic droit, Traduire en français).
Avec un compte (GitHub, Google…), le bouton get your puzzle input donne votre fichier de données, à enregistrer sous input.txt à côté de votre programme. Sans compte : le dossier du défi (lien ci-dessus) contient des données maison (input.txt) et le programme verifier.py, qui dit si vos réponses sont justes.
La partie 2 n’apparaît qu’une fois la partie 1 validée sur le site.
L’IA peut aider à comprendre un message d’erreur, jamais à écrire la solution.

Ce défi prolonge le défi précédent (Report Repair) et l’analyse de complexité de ce chapitre : comme le tri fusion détrône les tris quadratiques, une meilleure idée (deux indices qui ne font qu’avancer) remplace une recherche quadratique par un parcours linéaire. La fenêtre glissante reviendra au chapitre 12, avec la recherche naïve d’un motif dans un texte.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


preamble	préambule	previous	précédent
sum of any two	somme de deux quelconques	different	différent
weakness	faiblesse, faille	valid / invalid	valide / invalide
contiguous set	suite contiguë	at least two	au moins deux

Résumé de l’énoncé (partie 1)

Contexte. Le héros branche son ordinateur sur une prise de données de l’avion. Il en sort une longue suite de nombres (le fichier, un entier par ligne), chiffrée avec un vieux procédé qui a une faille. Dans ce procédé, chaque nombre doit pouvoir s’obtenir à partir des nombres reçus juste avant lui : un nombre qui ne le peut pas trahit l’erreur.

Ce qu’il faut faire.

Les 25 premiers nombres forment le préambule (le petit exemple de l’énoncé en utilise 5). Ils ne sont pas testés.
Chaque nombre suivant doit être la somme de deux nombres de valeurs différentes pris parmi les 25 qui le précèdent immédiatement. Autrement dit, on regarde une fenêtre de 25 nombres qui glisse d’un cran à chaque nouveau nombre.
Il faut renvoyer le premier nombre qui ne respecte pas la règle.

Exercice 1 — Comprendre ce qui est demandé #

Après lecture de l’énoncé et du résumé, vérifier sa compréhension :

La fenêtre contient 3 7 10 7 2. Le nombre suivant 14 est-il valide ?
Avec un préambule de longueur \(p\), quels indices forment la fenêtre du nombre d’indice \(i\) ?
La paire peut-elle utiliser un nombre sorti de la fenêtre ?

Exercice 2 — À la main, sur un petit exemple #

On considère la liste (inventée) suivante, avec un préambule de longueur \(5\) :

6  3  7  11  1  13  24  8  25  33  37  62  70  58  22

Vérifier à la main les nombres situés après le préambule, en écrivant à chaque fois la fenêtre des 5 nombres précédents et une paire qui convient. Vérification : le premier nombre invalide est 22.

Programmer la partie 1#

Exercice 3 — Somme de deux #

Écrire une fonction somme_de_deux(fenetre, cible) qui renvoie True si deux éléments de la liste fenetre ont pour somme cible, en respectant la règle des valeurs différentes. L’essayer avec des assert sur des cas simples.

Coup de pouce

Deux boucles sur les indices, avec j > i, comme pour le jour 1, et un test sur les valeurs des deux éléments.

Exercice 4 — La fenêtre glissante #

Écrire une fonction premier_invalide(nombres, p) où p est la longueur du préambule. Tester avec p = 5 sur l’exemple du défi, puis avec la bonne longueur sur vos données.

Coup de pouce

Pour le nombre d’indice i, la fenêtre est la tranche nombres[i - p:i]. Faire un petit dessin pour vérifier les bornes.

Partie 2#

Une fois la partie 1 validée, lire la suite de l’énoncé sur le site.

Résumé de la partie 2 (à lire après avoir validé la partie 1)

Pour exploiter la faille, il faut se servir du nombre fautif trouvé en partie 1.

Trouver une suite d’au moins deux nombres consécutifs du fichier dont la somme vaut ce nombre.
Il faut renvoyer la somme du plus petit et du plus grand nombre de cette suite (ce ne sont pas forcément le premier et le dernier).

Exercice 5 — Une première solution #

Écrire une fonction qui cherche la suite demandée en essayant toutes les positions de début et de fin. Sur l’exemple du défi, on doit trouver 12.

Coup de pouce

Une suite contiguë, c’est une tranche nombres[debut:fin]. Attention : la suite réduite au seul nombre invalide ne compte pas. Le plus petit et le plus grand nombre de la tranche se trouvent avec une boucle, comme une recherche de maximum.

Exercice 6 — Deux indices #

Les nombres de vos données sont tous positifs. Expliquer pourquoi on peut alors trouver la suite avec seulement deux indices debut et fin qui ne font qu’avancer, en tenant à jour la somme de la tranche. Programmer cette méthode et comparer sa complexité à celle de l’exercice précédent.

Coup de pouce

Si la somme courante est trop petite, on ajoute le nombre suivant (fin avance) ; si elle est trop grande, on retire le premier (debut avance).

Coup de pouce 2 (début de solution)

Chaque indice avance au plus \(n\) fois : la méthode est linéaire. La boucle while s’arrête quand la somme est atteinte avec au moins deux nombres.

Approfondissement#

Outil Python : mesurer une durée (time) et tirer au hasard (random)

Le module time fournit un chronomètre précis ; le module random tire des nombres au hasard, utile pour fabriquer de grosses données de test.

import random
import time

def somme_entiers(n):
    """Somme des entiers de 0 a n - 1, calculee par une boucle."""
    total = 0
    for k in range(n):
        total += k
    return total

x = random.randint(1, 6)         # entier au hasard entre 1 et 6 (bornes comprises)
liste = [random.randint(1, 1000) for _ in range(5)]
depart = time.perf_counter()     # top depart (en secondes)
total = somme_entiers(10**6)
duree = time.perf_counter() - depart
print(f"{duree:.4f} s")          # 4 chiffres apres la virgule

Intérêt. Vérifier expérimentalement une complexité : si l’on double \(n\), une méthode linéaire prend environ deux fois plus de temps, une méthode quadratique environ quatre fois plus. Une mesure isolée varie : la répéter.

À essayer. Mesurer somme_entiers(10**6) puis somme_entiers(2 * 10**6) : le rapport des durées est-il proche de 2 ?

★★★ Exercice 7 — Défi : mesurer #

Mesurer avec le module time la durée des deux méthodes de la partie 2 sur vos données, puis sur une liste aléatoire de \(10\,000\) nombres. Les mesures sont-elles cohérentes avec les complexités annoncées ?

Coup de pouce

time.perf_counter() avant et après l’appel ; la différence donne la durée en secondes.

Outil Python : les ensembles (set) — rappel

Tout est présenté dans l’encadré « Outil Python : les ensembles » du défi Crab Combat (chapitre 4) : ensemble vide set(), ajout avec add, retrait avec remove, test x in ensemble en temps constant, éléments non modifiables (tuples). Un ensemble ne contient jamais deux fois le même élément.

À essayer. Avec fenetre = [3, 7, 10, 7, 2], que vaut set(fenetre) ? Combien d’éléments ?

★★ Exercice 8 — Approfondissement 1 : la partie 1 avec un ensemble #

À la main : avec la fenêtre 3 7 10 7 2 et la cible 13, calculer pour chaque x la valeur 13 - x et dire si elle est dans la fenêtre. Recommencer avec la cible 14 : pourquoi le complément 7 de 7 ne convient-il pas ?
Écrire somme_de_deux_ensemble(fenetre, cible) avec une seule boucle et un ensemble, puis l’utiliser pour retrouver 22 sur l’exemple du défi.
Pour \(p = 25\), combien de tests environ fait chaque version pour un nombre ? En déduire les complexités totales.

Coup de pouce

Pour chaque x de la fenêtre, la seule valeur qui le complète est cible - x.

Coup de pouce 2 (début de solution)

Construire valeurs = set(fenetre), puis tester cible - x in valeurs sans oublier la règle des valeurs différentes : cible - x != x.