Défis Advent of Code#

Processus et ordonnancement

Défi 1 Seating System#

la salle d’attente — automate cellulaire et copie de grilles

Jour 11

Fichiers à télécharger

Consignes

L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2020/day/11 . 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 mobilise la notion d’effet de bord vue au chapitre 2 : la fonction tour doit renvoyer une nouvelle grille sans modifier l’ancienne. Il fait aussi écho à ce chapitre : toutes les cases changent « en même temps », et lire un état pendant qu’on le modifie donne des résultats incohérents, comme deux processus qui accèdent sans précaution à une même ressource.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


seat layout	plan des sièges	floor	sol (pas un siège)
empty / occupied	libre / occupé	adjacent	voisin, adjacent
simultaneously	en même temps	round	tour (de règles)
become	devenir	stop changing	cesser de changer

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

Contexte. Vous attendez un ferry dans une salle encore vide et vous voulez prévoir où les voyageurs vont s’asseoir, pour choisir la meilleure place. Leur comportement est très prévisible : on le simule comme un automate cellulaire. Le fichier est le plan de la salle : chaque caractère est une case du sol ou un siège.

Ce qu’il faut faire.

. représente le sol, L un siège libre, # un siège occupé.
Les voisins d’une case sont les 8 cases qui l’entourent (même ligne, même colonne et diagonales), sans sortir du plan.
À chaque tour, toutes les cases changent en même temps, d’après l’état du tour précédent. Un siège libre dont aucun voisin n’est occupé devient occupé (on aime être tranquille). Un siège occupé qui a au moins 4 voisins occupés se libère (trop de monde). Dans les autres cas, rien ne change ; le sol ne change jamais.
On répète les tours jusqu’à ce que plus rien ne bouge. La réponse est le nombre de sièges occupés à ce moment-là.

Exercice 1 — Comprendre ce qui est demandé #

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

Combien de voisins a une case du bord qui n’est pas un coin ?
Un siège occupé qui a exactement 3 voisins occupés change-t-il d’état ? Et un siège libre qui en a 1 ?
Pourquoi ne peut-on pas modifier la grille au fur et à mesure qu’on la parcourt ?

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

On considère la grille (inventée) suivante :

L.LLL
LLLL.
L.L.L
LLLLL
..L.L

Dessiner la grille après un tour, puis après deux tours. Vérification : la grille ne change plus après le troisième tour, et l’on compte alors 11 sièges occupés.

Programmer la partie 1#

Exercice 3 — Lire la grille #

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.

Écrire une fonction lire_grille(nom_fichier) qui renvoie une liste de listes de caractères (une liste par ligne). Afficher le nombre de lignes et de colonnes.

Exercice 4 — Compter les voisins occupés #

Écrire une fonction voisins_occupes(grille, i, j) qui renvoie le nombre de sièges occupés autour de la case \((i, j)\). La tester sur une case du bord et sur une case du centre.

Coup de pouce

Deux boucles sur les décalages di et dj dans [-1, 0, 1], sans oublier d’exclure le cas (0, 0) et de vérifier qu’on ne sort pas de la grille.

Méthode : compter des éléments avec un compteur

On parcourt la liste et l’on ajoute 1 à un compteur chaque fois que l’élément convient. Pour une grille (liste de listes), on ajoute les comptes de chaque ligne.

def compter(ligne, x):
    """Renvoie le nombre d'elements de ligne egaux a x."""
    total = 0
    for c in ligne:
        if c == x:
            total += 1
    return total

print(compter(["#", ".", "L", "#"], "#"))   # 2
print(compter("#.L##", "#"))                 # 3 : fonctionne aussi sur une chaine
grille = [["#", "L"], ["#", "#"]]
total = 0
for ligne in grille:
    total += compter(ligne, "#")
print(total)                                 # 3 : somme des comptes de chaque ligne

Intérêt. Le schéma « compteur initialisé à 0, une boucle, un test » sert partout. Son coût est proportionnel à la longueur de ce qu’on parcourt : compter les sièges occupés d’une grille de \(L \times C\) cases coûte \(O(L \cdot C)\).

À essayer. Que renvoie compter([1, 2, 1], 3) ? Et compter([], "#") ?

Exercice 5 — Un tour, puis jusqu’à stabilité #

