Aller au contenu

Défis Advent of Code#

Bases de données et SQL

Défi 1 Passport Processing#

les passeports — dictionnaires et validation

Jour 4

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/4 . 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 écho à la notion de domaine vue dans ce chapitre : chaque champ d’un passeport n’est valide que si sa valeur appartient à un domaine précis.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :
field champ required obligatoire
missing manquant optional facultatif
batch file fichier de lot blank line ligne vide
key:value pair paire clé:valeur at least / at most au moins / au plus

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

Contexte. Arrivé à l’aéroport, le héros s’aperçoit qu’il a emporté une carte d’identité du pôle Nord, et non son passeport. La file devant les scanners automatiques est interminable, car ces machines vérifient mal les documents. Le fichier contient les données lues par un scanner : chaque passeport y est décrit par une suite de champs (année de naissance, taille, couleur des yeux…). Il faut écrire le programme qui décide si un document est acceptable.

Ce qu’il faut faire.

  • Les passeports sont séparés par une ligne vide ; un même passeport peut s’étaler sur plusieurs lignes.

  • Un passeport est une suite de champs cle:valeur, séparés par des espaces ou des retours à la ligne, dans un ordre quelconque.

  • Il existe huit clés : byr (année de naissance), iyr (année de délivrance), eyr (année d’expiration), hgt (taille), hcl (couleur des cheveux), ecl (couleur des yeux), pid (numéro de passeport) et cid (pays).

  • En partie 1, un passeport est valide si les sept premières clés sont présentes ; cid peut manquer, ce qui laisse passer la carte du héros. Les valeurs ne sont pas encore examinées.

  • Il faut renvoyer le nombre de passeports valides.

Exercice 1 — Comprendre ce qui est demandé #

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

  1. Un passeport qui possède les huit champs mais contient byr:abc est-il valide en partie 1 ?

  2. Un passeport de sept champs, parmi lesquels cid, est-il valide ?

  3. Lire le fichier ligne par ligne rend-il le découpage en passeports facile ? Pourquoi ?

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

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

byr:1985 hgt:172cm ecl:grn
pid:004512398 iyr:2015 eyr:2027 hcl:#a97842

iyr:2018 hcl:#18171d byr:2001
ecl:blu eyr:2029 pid:765432109

hgt:64in pid:12345678 cid:99 ecl:hzl
hcl:#cc33ff byr:1950 iyr:2012 eyr:2023

eyr:2031 ecl:oth byr:1999 iyr:2014 pid:000000042 hcl:#0a0b0c hgt:190cm

hcl:#623a2f pid:543210987 eyr:2025 byr:1932
iyr:2019 ecl:amb hgt:158cm cid:7

Combien de passeports contient-il ? Lesquels sont valides selon la partie 1 ? Vérification : on doit en trouver 4.

Programmer la partie 1#

Exercice 3 — Séparer les passeports #

Lire tout le fichier en une chaîne et construire la liste des blocs de texte, un bloc par passeport. Afficher le nombre de blocs.

Coup de pouce

Une ligne vide, c’est deux retours à la ligne consécutifs : texte.split("\n\n").

Exercice 4 — Un passeport, un dictionnaire #

Écrire une fonction lire_passeport(bloc) qui renvoie un dictionnaire, par exemple {"byr": "1985", "hgt": "172cm", ...}. Garder les valeurs sous forme de chaînes.

Coup de pouce

bloc.split() sans argument coupe à la fois aux espaces et aux retours à la ligne. Chaque morceau se coupe ensuite en deux au :.

Rappel : « tous » avec un booléen drapeau

La méthode est présentée dans l’encadré « Méthode : « tous » ou « au moins un », avec un booléen drapeau » du défi Handy Haversacks (chapitre 1) : pour vérifier que toutes les valeurs conviennent, on part d’un booléen à True, que la boucle passe à False au premier contre-exemple.

