Aller au contenu

Défis Advent of Code#

Les algorithmes gloutons

Défi Lobby#

les batteries de l’escalator — un algorithme glouton

Jour 3

Fichiers à télécharger

dossier en ligne archive .zip

Consignes

  • L’énoncé se lit sur le site (voir le QR code) : https://adventofcode.com/2025/day/3 . 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 est une application directe de ce chapitre : un algorithme glouton, dont il faudra justifier qu’il donne bien la meilleure solution.

Lire l’énoncé#

Vocabulaire utile pour lire le texte original :
battery pile, batterie bank rangée, groupe
joltage rating tension indiquée (1 à 9) turn on allumer, activer
exactly two exactement deux rearrange réordonner
largest possible le plus grand possible total output total produit

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

Contexte. Dans le hall d’un immeuble, les ascenseurs sont en panne, et même l’escalier mécanique est à l’arrêt faute de courant. Des batteries de secours peuvent l’alimenter. Elles sont rangées en groupes, et chaque batterie porte une tension de 1 à 9. Chaque ligne du fichier décrit un groupe : la suite des tensions de ses batteries, dans l’ordre où elles sont rangées.

Ce qu’il faut faire.

  • Dans chaque groupe, on allume exactement deux batteries. Le groupe produit le nombre à deux chiffres formé par leurs tensions, dans l’ordre de la ligne : on ne peut pas réordonner les batteries.

  • On veut, pour chaque groupe, le plus grand nombre possible.

  • Réponse : la somme de ces maxima sur toutes les lignes.

Exercice 1 — Comprendre ce qui est demandé #

Après lecture du résumé (et de l’énoncé), vérifier sa compréhension sur ces cas particuliers :

  1. Dans la ligne 19, peut-on obtenir 91 ?

  2. Si le plus grand chiffre de la ligne est le dernier caractère, peut-il servir de chiffre des dizaines ?

  3. Dans 9399, quels chiffres faut-il choisir ?

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

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

372819465123987
111119111181111
564738291564738
999888777666555

Pour chaque ligne, trouver le plus grand nombre de deux chiffres possible. Vérification : on doit obtenir 394. Pour la troisième ligne, pourquoi ne peut-on pas obtenir 99 ?

Programmer la partie 1#

Exercice 3 — Lire et tester toutes les paires #

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.

Rappel pour lire un fichier ligne par ligne :

fichier = open("input.txt", encoding="utf-8")
for ligne in fichier:
    ligne = ligne.strip()   # enlève le retour à la ligne final
fichier.close()

Écrire une fonction meilleur_par_paires(ligne) qui essaie tous les couples d’indices i < j et renvoie le plus grand nombre int(ligne[i] + ligne[j]). Calculer la réponse (394 sur l’exemple).

Coup de pouce

Deux boucles imbriquées, la seconde commençant à i + 1, et un calcul de maximum.

Méthode : position du plus grand caractère

Les chiffres se comparent très bien sous forme de caractères : "9" > "8" vaut True. Pour trouver l’indice de la première apparition du plus grand caractère de ligne entre les indices debut (inclus) et fin (exclu), on parcourt cette zone en mémorisant la position du meilleur caractère vu jusque-là.

def position_max(ligne, debut, fin):
    """Indice de la premiere apparition du plus grand caractere
    parmi ligne[debut], ..., ligne[fin - 1]."""
    p = debut
    for i in range(debut + 1, fin):
        if ligne[i] > ligne[p]:      # strict : en cas d'egalite, on garde la premiere
            p = i
    return p

ligne = "38193"
print(position_max(ligne, 0, 5))   # 3 : le 9 est a l'indice 3
print(position_max(ligne, 0, 3))   # 1 : le 8, parmi "381"

Intérêt. Une seule boucle donne à la fois le plus grand chiffre (ligne[p]) et sa position p ; les bornes debut et fin permettent de chercher dans une partie de la ligne seulement, sans la recopier.

À essayer. Que renvoient position_max("9919", 0, 4) et position_max("9919", 1, 3) ? Que renverrait le premier appel si l’on écrivait >= au lieu de > ?

Exercice 4 — Une idée gloutonne #

Écrire une seconde fonction meilleur_glouton(ligne) qui ne fait que deux parcours : choisir d’abord le meilleur chiffre des dizaines, puis le meilleur chiffre des unités après lui. Vérifier qu’elle donne les mêmes résultats que la précédente.