Écrire une fonction tour(grille) qui renvoie la nouvelle grille sans modifier l’ancienne, puis répéter les tours tant que la grille change. Tester sur l’exemple du défi, puis sur vos données.

Coup de pouce

Attention : toutes les cases changent en même temps. Si l’on modifie la grille pendant qu’on la parcourt, les cases suivantes voient un mélange d’ancien et de nouvel état. Sur l’exemple, la première ligne deviendrait #.#L# au lieu de #.### après un tour.

Coup de pouce 2 (début de solution)

copie = grille[:] ne suffit pas : les lignes restent partagées. Construire une nouvelle liste de listes, par exemple par compréhension : [ligne[:] for ligne in grille], ou remplir une grille neuve case par case. Deux listes de listes se comparent directement avec ==.

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)

En observant mieux, on comprend que les voyageurs ne regardent pas seulement les places juste à côté : ils regardent aussi plus loin.

Dans chacune des 8 directions, on compte le premier siège visible (libre ou occupé) en sautant les cases de sol ; s’il n’y a que du sol jusqu’au bord, la direction ne compte pas.
Un siège occupé se libère s’il voit au moins 5 sièges occupés. La règle pour s’asseoir et la réponse demandée ne changent pas.

★★ Exercice 6 — Ce que l’on voit #

Écrire une fonction visibles_occupes (mêmes paramètres que voisins_occupes), puis adapter tour pour qu’elle reçoive en paramètres la fonction de comptage et le seuil. Sur l’exemple du défi, on doit trouver 9.

Coup de pouce

Pour chacune des 8 directions (di, dj), on avance pas à pas tant qu’on est dans la grille et sur du sol ; on s’arrête au premier siège rencontré.

Coup de pouce 2 (début de solution)

Une fonction est une valeur comme une autre en Python : tour(grille, visibles_occupes, 5) est un appel tout à fait valide, et dans tour on appelle simplement le paramètre reçu.

Outil Python : mesurer une durée (module time)

La fonction time.perf_counter() renvoie un instant en secondes (avec beaucoup de décimales). La différence entre deux appels donne la durée écoulée entre les deux.

import time

debut = time.perf_counter()     # instant de depart (en secondes)
total = 0
for i in range(1000000):
    total += i
duree = time.perf_counter() - debut
print(f"{duree:.3f} s")         # duree ecoulee, arrondie a 3 decimales

Intérêt. Vérifier expérimentalement une complexité : si doubler la taille des données double le temps, le programme est linéaire ; s’il le multiplie par 4, il est quadratique. Les durées varient d’une machine à l’autre : seuls les rapports comptent.

À essayer. Recopier et exécuter ce code, puis remplacer 1000000 par 2000000. Comment évolue la durée ?

★★★ Exercice 7 — Défi : précalculer #

Les voisins visibles d’un siège ne dépendent pas de l’état des sièges, seulement de la position du sol. Les calculer une seule fois au début (dictionnaire case \(\to\) liste de cases) et mesurer le gain de temps avec le module time.

Coup de pouce

Le sol ne change jamais : la recherche dans les 8 directions peut être faite une fois pour toutes.

Défi 2 Crab Combat#

la bataille contre le crabe — files et récursivité

Jour 22

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/22 . 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 mobilise les files vues au chapitre 3 : chaque paquet de cartes est une file, comme celle des processus prêts dans l’ordonnancement en tourniquet de ce chapitre. La partie 2 réinvestit la récursivité du chapitre 1 : chaque sous-partie est un appel récursif, avec sa propre mémoire des situations déjà vues.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


deck	paquet de cartes	round	manche, tour
draw	tirer, piocher	top / bottom	dessus / dessous (du paquet)
higher-valued	de plus grande valeur	winner	gagnant
score	score	sub-game	sous-partie (partie 2)
recursive	récursif	infinite game	partie sans fin

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

Contexte. Sur le radeau, l’ennui guette ; heureusement, un petit crabe est monté à bord et accepte de jouer aux cartes avec vous, à un jeu proche de la bataille. Le fichier donne la main de départ de chaque joueur.

Ce qu’il faut faire.