À essayer. Écrire complet(passeport) avec un drapeau tout_present. Que renvoie-t-elle si la liste des clés obligatoires est vide ?

Exercice 5 — Compter les passeports complets #

Écrire complet(passeport) qui vérifie la présence des champs obligatoires, puis compter. Tester sur l’exemple du défi, puis sur vos données.

Coup de pouce

Ranger les clés obligatoires dans une liste et tester chacune avec l’opérateur in, qui teste la présence d’une clé dans un dictionnaire.

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)

Des documents absurdes passent encore : il faut maintenant contrôler aussi les valeurs. Un passeport est valide si les sept clés sont présentes et si :

  • byr est entre 1920 et 2002, iyr entre 2010 et 2020, eyr entre 2020 et 2030 (quatre chiffres, bornes comprises) ;

  • hgt est un nombre suivi de cm (de 150 à 193) ou de in (de 59 à 76) ;

  • hcl est # suivi d’exactement six caractères parmi 0-9 et a-f ; ecl vaut exactement l’un de amb blu brn gry grn hzl oth ;

  • pid compte exactement neuf chiffres (zéros de tête compris) ; cid est ignoré.

Méthode : tester la forme d’une chaîne (boucle drapeau, tranches)

Pour savoir si une chaîne ne contient que des chiffres, on la parcourt avec un booléen drapeau (« tous ») ; les comparaisons de tranches testent le début ou la fin. Tout cela renvoie un booléen qui décrit la forme de la chaîne, sans la convertir.

def que_des_chiffres(s):
    """Renvoie True si s est non vide et ne contient que des chiffres."""
    if len(s) == 0:
        return False
    ok = True
    for c in s:
        if c not in "0123456789":
            ok = False
    return ok

print(que_des_chiffres("2019"))   # True : que des chiffres
print(que_des_chiffres("-12"))    # False : le signe n'est pas un chiffre
print(que_des_chiffres(""))       # False : chaine vide
taille = "172cm"
print(taille[-2:] == "cm")      # True : les 2 derniers caracteres
print(taille[:1] == "#")        # False : le premier caractere
print(taille[:-2], taille[-2:]) # 172 cm : tranches avec indices negatifs

Intérêt. Vérifier la forme d’une chaîne avant d’appeler int, qui provoque une erreur sur "abc" ou "170cm".

À essayer. Que renvoient int("0042") et que_des_chiffres("0042") ?

Outil Python : ranger des fonctions dans un dictionnaire

En Python, une fonction est une valeur comme une autre : on peut la ranger dans une variable, une liste ou un dictionnaire, puis l’appeler plus tard.

def double(x):
    return 2 * x

def carre(x):
    return x * x

operations = {"double": double, "carre": carre}   # sans parentheses
for nom, f in operations.items():
    print(nom, f(5))      # double 10, puis carre 25

Intérêt. Une seule boucle applique à chaque champ la règle qui lui correspond ; ajouter une règle revient à ajouter une ligne au dictionnaire.

À essayer. Que contient le dictionnaire si l’on écrit {"double": double(5)} ?

Exercice 6 — Une fonction par règle #

  1. Pour chaque champ, écrire une fonction de validation : valide_byr(valeur), valide_hgt(valeur), etc. Pour chacune, écrire au moins un assert qui doit réussir et un qui doit échouer, en visant les valeurs limites.

  2. Écrire valide(passeport) qui combine le tout, puis compter. Sur l’exemple du défi, on doit trouver 2 passeports valides.

Coup de pouce

Penser aux chaînes pièges : une taille sans unité, un identifiant trop court, une couleur en majuscules… La fonction que_des_chiffres de l’encadré « Méthode » et les tranches valeur[:-2] et valeur[-2:] sont utiles.

Coup de pouce 2 (début de solution)

Un dictionnaire peut associer chaque nom de champ à sa fonction de validation : regles = {"byr": valide_byr, ...}. On parcourt alors regles.items() et on appelle fonction(passeport[cle]).