Coup de pouce

Le chiffre des dizaines compte dix fois plus que celui des unités : il faut le prendre le plus grand possible. Mais il ne peut pas être le dernier caractère de la ligne (il faut laisser une place pour les unités).

Coup de pouce 2 (début de solution)

Avec la fonction position_max de l’encadré : p = position_max(ligne, 0, len(ligne) - 1) donne le chiffre des dizaines (le dernier caractère est exclu), puis q = position_max(ligne, p + 1, len(ligne)) celui des unités. Le résultat est int(ligne[p] + ligne[q]).

Lien avec le cours : algorithmes gloutons

Un algorithme glouton construit une solution en faisant, à chaque étape, le choix qui semble le meilleur sur le moment, sans jamais revenir en arrière (comme le rendu de monnaie du cours). Il est rapide, mais il ne donne pas toujours la meilleure solution : il faut le justifier. Ici, pourquoi est-il correct ? Deux nombres de même longueur se comparent d’abord par leur premier chiffre ; le premier chiffre choisi doit donc être le plus grand parmi ceux qui laissent assez de chiffres après eux. Si ce maximum apparaît plusieurs fois, prendre sa première apparition laisse le plus de choix pour la suite. Après ce choix, il reste le même problème, plus petit, sur la fin de la 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)

Deux batteries par groupe ne suffisent pas à faire repartir l’escalier. On allume maintenant exactement 12 batteries dans chaque groupe, toujours sans changer leur ordre, pour former le plus grand nombre de 12 chiffres possible. Réponse : la somme de ces maxima sur toutes les lignes.

Exercice 5 — Combien de possibilités ? #

Dans la partie 2, on ne choisit plus deux chiffres. Regarder la longueur des lignes de vos données. Pour une ligne de 100 chiffres, essayer toutes les possibilités est-il raisonnable ? (Pour 12 chiffres choisis parmi 100, il y a plus de \(10^{15}\) possibilités.)

Exercice 6 — Le glouton généralisé #

Écrire une fonction meilleur(ligne, k) qui choisit k chiffres, de gauche à droite, avec le même principe glouton. La partie 1 correspond à k = 2. Sur l’exemple du défi, avec k = 12, la première ligne donne 819465123987 et le total vaut 2676756647502.

Coup de pouce

Quand il reste r chiffres à choisir, le prochain chiffre doit laisser au moins r - 1 chiffres après lui : on le cherche donc entre l’indice debut (juste après le chiffre choisi précédemment) et l’indice len(ligne) - r inclus.

Coup de pouce 2 (début de solution)

Une boucle for r in range(k, 0, -1): ; la recherche se fait avec p = position_max(ligne, debut, len(ligne) - r + 1) ; on ajoute ligne[p] à une chaîne resultat, puis on avance debut juste après : debut = p + 1.

Approfondissement#

Outil Python : le hasard (random)

Le module random tire des nombres au hasard ; random.randint(a, b) renvoie un entier entre a et b inclus.

import random

print(random.randint(1, 9))            # un entier au hasard entre 1 et 9 (inclus)

Intérêt. Pour tester un algorithme rapide, on le compare à une recherche exhaustive lente mais sûre, sur beaucoup de petits cas tirés au hasard.

À essayer. Écrire une boucle qui construit une chaîne de 15 chiffres, chacun tiré au hasard entre 1 et 9.

★★★ Exercice 7 — Approfondissement 1 : convaincre et tester #

  1. Écrire une fonction exhaustif(ligne, k) qui essaie tous les choix de k chiffres pris dans l’ordre de la ligne et renvoie le plus grand nombre obtenu.

    Coup de pouce

    Construire la liste de tous les débuts de choix : partir de [""] puis, pour chaque caractère c de la ligne, remplacer chaque début s par deux débuts, s (on ne prend pas c) et s + c (on le prend, si s a moins de k caractères). À la fin, garder le plus grand des choix de longueur k.

  2. Comparer meilleur(ligne, k) et exhaustif(ligne, k) sur 300 lignes de 15 chiffres tirées au hasard, avec k lui aussi au hasard. Combien de désaccords ?

  3. Rédiger en quelques lignes la justification du glouton pour k quelconque.

  4. Que se passerait-il si l’on prenait la dernière apparition du maximum ? Tester la ligne "9919" avec k = 3.

    Coup de pouce

    Prendre une apparition plus tardive laisse moins de chiffres après elle.