Le fichier contient deux blocs (joueur 1, puis joueur 2) : une carte par ligne, la carte du dessus en premier. Toutes les valeurs sont différentes.
À chaque manche, chaque joueur retire sa carte du dessus ; la plus forte gagne. Le gagnant place les deux cartes sous son paquet : la sienne d’abord, puis celle de l’adversaire.
La partie s’arrête quand un joueur a toutes les cartes.
Score du gagnant : la carte du dessous est multipliée par \(1\), celle juste au-dessus par \(2\), etc., jusqu’à la carte du dessus multipliée par le nombre de cartes ; on additionne. Autrement dit, plus une carte est haut dans le paquet, plus elle compte. Réponse : ce score.

Exercice 1 — Vérifier sa compréhension #

Une manche peut-elle se terminer par une égalité ?
Le gagnant a 10 cartes, la carte du dessus vaut 4 : que rapporte-t-elle au score ?
Le nombre total de cartes change-t-il au cours de la partie ?

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

On considère les paquets (inventés) suivants, le dessus étant écrit en premier :

Joueur 1 : 6 2 8 1
Joueur 2 : 4 7 3 5

Jouer les trois premières manches à la main en écrivant les deux paquets après chaque manche. Combien de cartes chaque joueur a-t-il alors ? Vérification : la partie complète dure 18 manches et le score du gagnant vaut 198.

Programmer la partie 1#

Méthode : une file avec une liste Python

Un paquet de cartes est une file : on retire au début (le dessus), on ajoute à la fin (le dessous). Une simple liste Python suffit : pop(0) retire et renvoie le premier élément, append ajoute à la fin.

paquet = [6, 2, 8, 1]      # dessus du paquet a gauche
x = paquet.pop(0)          # retire et renvoie 6
paquet.append(4)           # ajoute a la fin : [2, 8, 1, 4]
paquet.append(7)
paquet.append(3)
print(len(paquet), paquet[0])   # 6 2 : longueur, premier element
print(paquet[:2])          # [2, 8] : nouvelle liste des deux premiers
if paquet:                 # une liste vide vaut False
    print("non vide")

Intérêt et limite. C’est la file du cours, sans rien à programmer. Mais pop(0) décale tous les autres éléments d’une case : \(O(n)\) opérations pour \(n\) éléments. Avec au plus 50 cartes, c’est négligeable ; pour de très longues files, on utiliserait la classe File du cours (deux piles) ou un indice de tête qui avance au lieu de décaler la liste, pour retirer en \(O(1)\). Question : que contient paquet à la fin du code ? Que se passe-t-il si l’on appelle pop(0) sur une liste vide ?

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 — Une file pour chaque joueur #

Lire le fichier et ranger les cartes de chaque joueur dans une file : on retire au début (dessus du paquet), on ajoute à la fin (dessous). Utiliser une liste Python (encadré ci-dessus), ou une classe File du cours.

Coup de pouce

Le fichier contient deux blocs séparés par une ligne vide : après strip, texte.split("\n\n") les sépare, puis split("\n") découpe chaque bloc en lignes (la première, Player 1:, ne contient pas de carte). Avec paquet = [6, 2, 8, 1], paquet.pop(0) renvoie 6 et paquet.append(x) ajoute à la fin.

Rappel : parcourir avec l’indice

Pour connaître à la fois la position et la valeur de chaque élément, on parcourt les indices avec range(len(...)).

paquet = [8, 6, 7]
for i in range(len(paquet)):
    print(i, paquet[i])    # 0 8, puis 1 6, puis 2 7

Intérêt. L’indice i dit où se trouve la carte dans le paquet : c’est lui qui fixe son coefficient dans le score. Question : écrire une boucle qui affiche paquet[i] * (3 - i) pour la liste [8, 6, 7], puis qui calcule la somme de ces trois produits dans une variable total.

Exercice 4 — Jouer et compter #

Écrire une fonction combat(p1, p2) qui joue la partie et renvoie le paquet du gagnant, puis une fonction score(paquet). Tester sur l’exemple, puis sur vos données.

Coup de pouce

La boucle tourne while p1 and p2 : une file vide vaut False. Pour le score, la carte du dessous est multipliée par 1 : en parcourant le paquet par indice (for i in range(len(paquet))), la carte d’indice i est multipliée par len(paquet) - i ; on accumule les produits dans une variable total.

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)

Le crabe a perdu et propose une revanche à une version « récursive » du jeu.