Approfondissement#

★★★ Exercice 7 — Défi : décrire la forme par un motif #

Plusieurs règles décrivent la forme d’une chaîne, caractère par caractère. On la résume par un motif : dans un motif, 9 désigne un chiffre quelconque, h un caractère hexadécimal (0 à 9 ou a à f) et tout autre caractère doit être recopié tel quel. Par exemple "#hhhhhh" décrit hcl et "99h99" accepte "08a30" mais ni "8a30" ni "08g30".

  1. Écrire respecte(motif, valeur) qui renvoie True si valeur a la forme décrite par motif.

  2. Réécrire valide_hcl, valide_pid et la vérification des années avec respecte. Les tests écrits plus haut doivent toujours passer.

Coup de pouce

Commencer par comparer les longueurs, puis parcourir les deux chaînes en parallèle avec un indice i.

Coup de pouce 2 (début de solution)

Les tests de la partie 2 servent ici de filet de sécurité : on modifie le code, on relance les assert.

Défi 2 Ticket Translation#

les billets de train — dictionnaires et ensembles

Jour 16

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/16 . 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 écho aux contraintes de domaine vues dans ce chapitre : chaque champ d’un billet n’accepte que certaines valeurs, et l’on s’en sert pour écarter les enregistrements incohérents.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :
ticket billet field champ
range intervalle inclusive bornes comprises
nearby voisin, proche invalid non valide
scanning error rate taux d’erreur de lecture comma-separated séparé par des virgules
determine déterminer position position, rang

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

Contexte. Votre trajet passe par un train à grande vitesse, mais le billet est écrit dans une langue inconnue : vous ne pouvez lire que les nombres. Vous avez rassemblé dans un fichier les règles de validité des différents champs d’un billet, votre billet, et ceux d’autres voyageurs aperçus à la gare.

Ce qu’il faut faire.

  • Le fichier a trois blocs séparés par une ligne vide. D’abord les règles nom: a-b or c-d : la valeur de ce champ doit être dans l’un des deux intervalles, bornes comprises. Puis votre billet (your ticket: suivi d’une ligne). Enfin les billets voisins (nearby tickets: suivi d’une ligne par billet).

  • Un billet est une suite d’entiers séparés par des virgules. Les champs sont dans le même ordre sur tous les billets, mais on ne sait pas quel champ est à quelle position.

  • Une valeur est non valide si elle ne respecte aucune règle : elle ne peut correspondre à aucun champ, quelle que soit sa position.

  • La réponse est la somme de toutes les valeurs non valides des billets voisins (votre propre billet est laissé de côté).

Exercice 1 — Comprendre ce qui est demandé #

Questions de vérification, à traiter sur le cahier :

  1. Pour la règle 2-6 or 9-12, les valeurs 6, 7 et 9 sont-elles acceptées ?

  2. Une valeur non valide égale à 0 change-t-elle la somme ? Son billet est-il valide pour autant ?

  3. Une valeur peut-elle respecter plusieurs règles à la fois ?

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

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

poids: 1-4 or 8-12
taille: 3-6 or 10-15
depart: 5-11 or 14-20

your ticket:
9,14,7

nearby tickets:
3,13,10
2,21,10
12,15,11
7,0,13
4,13,10
25,4,4
3,6,11

Repérer les valeurs non valides. Vérification : la réponse est 46. Que remarque-t-on sur le quatrième billet voisin ?

Programmer la partie 1#

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 3 — Lire le fichier #

Écrire une fonction lire(nom_fichier) qui renvoie trois objets : un dictionnaire regles (nom du champ \(\to\) liste de deux couples de bornes), votre billet et la liste des billets voisins (listes d’entiers).

Coup de pouce

open(...).read().strip().split("\n\n") sépare les trois blocs, car ils sont séparés par une ligne vide.

Rappel : « au moins un » et « tous » avec un booléen drapeau

