Défis Advent of Code#

Graphes

Défi 1 Jurassic Jigsaw#

le puzzle d’images — grilles, rotations et symétries

Jour 20

Fichiers à télécharger

Consignes

L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2020/day/20 . 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 réinvestit les graphes de ce chapitre : les tuiles en sont les sommets, et deux tuiles qui partagent un bord sont reliées par une arête. L’approfondissement assemble l’image par un parcours de ce graphe.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


tile	tuile, morceau d’image	reassemble	réassembler
rotated / flipped	tourné / retourné (en miroir)	border / edge	bord
line up	coïncider, s’aligner	outermost	le plus à l’extérieur
corner	coin	ID number	numéro d’identification
sea monster	monstre marin (motif à chercher)	roughness	rugosité (partie 2)

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

Contexte. Les messages du satellite contiennent en fait une photo, mais l’appareil l’a envoyée découpée en petits carrés (des « tuiles »), mélangés et, pire, tournés ou retournés au hasard. Il faut reconstituer ce puzzle. Chaque bloc du fichier est une tuile en noir et blanc, avec son numéro.

Ce qu’il faut faire.

Un bloc est une ligne Tile <numéro>: suivie d’une grille carrée de \(10 \times 10\) caractères . ou # ; les blocs sont séparés par une ligne vide.
Remises dans le bon sens, les tuiles forment une image carrée. Chaque tuile a pu être tournée d’un nombre quelconque de quarts de tour et/ou retournée en miroir.
Deux tuiles voisines dans l’image ont, une fois bien orientées, des bords identiques : c’est ce qui permet de les raccorder. Les bords extérieurs de l’image ne correspondent à aucune autre tuile (en pratique, deux tuiles non voisines n’ont jamais de bord commun).
Réponse : le produit des numéros des quatre tuiles placées aux coins de l’image.

Exercice 1 — Vérifier sa compréhension #

Deux bords qui se correspondent peuvent apparaître « à l’envers » l’un par rapport à l’autre : pourquoi ?
Combien de bords sans correspondant a une tuile de coin ? une tuile du bord de l’image ? une tuile intérieure ?
Faut-il reconstituer toute l’image pour la partie 1 ?

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

Voici deux tuiles inventées de taille \(5\times 5\) :

Tuile A
#.#..
#.#..
#...#
.#.##
#....

Tuile B
.#...
##.##
###.#
....#
.#.##

Écrire les quatre bords de chaque tuile sous forme de chaînes, en lisant toujours de gauche à droite (haut, bas) ou de haut en bas (gauche, droite).
Montrer qu’un seul bord de A coïncide avec un bord de B, à condition de lire l’un des deux à l’envers. Vérification : il s’agit du bord droit de A et du bord gauche de B.
Pour placer B à droite de A, B doit-il être tourné, retourné, ou laissé tel quel ?

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 les tuiles #

Construire un dictionnaire tuiles qui associe à chaque numéro (un entier) la tuile sous forme de liste de chaînes. Vérifier le nombre de tuiles : est-ce un carré parfait ?

Coup de pouce

Les tuiles sont séparées par une ligne vide : split("\n\n"). La première ligne d’un bloc donne le numéro : une tranche enlève le texte Tile et le : final.

Outils Python : lire une chaîne à l’envers, construire une colonne, comparer deux chaînes

