• [^] # Re: Jour 3

    Posté par . En réponse au journal Advent of Code 2025. Évalué à 2.

    Ton algorithme ressemble beaucoup à l'algorithme en temps linéaire O(n) que j'ai obtenu.
    Je fais plus ou moins la même chose mais où cells est une pile.
    Je parcours ma liste de chiffres et pour chaque chiffre c, je retire du haut de ma pile tous les chiffres plus petits que c, si celle ci reste suffisamment grande pour qu'il reste 12 chiffres à la fin.
    Ensuite je rajoute c à ma pile seulement si celle ci a moins de 12 éléments.
    C'est bien en temps linéaire car chaque élément retiré de la pile ne le sera qu'une seule fois.
    En pseudo-code ça donne

    cells = []
pour chaque (i, c) de enumerate(ligne)
 reste = taille(ligne) - i - 1
 tant que cells n'est pas vide
 c2 = dernier élément de cells
 si c2 < c et taille(cells) + reste >= 12
 retirer c2 de cells
 sinon
 break
 si taille(cells) < 12
 ajouter c à la fin de cells
renvoyer cells

    mais comme je disais, c'est moins rapide (du moins, mon implémentation) que celle en 12 passes.