La méthode est présentée dans l’encadré « Méthode : « tous » ou « au moins un », avec un booléen drapeau » du défi Handy Haversacks (chapitre 1) : pour « au moins un », le drapeau part de False et passe à True au premier exemple ; pour « tous », il part de True et passe à False au premier contre-exemple.

À essayer. Pour une liste vide, que vaut à la fin un drapeau « au moins un » ? un drapeau « tous » ? Pourquoi ces deux résultats sont-ils cohérents ?

Exercice 4 — Valeurs non valides #

Écrire une fonction respecte(valeur, bornes) puis une fonction valable_quelque_part(valeur, regles). En déduire le taux d’erreur. Tester sur l’exemple du défi, puis sur vos données.

Coup de pouce

a <= valeur <= b s’écrit tel quel en Python. Les deux fonctions sont des « au moins un » : un drapeau initialisé à False dans chacune.

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)

Il s’agit maintenant de déchiffrer votre billet : savoir à quel champ correspond chaque position.

  • Écarter d’abord les billets voisins qui contiennent au moins une valeur non valide.

  • Avec les billets restants, déterminer la position de chaque champ (une seule attribution est possible).

  • La réponse est le produit des valeurs de votre billet pour les champs dont le nom commence par departure.

Exercice 5 — Ne garder que les bons billets #

Construire la liste des billets voisins valides. Attention : un billet peut contenir une valeur non valide qui ne change pas la somme de la partie 1. Sur l’exemple du défi, il reste 4 billets valides.

Outil Python : les ensembles (set) — rappel

Tout est présenté dans l’encadré « Outil Python : les ensembles » du défi Crab Combat (chapitre 4) : set(), add, remove, test x in ensemble en temps constant, éléments non modifiables (tuples). Dans ce défi, ces opérations suffisent.

À essayer. Que contient {1, 2, 2, 3} ? Que se passe-t-il si l’on appelle remove pour retirer un élément absent ? Comment l’éviter avec un test in ?

Outil Python : tester le début d’une chaîne avec une tranche

s[:n] est la chaîne des n premiers caractères de s. Pour savoir si s commence par debut, on compare s[:len(debut)] à debut.

nom = "departure track"
debut = "departure"
print(nom[:len(debut)] == debut)     # True
print("arrival"[:6] == "depart")     # False

Intérêt. len(debut) évite de compter les lettres à la main. Une tranche plus longue que la chaîne ne provoque pas d’erreur : elle s’arrête à la fin de la chaîne.

À essayer. Que vaut "dep"[:9] ? En déduire la valeur de "dep"[:9] == "departure".

★★ Exercice 6 — Élimination par contraintes #

Pour chaque position, construire l’ensemble des champs compatibles avec toutes les valeurs des billets valides à cette position. Puis : tant qu’il reste des positions non attribuées, trouver une position qui n’a plus qu’un seul champ possible, l’attribuer, et retirer ce champ des autres ensembles. Sur l’exemple, la position 0 est compatible avec poids et taille, la position 1 avec taille seulement ; à la fin, depart est en position 2 et vaut 7 sur votre billet.

Coup de pouce

Un dictionnaire possibles associant à chaque position un set de noms de champs. Avant d’appeler remove, tester avec in que le champ est encore dans l’ensemble. Pour récupérer l’unique élément d’un ensemble, une boucle for suffit.

Coup de pouce 2 (début de solution)

La boucle principale est un while sur le nombre de positions déjà attribuées. À chaque tour, on cherche une position p telle que len(possibles[p]) == 1.

★★★ Exercice 7 — Défi : et si l’élimination bloquait ? #

Inventer un petit exemple où, à un moment, aucune position n’a un seul champ possible alors qu’une attribution existe. Comment faudrait-il alors chercher la solution ?

Coup de pouce

Penser au retour sur trace : on essaie un choix, et on revient en arrière s’il mène à une impasse.