s[::-1] est la tranche qui parcourt s avec un pas de \(-1\) : c’est la chaîne à l’envers. Pour obtenir une colonne d’une tuile, on part d’une chaîne vide et on lui ajoute, ligne après ligne, le caractère voulu. Enfin min(a, b) et < comparent deux chaînes dans l’ordre « alphabétique » des caractères (l’ordre de leurs codes : # vient avant .).

tuile = ["#.#", "..#", "##."]
print(tuile[0][::-1])               # "#.#" lu a l'envers : "#.#"
print("..#"[::-1])                  # "#.."
gauche = ""
for ligne in tuile:
    gauche += ligne[0]              # premier caractere de chaque ligne
print(gauche)                       # "#.#"
print(min("..#", "#.."))            # "#.." car "#" < "."

Intérêt. Avec min(b, b[::-1]), un bord et son inverse donnent la même chaîne : on peut alors les ranger sous une seule clé de dictionnaire. Question : écrire le bord droit de cette tuile avec une boucle. Que vaut min("##.", ".##") ?

Exercice 4 — Les bords #

Écrire une fonction bords(tuile) qui renvoie la liste des quatre bords. Puis compter, pour chaque bord de chaque tuile, combien d’autres tuiles possèdent ce bord, à l’endroit ou à l’envers.

Coup de pouce

Une boucle qui ajoute ligne[0] à une chaîne, vide au départ, donne le bord gauche ; chaine[::-1] lit une chaîne à l’envers.

Exercice 5 — Les coins #

Une tuile de coin a exactement deux bords qui ne correspondent à aucune autre tuile. Repérer les quatre coins et calculer la réponse.

Coup de pouce

Construire un dictionnaire qui associe à chaque bord, mis sous une forme canonique (le plus petit, dans l’ordre alphabétique, entre le bord et son inverse : min(b, b[::-1])), la liste des tuiles qui le possèdent. Un bord de tuile est « libre » si cette liste n’a qu’un élément.

Partie 2#

Une fois la partie 1 validée, lire la suite de l’énoncé sur le site. Cette partie est longue : la découper en étapes et tester chacune.

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

Une fois l’image reconstituée, on y cherche des monstres marins.

Assembler l’image, retirer le bord (première et dernière lignes et colonnes) de chaque tuile, puis recoller les tuiles : chacune devient un carré \(8 \times 8\).
Chercher un motif (le « monstre », dessiné sur le site) dans l’une des 8 orientations de l’image : chaque # du motif doit tomber sur un # de l’image, les autres cases sont quelconques.
Réponse : le nombre de # de l’image qui n’appartiennent à aucun monstre.

★★ Exercice 6 — Assembler l’image #

Écrire rotation(tuile) (quart de tour) et symetrie(tuile) (miroir), puis orientations(tuile) qui renvoie les huit positions possibles (lire l’encadré). Assembler ensuite toute l’image en suivant la stratégie de l’encadré.

Coup de pouce

Tester rotation sur la tuile A : quatre rotations successives doivent redonner A, et orientations(A) doit contenir 8 tuiles toutes différentes.

Coup de pouce 2 (début de solution)

Pour une liste de chaînes t de taille \(n\), la ligne j de la tuile tournée d’un quart de tour dans le sens horaire est formée des caractères t[n - 1 - i][j] pour i de 0 à n - 1, ajoutés un par un à une chaîne vide au départ.

Outil Python : les ensembles (set), et rappel sur le drapeau

Pour tester si toutes les cases d’une liste sont des #, on utilise un booléen « drapeau » (méthode du défi Handy Haversacks, chapitre 1) : il part de True et la boucle le passe à False au premier contre-exemple. Un ensemble est une collection sans doublon et sans ordre ; on y ajoute avec add, on réunit deux ensembles avec a | b, et le test x in ensemble est très rapide (encadré « les ensembles » du défi Crab Combat, chapitre 4).

image = ["#.#", "###"]
cases = [(0, 0), (1, 1)]
tout_diese = True
for i, j in cases:
    if image[i][j] != "#":
        tout_diese = False
print(tout_diese)                    # True
couvertes = set()                    # ensemble vide (attention : {} est un dict)
couvertes.add((0, 0))
couvertes = couvertes | {(0, 0), (1, 1)}   # reunion : (0, 0) n'est pas compte deux fois
print(len(couvertes))                # 2
print((1, 1) in couvertes)           # True

Intérêt. Si deux monstres se chevauchaient, une case commune ne serait comptée qu’une fois dans l’ensemble. Question : que vaudrait tout_diese avec la liste de cases [(0, 0), (0, 1)] ?

★★ Exercice 7 — Chercher le motif #

Retirer les bords de chaque tuile, recoller l’image, puis chercher le motif dans chacune de ses huit orientations. Calculer la réponse demandée.

Coup de pouce

Stocker le motif comme une liste de décalages (ligne, colonne) des cases # ; le motif est présent à la position (i, j) si (avec un drapeau) toutes les cases (i + dl, j + dc) de l’image sont des #. Une seule orientation de l’image contient des motifs.

Pour y arriver : orientations et assemblage#

Les huit orientations d’une grille carrée

Un carré peut être tourné de \(0\), \(1\), \(2\) ou \(3\) quarts de tour : cela fait 4 positions. On peut aussi le retourner (miroir gauche-droite) avant de le tourner : 4 positions de plus. Toute autre transformation (miroir haut-bas, miroir selon une diagonale) redonne l’une de ces 8 positions : par exemple, le miroir haut-bas est un miroir gauche-droite suivi d’un demi-tour. Il suffit donc de deux fonctions, rotation et symetrie, pour toutes les obtenir.

Stratégie d’assemblage pas à pas

Prendre un coin trouvé en partie 1 et chercher l’orientation où ses deux bords libres sont en haut et à gauche : il sera la case \((0, 0)\).
Remplir la première ligne de gauche à droite : pour la case suivante, chercher parmi les tuiles non placées celle qui, dans l’une de ses 8 orientations, a un bord gauche égal au bord droit de la tuile précédente.
Pour les lignes suivantes, chaque tuile doit avoir son bord haut égal au bord bas de la tuile du dessus.
Grâce à la partie 1, on sait que chaque bord intérieur n’est partagé que par deux tuiles : à chaque étape, il y a donc une seule tuile possible.

Approfondissement#

★★ Exercice 8 — Approfondissement 1 : assembler par un parcours #

La stratégie du défi part d’un coin et remplit l’image ligne par ligne. On peut aussi partir de n’importe quelle tuile, laissée telle quelle à la position \((0, 0)\), et propager : pour chaque tuile placée, on cherche ses voisines par ses quatre bords, on les oriente et on les place à côté. Les positions peuvent devenir négatives ; on « recadre » à la fin.

À la main, avec les tuiles A et B du défi : A est placée telle quelle en \((0, 0)\). À quelle position va B, et dans quelle orientation ? Quelle serait la position de B si l’on avait placé B en premier ?
Écrire assembler_parcours(tuiles) qui utilise une pile des tuiles placées mais pas encore traitées, et un dictionnaire place qui associe à chaque position (ligne, colonne) la tuile orientée. Vérifier qu’on obtient la même réponse à la partie 2.

Coup de pouce

Pour le côté droit d’une tuile t placée en (l, c) : la voisine (si elle existe et n’est pas encore placée) va en (l, c + 1), dans l’orientation dont le bord gauche est égal au bord droit de t. Idem pour les trois autres côtés.

Coup de pouce 2 (début de solution)

Une liste COTES de quadruplets (dl, dc, mon_bord, son_bord), par exemple (0, 1, droite, gauche), évite d’écrire quatre fois le même code (les fonctions sont des valeurs comme les autres). Recadrage : soustraire à toutes les positions le plus petit numéro de ligne et le plus petit numéro de colonne, trouvés par une boucle sur les clés de place.
Cette méthode suppose qu’aucun bord n’est un palindrome (une chaîne égale à son inverse). Pourquoi ? La méthode du défi a-t-elle le même défaut ?
Comparer les deux méthodes : nombre de tuiles examinées, longueur du code. Quel parcours de graphe reconnaît-on ?

Défi 2 Allergen Assessment#

les allergènes — ensembles, intersections et élimination

Jour 21

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/21 . 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 peut se lire avec les graphes de ce chapitre : relier chaque allergène aux ingrédients qui peuvent le contenir donne un graphe, et l’élimination retire des arêtes jusqu’à ce qu’il n’en reste qu’une par allergène.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


ingredient	ingrédient	allergen	allergène
food	aliment	contains	contient
listed / marked	indiqué, mentionné	safe	sans danger
exactly one	exactement un	zero or one	zéro ou un
dangerous	dangereux	alphabetically	par ordre alphabétique

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

Contexte. Pour rejoindre votre île, vous construisez un radeau et devez emporter des provisions. Problème : les étiquettes des aliments sont écrites dans une langue inconnue, seuls certains allergènes sont indiqués dans une langue que vous comprenez. Chaque ligne du fichier décrit un aliment : sa liste d’ingrédients (illisibles) et quelques-uns des allergènes qu’il contient.

Ce qu’il faut faire.

Une ligne contient des ingrédients séparés par des espaces, puis (contains suivi d’allergènes séparés par des virgules, et ).
Chaque allergène se trouve dans exactement un ingrédient ; un ingrédient contient zéro ou un allergène.
Si un allergène est indiqué sur une ligne, l’ingrédient qui le contient figure sur cette ligne. Mais un allergène peut être présent dans un aliment sans y être indiqué : l’absence de mention ne prouve rien.
Trouver les ingrédients qui ne peuvent contenir aucun allergène. Réponse : le nombre total de leurs apparitions (un ingrédient présent sur trois lignes compte trois fois).

Exercice 1 — Vérifier sa compréhension #

Un allergène est indiqué sur deux lignes : où peut se trouver l’ingrédient qui le contient ?
Un ingrédient absent d’une ligne qui indique milk peut-il contenir milk ?
Un ingrédient présent sur une ligne qui n’indique pas milk peut-il contenir milk ?

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

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

brak zuli monto pirf (contains gluten, milk)
zuli kesa tolu (contains gluten)
monto tolu brak vemi (contains eggs)
tolu pirf zuli (contains gluten, eggs)
kesa zuli brak (contains milk)

Pour l’allergène gluten, quels ingrédients figurent sur toutes les lignes qui le mentionnent ? Faire de même pour eggs et milk.
En déduire les ingrédients qui ne peuvent contenir aucun allergène, et la réponse de la partie 1. Vérification : on doit trouver 7.
L’ingrédient monto figure sur une ligne qui mentionne milk. Pourquoi est-il pourtant sans danger ?

Programmer la partie 1#

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, parcours avec for, éléments non modifiables (tuples), réunion a | b (éléments présents dans l’un ou dans l’autre) et intersection a & b (éléments présents dans les deux). Ces deux opérateurs renvoient un nouvel ensemble, sans modifier a ni b.

À essayer. Avec a = set("brak zuli monto".split()) et b = {"zuli", "kesa", "brak"}, que valent a & b, b & a et a | b ? Écrire une boucle qui construit l’ensemble des éléments de b absents de a. Que vaut len(a & set()) ?

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 #

Construire la liste aliments : chaque aliment est un couple (ingredients, allergenes) de deux ensembles de chaînes.

Coup de pouce

Après strip, ligne.split(" (contains ") sépare les deux parties ; il reste à enlever la parenthèse finale (le dernier caractère) avec la tranche [:-1] puis à couper selon ", ".

Exercice 4 — Les candidats #

Écrire une fonction candidats(aliments) qui renvoie un dictionnaire associant à chaque allergène l’ensemble des ingrédients qui peuvent le contenir. Tester sur l’exemple.

Coup de pouce

L’ingrédient qui contient un allergène est présent sur chaque ligne où cet allergène est indiqué : il est donc dans l’intersection (opérateur &) des ensembles d’ingrédients de ces lignes.

Exercice 5 — Compter #

Calculer l’ensemble des ingrédients « suspects » (réunion des candidats), puis compter les apparitions des autres ingrédients dans le fichier.

Coup de pouce

Réunion de plusieurs ensembles : partir de set() et le remplacer, pour chaque ensemble de candidats e, par suspects | e. Pour compter, parcourir les ingrédients de chaque ligne et ajouter 1 à un compteur pour chacun qui n’est pas dans suspects ; attention, on compte chaque apparition sur chaque ligne.

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 reste à identifier les ingrédients dangereux pour pouvoir les éviter. Déterminer, pour chaque allergène, l’ingrédient qui le contient (la solution est unique). Réponse : la liste de ces ingrédients, rangés dans l’ordre alphabétique de leur allergène (et non de leur nom), séparés par des virgules sans espace.

Méthode : trier puis assembler des chaînes

Trier. Les chaînes se comparent avec < dans l’ordre alphabétique ("eggs" < "gluten" vaut True) : le tri par insertion du cours de première les range donc dans l’ordre alphabétique, sans rien changer à son code.

Assembler. Pour coller des chaînes en intercalant un séparateur, on part du premier mot et l’on ajoute, pour chacun des suivants, le séparateur puis le mot : il n’y a pas de virgule en trop à la fin.

mots = ["tolu", "zuli", "brak"]
texte = mots[0]
for i in range(1, len(mots)):
    texte = texte + "," + mots[i]
print(texte)                    # tolu,zuli,brak

Question : que se passe-t-il si la liste mots est vide ? Que faut-il changer pour obtenir tolu - zuli - brak ?

Exercice 6 — Attribuer chaque allergène #

Déterminer quel ingrédient contient chaque allergène, puis construire la chaîne demandée. Sur l’exemple du défi, on doit obtenir tolu,zuli,brak.

Coup de pouce

C’est le même raisonnement qu’un sudoku : un allergène qui n’a plus qu’un seul candidat est résolu, et cet ingrédient peut être retiré des candidats de tous les autres allergènes.

Coup de pouce 2 (début de solution)

Tant que le dictionnaire des candidats n’est pas vide : chercher un allergène dont l’ensemble a une seule valeur, le retirer du dictionnaire (del) en notant l’ingrédient dans un dictionnaire attribution, puis retirer cet ingrédient (remove, après avoir testé in) de tous les autres ensembles. Pour la réponse, trier les allergènes (tri par insertion), puis assembler les ingrédients correspondants.

★★★ Exercice 7 — Défi : et si ça bloquait ? #

Inventer un petit fichier pour lequel la méthode d’élimination ne suffit pas : à un moment, aucun allergène n’a un seul candidat. Que faudrait-il faire alors ?

Coup de pouce

Essayer avec deux allergènes indiqués toujours ensemble, sur les mêmes lignes : le problème a-t-il encore une seule solution ? Dans les cas où la solution est unique mais où l’élimination bloque, on peut tester les possibilités une à une (retour sur trace).

Un peu d’histoire : Philip Hall et le « problème des mariages » (1935)

Le graphe du défi. Dessinons les allergènes d’un côté, les ingrédients de l’autre, et relions chaque allergène à ses candidats. Toutes les arêtes vont d’un groupe à l’autre : c’est un graphe biparti. Choisir un ingrédient par allergène, deux allergènes n’ayant jamais le même ingrédient, revient à garder des arêtes sans sommet commun : on appelle cela un couplage. Sur le petit exemple de la fiche :

Le théorème. En 1935, le mathématicien anglais Philip Hall (1904–1982), spécialiste d’algèbre à Cambridge, publie un article de cinq pages, On Representatives of Subsets. Il y répond à une question simple : à quelle condition peut-on choisir, dans chaque ensemble d’une liste, un élément différent pour chacun ? Réponse : il faut et il suffit que tout groupe de \(k\) ensembles contienne, à eux tous, au moins \(k\) éléments différents. La condition est évidemment nécessaire (trois allergènes qui n’ont que deux candidats à eux trois ne peuvent pas être servis) ; le tour de force de Hall est de prouver qu’elle suffit. En 1950, Paul Halmos et Herbert Vaughan le reformulent avec des jeunes filles qui veulent chacune épouser un garçon qu’elle connaît : depuis, on l’appelle le théorème des mariages.

Et aujourd’hui. En 1962, David Gale et Lloyd Shapley étudient la version où chacun classe ses partenaires par préférence (« mariages stables ») ; leur algorithme sert à répartir des étudiants entre des formations (la procédure Parcoursup s’en inspire) et a valu à Shapley le prix Nobel d’économie 2012, partagé avec Alvin Roth.

Sources : P. Hall, « On Representatives of Subsets », J. London Math. Soc., 10 (1935), p. 26–30 ; P. Halmos et H. Vaughan, « The Marriage Problem », Amer. J. Math., 72 (1950) ; D. Gale et L. Shapley, « College Admissions and the Stability of Marriage », Amer. Math. Monthly, 69 (1962).