Avant chaque manche : si la même configuration des deux paquets est déjà apparue dans cette partie, le joueur 1 gagne aussitôt la partie.
Sinon, chacun tire sa carte. Si chaque joueur a encore au moins autant de cartes que la valeur qu’il vient de tirer, le gagnant de la manche est celui d’une sous-partie jouée avec des copies de ses \(n\) cartes suivantes (\(n\) = valeur tirée). Sinon, la plus forte carte gagne. Le gagnant range les cartes comme avant.
Réponse : le score du gagnant de la partie principale.

Outil Python : les ensembles (set)

Un ensemble est une collection sans doublon et sans ordre : pas d’indice ; on peut seulement ajouter, retirer, tester l’appartenance et parcourir (dans un ordre quelconque). Ses éléments doivent être non modifiables : nombres, chaînes, tuples — pas de liste.

vus = set()              # ensemble vide (attention : {} est un dictionnaire vide)
vus.add(5)               # ajout ; ajouter une valeur deja presente ne change rien
vus.add(8)
print(8 in vus)          # True : test d'appartenance
print(len(vus))          # 2
vus.remove(8)            # retrait (erreur si absent : tester avant avec in)
a = {1, 2, 3}            # ensemble ecrit directement
b = set([2, 3, 4, 4])    # a partir d'une liste : {2, 3, 4}
print(len(b))            # 3 : le doublon a disparu
for x in a:              # parcours, dans un ordre quelconque
    print(x)
pairs = {n for n in range(10) if n % 2 == 0}   # ensemble en comprehension

Deux opérateurs construisent un nouvel ensemble à partir de deux autres, sans les modifier : la réunion a | b (éléments présents dans a ou dans b) et l’intersection a & b (éléments présents dans les deux).

a = {1, 2, 3}
b = {2, 3, 4}
print(a | b)             # {1, 2, 3, 4} : reunion, sans doublon
print(a & b)             # {2, 3} : intersection
a = a | {7}              # pour agrandir a, on le remplace par la reunion

Dans ce défi, pour mémoriser l’état des deux paquets, on le convertit en un couple de tuples :

p1, p2 = [6, 2], [4, 7]
deja_vus = set()
etat = (tuple(p1), tuple(p2))             # ((6, 2), (4, 7))
print(etat in deja_vus)                   # False
deja_vus.add(etat)
print(((6, 2), (4, 7)) in deja_vus)       # True

Intérêt. Avec une liste, x in liste compare x à chaque élément l’un après l’autre : jusqu’à \(n\) comparaisons. Un ensemble range ses éléments selon une valeur calculée à partir d’eux (une fonction de hachage, le même principe que les clés d’un dictionnaire) : Python va directement là où x devrait se trouver. Le test x in ensemble prend donc un temps qui ne dépend pas du nombre d’éléments (temps constant, en moyenne). C’est aussi ce qui rend a & b rapide : Python parcourt un des deux ensembles et teste chaque élément dans l’autre en temps constant, au lieu de comparer chaque élément de a à chaque élément de b. Cet encadré servira dans plusieurs défis des chapitres suivants.

À essayer. Que se passe-t-il si l’on essaie deja_vus.add(p1) ? Que renvoie set("banane") ? Que valent set("chat") & set("chien") et set("chat") | set("chien") ? Et a & set() ?

★★ Exercice 5 — Le combat récursif #

Écrire une fonction récursive combat_recursif(p1, p2) qui renvoie le numéro du gagnant et son paquet. Sur l’exemple du défi, le joueur 1 gagne avec un score de 151. Bien relire la règle qui empêche une partie de durer indéfiniment : elle s’applique à chaque partie et sous-partie séparément.

Coup de pouce

La mémoire des situations déjà vues est un ensemble créé au début de chaque appel de la fonction (donc propre à chaque sous-partie). Une liste n’est pas utilisable comme élément d’un ensemble : y ranger le couple (tuple(p1), tuple(p2)).

Coup de pouce 2 (début de solution)

Pour une sous-partie, on construit de nouveaux paquets (copies) : la tranche p1[:n] est une nouvelle liste qui contient les n cartes du dessus, sans modifier p1. La fonction renvoie un couple (gagnant, paquet) ; dans la sous-partie, seul le gagnant compte pour décider de la manche en cours.

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

Compter le nombre total d’appels de combat_recursif et la profondeur maximale de récursion atteinte sur vos données. Pourquoi la profondeur reste-t-elle faible ?

Coup de pouce

À chaque appel récursif, le nombre total de cartes en jeu diminue strictement.