Défis Advent of Code#

Les algorithmes de tri

Défi Historian Hysteria#

deux listes à réconcilier — trier, distances, compter

Jour 1

Fichiers à télécharger

dossier en ligne archive .zip

Consignes

L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2024/day/1 . On peut le lire en anglais ou le faire traduire par le navigateur (clic droit, Traduire en français).
Avec un compte (facultatif), le lien get your puzzle input donne vos données, à enregistrer sous input.txt à côté du 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 le tri d’un tableau vu dans ce chapitre.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :


list	liste	side by side	côte à côte
left / right	gauche / droite	to pair up	associer par paires
smallest	le plus petit	second-smallest	le deuxième plus petit
how far apart	à quelle distance (l’écart)	to add up	additionner
to reconcile	mettre en accord	location ID	identifiant de lieu

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

Contexte. Les historiens du pôle Nord cherchent leur chef, introuvable. Dans son bureau, ils ont dressé deux listes de lieux à visiter, chaque lieu étant désigné par un numéro. Mais les deux listes ne concordent pas, et il faut mesurer à quel point elles diffèrent. Le fichier présente les deux listes côte à côte.

Ce qu’il faut faire.

Chaque ligne contient deux entiers séparés par plusieurs espaces : le premier appartient à la liste de gauche, le second à la liste de droite.
On ne compare pas les nombres d’une même ligne : on trie chaque liste, puis on associe le plus petit nombre de gauche au plus petit de droite, le deuxième au deuxième, etc.
L’écart d’une paire est la distance entre ses deux nombres, c’est-à-dire la valeur absolue de leur différence.
La réponse est la somme des écarts de toutes les paires.

Exercice 1 — Vérifier sa compréhension #

Questions pièges, à traiter sur le cahier :

Si les deux listes contiennent exactement les mêmes nombres, dans un autre ordre, quelle est la réponse ?
L’écart entre 3 et 7 est-il le même que l’écart entre 7 et 3 ?
Pourquoi les deux listes ont-elles forcément la même longueur ?

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

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

Écrire les deux listes triées l’une sous l’autre, puis les écarts. Vérification : on doit obtenir 4.

Programmer la partie 1#

Exercice 3 — Lire les deux colonnes #

Outil Python : découper une ligne (split)

ligne.split() découpe la chaîne ligne sur les espaces et renvoie la liste des morceaux (des chaînes) ; les espaces multiples ne gênent pas. Avec un argument, ligne.split(", ") découpe sur ce séparateur.

morceaux = "5   2".split()
print(morceaux)              # ['5', '2'] : deux chaines
print(int(morceaux[0]))      # 5 : converti en entier
print("a, b, c".split(", ")) # ['a', 'b', 'c']

Écrire une fonction lire(nom_fichier) qui renvoie les deux listes gauche et droite. Sur l’exemple : [5, 2, 7, 1, 2, 6] et [2, 5, 4, 2, 8, 2].

Coup de pouce

Même schéma que d’habitude (open, boucle sur les lignes). "5 2".split() renvoie ["5", "2"] : les espaces multiples ne gênent pas.

Coup de pouce 2 (début de solution)

morceaux = ligne.split() puis gauche.append(int(morceaux[0])) et de même pour droite. Une fonction peut renvoyer deux valeurs : return gauche, droite, récupérées par g, d = lire("exemple.txt").

Outil Python : la valeur absolue (abs)

La fonction abs, déjà rencontrée au chapitre Le binaire et l’écriture des nombres, renvoie la valeur absolue d’un nombre : le nombre sans son signe. Pour deux nombres x et y, abs(x - y) est la distance entre eux, quel que soit le plus grand.

print(abs(-4))       # 4
print(abs(4))        # 4
print(abs(3 - 7))    # 4
print(abs(7 - 3))    # 4 : meme distance

Intérêt. Inutile d’écrire un if pour savoir quel nombre est le plus grand. Question : que vaut abs(0) ? abs(-2.5) ?

Exercice 4 — La distance totale #

Écrire une fonction distance_totale(gauche, droite) qui renvoie la réponse de la partie 1. Tester sur l’exemple, puis sur vos données.

Coup de pouce

Écrire d’abord une fonction trier(t) (tri par insertion ou par sélection du chapitre) et trier les deux listes, puis parcourir les indices : l’écart entre deux nombres x et y est abs(x - y).

Coup de pouce 2 (début de solution)

Pour ne pas modifier les listes lues, trier des copies : g_tri = [x for x in gauche], puis trier(g_tri). Ensuite, un accumulateur total et une boucle sur range(len(g_tri)).

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 historiens remarquent que beaucoup de numéros se retrouvent dans les deux listes : on mesure maintenant leur ressemblance autrement. Pour chaque nombre de la liste de gauche, on compte combien de fois il apparaît dans la liste de droite, et on multiplie le nombre par ce compte. La réponse est la somme de ces produits ; un nombre présent deux fois à gauche est compté deux fois.

Exercice 5 — Compter les apparitions #

Écrire une fonction nb_apparitions(x, liste) qui compte, avec une boucle, combien de fois x apparaît dans liste. Combien de comparaisons fait nb_apparitions(2, [2, 5, 4, 2, 8, 2]) ?
Utiliser cette fonction pour répondre à la partie 2. Sur l’exemple du défi, on doit trouver 17.

Coup de pouce

Relire précisément ce que l’énoncé multiplie : quel nombre, et par quoi ? Faut-il trier pour cette partie ?

Coup de pouce 2 (début de solution)

Pour chaque x de la liste de gauche, on ajoute au total x * nb_apparitions(x, droite).

Approfondissement#

★★★ Exercice 6 — Approfondissement 1 : compter une fois pour toutes #

Avec 1000 nombres par liste, combien de comparaisons fait la solution de la partie 2 qui utilise nb_apparitions ?
Sur l’exemple, écrire à la main le dictionnaire compte qui associe à chaque nombre de la liste de droite son nombre d’apparitions.
Écrire une fonction similarite_dico(gauche, droite) qui construit ce dictionnaire en un parcours de la liste de droite, puis répond en un seul parcours de la liste de gauche. Quel est son coût ?

Coup de pouce

Pour chaque y de la liste de droite : si y est déjà une clé, augmenter sa valeur de 1 ; sinon, créer la clé avec la valeur 1.

Coup de pouce 2 (début de solution)

Ensuite, pour chaque x de gauche : si x in compte, ajouter x * compte[x] au total ; sinon, rien à ajouter. Sans ce test, compte[x] provoquerait une erreur pour un nombre absent de la liste de droite.