Journal Advent of Code 2025

Posté par  . Licence CC By‑SA.
Étiquettes :
14
30
nov.
2025

Comme chaque année, durant le mois de décembre, a lieu l'advent of code.
https://adventofcode.com/2025

Chaque jour est proposé un problème algorithmique de difficulté croissante.
Le but initial est de le résoudre le plus vite possible mais on peut s'amuser comme on veut (juste le résoudre, avoir le temps d'exécution le plus bas, faire du code golfing, etc).

Chaque jour propose deux problèmes partageant la même input. Le second étant souvent lié au premier mais en version plus difficile. On gagne une étoile par problème résolu.
L'ouverture se fait à 6h mais on n'est pas obligé de se lever aussi tôt

Certains problèmes requièrent des notions algorithmiques souvent basiques (recherche de chemins, Dijstra, programmation dynamique, résolution de systèmes d'équations linéaires, théorème des restes chinois, etc).

Cette année, deux différences par rapport aux années précédentes:

  • Il n'y a plus de leaderboard global, je pense que c'est du aux grands nombres de LLM utilisées dans le leaderboard. Les leaderboards locaux existent toujours cependant.
    celui des membres de linuxfr est ici: https://adventofcode.com/2024/leaderboard/private/view/1844559

  • Il n'y aura que 12 journées, le créateur n'ayant plus le temps de s'occuper de 25 journées. Cependant, il annonce que la difficulté des énigmes croîtra plus rapidement et restera globalement la même.

Pour ma part, je le ferai en Rust comme durant les années précédentes.

Bon jeu à tous ceux qui y participent

  • # Décroissance vaincra !

    Posté par  . Évalué à 3 (+2/-0). Dernière modification le 30 novembre 2025 à 14:14.

    Cependant, il annonce que la difficulté des énigmes croira plus rapidement

    Je crois que tu ne connais pas bien le futur du verbe croître :-)

    • [^] # Re: Décroissance vaincra !

      Posté par  . Évalué à 1 (+0/-0).

      Merci d'avoir signalé l'erreur. J'ai l'impression que je ne peux plus modifier le texte maintenant (je ne connais pas très bien linuxfr).

      • [^] # Re: Décroissance vaincra !

        Posté par  (Mastodon) . Évalué à 3 (+0/-0). Dernière modification le 30 novembre 2025 à 19:12.

        Au bout de quelques minutes seuls les modérateurs peuvent effectuer une modification. Je viens de corriger.

        (et il a fallut que je vérifie j'étais vraiment pas sûr de moi !)

        En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

        • [^] # Re: Décroissance vaincra !

          Posté par  . Évalué à 3 (+1/-0).

          (et il a fallut que je vérifie j'étais vraiment pas sûr de moi !)

          Il s'agit donc d'une vérification récursive. :-)

        • [^] # Re: Décroissance vaincra !

          Posté par  (site web personnel) . Évalué à 6 (+4/-0).

          Au bout de quelques minutes seuls les modérateurs peuvent effectuer une modification

          tu confonds avec les commentaires qu'on peut éditer pendant 5 min.

          Un journal publié n'est modifiable que par l'équipe de modération.

          Ya que les pages wiki, les dépêches en rédaction, les entrées de forum et de suivi qu'un utilisateur identifié peut modifier (et les commentaires pendant un temps de grâce de 5 min).

          • [^] # Re: Décroissance vaincra !

            Posté par  (Mastodon) . Évalué à 3 (+0/-0).

            Oups :)

            Merci pour la précision.

            En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

            • [^] # Re: Décroissance vaincra !

              Posté par  (site web personnel) . Évalué à 2 (+0/-0). Dernière modification le 01 décembre 2025 à 11:32.

              ah mais merci à toi pour effectuer la modération dans la joie et la bonne humeur _o/

              en fait, je triche, j'ai une anti-sèche — bizarre je croyais qu'il y avait un tableau, bah peut-être ailleurs… — yaura une interro1 surprise au PSL ou à l'OSXP, si certains le souhaitent ! :D (mais pas de livre à gagner, ça c'est une main innocente qui le détermine :p)

              1. par exemple, qui peut ajouter des options à un sondage une fois publié ? Trouver (au moins) 3 méthodes pour voter plusieurs fois sur un sondage. Et ya moyen de faire plus compliqué :D ↩

  • # Leaderboard

    Posté par  . Évalué à 3 (+2/-0).

    A priori nous n'avons pas accès au lien pour voir le leaderboard de linuxfr.
    Je participe régulièrement à AoC, jamais jusqu'au bout cependant, difficile de justifier passer du temps à coder alors que la famille est en congés 😀

    • [^] # Re: Leaderboard

      Posté par  . Évalué à 3 (+2/-0).

      Ha oui, désolé.

      Si j'en crois les années précédentes, le code pour accéder au leaderboard de linuxfr est
      1844559-f65dbf07.

      • [^] # Re: Leaderboard

        Posté par  . Évalué à 2 (+0/-0).

        je confirme, je viens de le rejoindre en tant que utilisateur anonyme #5227760

    • [^] # Re: Leaderboard

      Posté par  (Mastodon) . Évalué à 2 (+0/-0). Dernière modification le 01 décembre 2025 à 17:20.

      Cette année tu devrais pouvoir aller au bout, puisque ça se termine le 12 décembre, au lieu du 24 !
      Et oui, j'ai toujours trouvé difficile de coder les derniers jours.

      Bon, bah c'est reparti hein :)

  • # Cet année, je vais faire plutot..

    Posté par  . Évalué à 6 (+5/-0). Dernière modification le 01 décembre 2025 à 01:33.

    Je ne pense pas le faire cette année.
    En ce moment , j essaie de progresser en ctf

    Je vais donc tenter faire le :https://ctf.xmas.root-me.org/

  • # Jour 1

    Posté par  . Évalué à 2 (+1/-0).

    Alors, qui participe cette année?

    Le jour 1 est facile comme chaque année mais la partie 2 demande un peu de réflexion si on cherche mieux que la solution naïve.

    • [^] # Re: Jour 1

      Posté par  (site web personnel) . Évalué à 5 (+4/-1).

      To play, please identify yourself via one of these services:

      [GitHub] [Google] [Twitter] [Reddit] - [How Does Auth Work?]

      eh ! il manque LinuxFr.org qui propose OAuth2 ;-) (et gitlab, et codeberg, et…)

    • [^] # Re: Jour 1

      Posté par  . Évalué à 3 (+1/-0).

      allez, j'ai fait le premier jour pour la première fois cette année. Je crois que 25 jours les années précédentes, c'était trop pour moi, 12, ça paraît plus abordable.

      qqu'un sait si c'est les données des problèmes sont personnalisées ou c'est données communes pour tous ?

      • [^] # Re: Jour 1

        Posté par  . Évalué à 2 (+1/-0).

        Il y a plusieurs jeux de données habituellement
        Donc plusieurs réponses, pas possible de juste copier la valeur réponse

      • [^] # Re: Jour 1

        Posté par  (Mastodon) . Évalué à 2 (+0/-0).

        Honnêtement, je ne sais pas s'il a un système pour générer des données, ou s'il a un panel.

        Mais a priori, chaque exercice peut toujours se résoudre rapidement, en temps de calcul, avec un algorithme bien pensé, donc c'est possible qu'il puisse générer des données pour chacun.
        A priori donc on a un jeu de données personnalisé, on ne peut pas comparer les résultats, mais on peut valider les données d'un autre sur son algo, ou l'algorithme d'un autre sur ses propres données.

        Ça m'est vraiment rarement arrivé d'avoir un code adapté en fonction de mes données (quelques optimisations au début, sans détection génériques).

        • Yth.

        • [^] # Re: Jour 1

          Posté par  . Évalué à 3 (+1/-0).

          Honnêtement, je ne sais pas s'il a un système pour générer des données, ou s'il a un panel.

          Surtout que les deux réponses sont possibles en fonction de l'avancée du jeu. Pour ce premier exercice, il est tout-à-fait possible d'écrire un générateur aléatoire.

          Par contre, il semble à peu près certain que chaque jeu de donnée est généré une fois pour toute pour chaque compte. Chaque participant reste donc sur un même jeu, qui lui est propre.

    • [^] # Re: Jour 1

      Posté par  . Évalué à 3 (+0/-0).

      la partie 2 demande un peu de réflexion si on cherche mieux que la solution naïve.

      D'expérience, j'essaye toujours de rendre le code de la partie 1 un peu évolutif, mais c'est difficile et parfois il faudrait tout recoder pour la partie 2, ce qui me semble un peu éloigné de l'objectif.

      Là j'ai juste décomposé les mouvements en unités, ce qui est très efficace en terme de réutilisation de code, mais sous-optimal en termes de perfs. Tu mets où ton critère entre efficacité du code et efficacité du développement? Est-ce que tant que tu es en O(n) tu es bon?

      • [^] # Re: Jour 1

        Posté par  . Évalué à 1 (+0/-0).

        Tu mets où ton critère entre efficacité du code et efficacité du développement? Est-ce que > tant que tu es en O(n) tu es bon?

        Ca dépend des années.
        La première fois que j'ai fait l'aoc, je cherchais la lisibilité et réutilisabilité du code.
        Mais cette année comme l'année dernière, je vise la vitesse d'exécution.

        • [^] # Re: Jour 1

          Posté par  (Mastodon) . Évalué à 3 (+1/-0).

          Aujourd'hui, je démarre comme une bouse, 1ère partie triviale, et 2de partie bourrée d'erreurs d'algo.
          J'ai tout recommencé avec une jolie classe et une unique fonction, appliquée dans une unique boucle, avec une itération par ligne de donnée, moins de 10 opérations basiques (tests, modulo, assignation, etc) dans la fonction, et les résultats des deux exercices sont calculés en une fois, et justes dès la première exécution :)

          Comme quoi, vouloir faire vite-fait, même au jour 1, c'pas toujours idéal…
          Bon, allez, demain je m'y mets plus tôt, et plus concentré !

          • Yth.

          • [^] # Re: Jour 1

            Posté par  . Évalué à 3 (+1/-0).

            Ça me rassure de ne pas être tout seul. :-)

            Et effectivement, structurer ses données proprement a été, par les années passées également, un moyen efficace d'éliminer rapidement la plupart des bugs, alors même que l'on pense tous raisonnablement coder à peu près proprement par ailleurs. Ce qui est remarquable ici, c'est de voir avec quel brio les scripts sont conçus pour les révéler. Il s'agit de bien plus que de simples cas d'écoles à la difficulté progressive.

    • [^] # Re: Jour 1

      Posté par  . Évalué à 2 (+0/-0).

      Alors, qui participe cette année?

      _o/

      Le jour 1 est facile comme chaque année mais la partie 2 demande un peu de réflexion si on cherche mieux que la solution naïve.

      Absolument et comme toujours, il y a même un piège qui n'est pas bien caché mais dans lequel on risque quand même de tomber si l'on va trop vite. Cela ajouté au temps nécessaire pour dégripper un peu les neurones après une période d'interruption.

      Même s'il n'est pas très sournois et qu'on le voit venir, on risque de se faire prendre si l'on rédige d'emblée des équations « un peu trop belles »…

    • [^] # Re: Jour 1

      Posté par  . Évalué à 3 (+1/-0).

      o/

      Premier jour facile. J'ai même pas pensé à brut-forcer la partie deux. Si j'avais galéré sur un cas limite, je l'aurai fait. Mais là c'est passé du premier coup.

      En réorganisant un peu le code, la solution aux deux parties en 9 lignes :

      ans1 = ans2 = 0
pos = new_pos = 50
for line in open(0):
    t,q = divmod(int(line[1:]), 100)
    new_pos += q if line[0] == "R" else -q
    ans2 += t + ((pos>0 and new_pos<=0) or new_pos>=100)
    pos = new_pos = new_pos % 100
    ans1 += (pos == 0)
print(ans1, ans2)

      • [^] # Re: Jour 1

        Posté par  (Mastodon) . Évalué à 3 (+1/-0).

        J'ai perdu le fil de mes pensées sur l'équivalent de ta ligne ans2 += t + ((pos>0 and new_pos<=0) or new_pos>=100), j'ai laissé tombé l'idée d'être intelligent à ce moment là, et suis parti sur du clair et sûr.

        class Serrure:
    pos = 50
    sens = "R"
    clic = 0
    zero = 0
    def __call__(self, rotation):
        sens = rotation[0]
        valeur = int(rotation[1:])
        if sens != self.sens:
            self.sens, self.pos = sens, (-self.pos)%100
        clic, self.pos = divmod(self.pos + valeur, 100)
        self.zero += self.pos==0  # exercice 1
        self.clic += clic  # exercice 2

serrure = Serrure()
for x in data.strip().splitlines(): # data
    serrure(x)

ex1 = serrure.zero
ex2 = serrure.clic
        • Yth.

        • [^] # Re: Jour 1

          Posté par  . Évalué à 2 (+0/-0).

          Je m'étais fait un petit dessin ; ça m'a aidé.
          À l'inverse, retourner le cadran pour se retrouver systématiquement sur le cas "sens des aiguilles d'une montre" (="R") m'a paru une gymnastique plus compliquée.

  • # Jour 2

    Posté par  . Évalué à 2 (+0/-0).

    Jour que j'ai trouvé plus facile que le précédent, mais plus laborieux.

    J'ai blêmi en voyant une énoncée avec des "ranges" car j'ai un très mauvais souvenir d'un problème d'intersection de range ; mais il n'en est rien ici.

    J'ai aussi pensé qu'on aurait un problème de passage à l'échelle pour la partie 2 ; mais il n'en est rien non plus.

    Patience, ce sera pour la prochaine :)

    • [^] # Re: Jour 2

      Posté par  . Évalué à 2 (+0/-0).

      Je mets le code, même si je ne lui trouve rien d'intéressant:

      def is_invalid_p1(n):
    s = str(n)
    m = len(s) // 2
    return s[:m] == s[m:]

def chunk_str(s, l):
    for i in range(0, len(s), l):
        yield s[0+i:l+i]

def is_invalid_p2(n):
    s = str(n)
    l = len(s)
    for m in range(1,1+(l//2)):
        if (l%m) == 0:  # if str can be chunked equally
            a = chunk_str(s,m)
            b = chunk_str(s,m)
            next(b)
            if all(u==v for (u,v) in zip(a,b)):
                return True
    return False

ans1 = ans2 = 0
for line in open(0).read().split(','):
    f, t = line.split("-")
    f = int(f)
    t = int(t)
    for i in range(f, t+1):
        if is_invalid_p1(i):
            ans1 += i
        if is_invalid_p2(i):
            ans2 += i
print(ans1, ans2)

      (C'est dans ces moments que j'aimerai que linuxfr supporte le details/summary).

      • [^] # Re: Jour 2

        Posté par  (site web personnel) . Évalué à 3 (+1/-0).

        (C'est dans ces moments que j'aimerai que linuxfr supporte le details/summary).

        c'est par ici le suivi ;-)

        reste à trouver une syntaxe Markdown appropriée…

    • [^] # Re: Jour 2

      Posté par  . Évalué à 3 (+2/-0).

      Pour le problème du jour, ma première approche a consisté à énumérer chaque id de chaque intervalle et tester s'il est invalide ou non.
      Ca prend 100ms, c'est raisonnable mais j'ai cherché une solution plus efficace.

      Je fais 2 suppositions sur l'input:

      • Tous les intervalles sont deux à deux disjoints
      • Chaque nombre contient au plus 10 chiffres

      Pour la partie 1:
      Pour l'exemple, on considère un intervalle [start, end] où start et end sont tous les deux des entiers à 6 chiffres.
      Alors, les ids invalides pour cet intervalle sont les entiers multiples de 1001 dans cet intervalle.
      Il faut donc faire la somme d'une suite arithmétique et ça peut se faire de manière efficace (en temps constant) sans avoir à itérer sur les valeurs de l'intervalle.

      Pour la partie 2, c'est un peu plus compliqué.
      Gardons le même exemple. La somme des ids invalides est la somme des multiples de 1001 (comme dans la partie 1) et des multiples de 10101 (si on coupe l'entier en 3).
      Le problème, c'est qu'on a pu compter des ids en double (ceux à la fois multiples de 1001 et de 10101, ce qui correspond aux multiples de 111111).
      Il faut donc retirer la somme de ces ids du total.
      Les entiers posant ce problème sont ceux à 6 chiffres et ceux à 10 chiffres.

      Je ne vais pas poster mon code car il est peu long et très moche.

      Ca prend moins d'une microseconde soit 100_000 fois plus rapide que la première approche.

    • [^] # Re: Jour 2

      Posté par  (Mastodon) . Évalué à 2 (+0/-0).

      J'ai adopté une approche qui consiste à regarder les valeurs possibles en fonction de la première partie de l'identifiant (par exemple pour 1188511880-1188511890 exercice 1 on a uniquement 11885, mais pour 111200-222200, avec 3 répétitions on aurait tout dans [11-22]).
      Je les multiplie par le nombre de répétition (ici ça donne 1188511885, ou 111111, 121212, …, 222222), et on vérifie si le nombre est dans l'intervalle.

      Pour simplifier, je redécoupe les intervalles où les nombres n'ont pas la même taille, par exemple je remplace 95-115 par 95-99 et 100-115, au début.
      Après pour l'exercice 1 on regarde que sur les nombres répétés deux fois, et pour l'exercice 2 on teste toutes répétitions de 2 à longueur.

      Pour l'exercice 2 il faut dédupliquer, par exemple 222220-222224 donne 222222 pour 222|222, 22|22|22 et 2|2|2|2|2|2.

      class Range:
    def __init__(self, a, b):
        self.sa, self.sb = str(a), str(b)
        self.a, self.b = int(a), int(b)
        self.len=len(self.sa)
    def invalid(self, repeat=2):
        if self.len%repeat: return  # longueur non divisible par le nb de répétitions
        for root in range(
                int(self.sa[:self.len//repeat]),
                int(self.sb[:self.len//repeat])+1):
            if self.a <= (v:=int(str(root)*repeat)) <= self.b:
                yield v
    def all_invalid(self):
        for repeat in range(2, self.len+1):
            yield from self.invalid(repeat)


r=[]  # ranges de même taille, eg 95-115 => 95-99, 100-115
for rng in data:
    a, b = (int(_) for _ in rng.split("-"))
    ta = a
    while ta < b:
        tb = min(int("9"*len(str(ta))), b)
        r.append(Range(ta, tb))
        ta = tb+1

ex1 = sum(v for _ in r for v in _.invalid())
ex2 = sum({v for _ in r for v in _.all_invalid()})
      • Yth.

      • [^] # Re: Jour 2

        Posté par  . Évalué à 2 (+0/-0). Dernière modification le 03 décembre 2025 à 09:12.

        j'optimise pour le temps que j'y passe, ça fait pas du code très performant :) Pour le jour 2, mon code calcul la partie 2 en un peu moins de 4 secondes (en même temps, c'est du python).

        Pour la partie 1, c'est la même idée que steph1978, cad comparer les deux moitiés des nombres dont la représentation en caractères est de longueur pair.

        pour la partie 2, je tronçonne la représentation en sous-chaînes de longueur i pour toutes les longueurs i pertinentes (i variant de 1 à la moitié de la longueur de la représentation, et seulement si la longueur est divisible par i), et j'ajoute les tronçons de chaînes dans un set. En Python, un set ne pouvant contenir qu'une seul occurrence de chaque valeur, chaque fois qu'un tronçon déjà présent est ajouté, le set ne bouge pas. Si le set est de taille 1 à la fin de l'opération, tous les tronçons étaient identiques, on a trouvé un nombre invalide.

    • [^] # Commentaire supprimé

      Posté par  (Mastodon) . Évalué à 2 (+0/-0). Dernière modification le 03 décembre 2025 à 08:04.

      Ce commentaire a été supprimé par l’équipe de modération.

  • # Jour 3

    Posté par  . Évalué à 2 (+0/-0).

    Difficile de départager ces trois premiers jours en terme de difficulté. On est peut être sur un "hockey stick" et on attend le point d'inflexion, peut être demain.

    Ce jour, première partie en one shot, sans passer par l’exemple 😎. Pour la deuxième partie, j'ai un peu ratatouillé sur les conditions d'arrêt de ma fonction récursive 😩 et perdu un peu de temps.

    Pour les curieux (ou masochiste), je mets le code dans le commentaire en dessous.
    Vous pouvez le fermer en appuyant sur [-] pour éviter le spoil.

    • [^] # Re: Jour 3

      Posté par  . Évalué à 2 (+0/-0).

      Voici le code, 11 lignes, refactoré pour traiter les deux parties en une fois:

      def findmax(bank,n):
    if n>=len(bank): return bank
    if n==0: return ""
    m = max(bank[:len(bank)-n+1])
    i = bank.find(m)
    return m + findmax(bank[i+1:], n-1)
ans1 = ans2 = 0
for bank in open(0).read().strip().split('\n'):
    ans1 += int(findmax(bank,2))
    ans2 += int(findmax(bank,12))
print(ans1, ans2)

      • [^] # Re: Jour 3

        Posté par  (Mastodon) . Évalué à 4 (+2/-0). Dernière modification le 03 décembre 2025 à 14:31.

        Assez similaire dans l'algo au bout du compte, j'ai passé assez rapidement le second exercice, pas de bug, j'ai trouvé plus simple celui du jour.

        • Yth.
        data = stdin.read().strip().splitlines()

def joltage(bank, count=2):
    r, i, bank = [], 0, bank+"."  # bank[i:-0] does not work, going for [:-1] with 1 garbage
    for n in range(count, 0, -1):
        r.append(a:=max(bank[i:-n]))
        i += bank[i:].index(a)+1  # i(ndex) of next unused battery inside bank
    return int("".join(r))

ex1 = sum(joltage(_, 2) for _ in data)
ex2 = sum(joltage(_, 12) for _ in data)

    • [^] # Re: Jour 3

      Posté par  . Évalué à 1 (+0/-0).

      J'ai écrit un algorithme similaire aux deux plus haut (en version itérative).

      J'ai aussi obtenu un algorithme linéaire, en une seule passe sur la chaîne, mais celui s'avère plus lent sur le jeu de données que l'algorithme initial.

      J'aurais aimé trouver un algorithme plus efficace mais tant pis.

    • [^] # Re: Jour 3

      Posté par  . Évalué à 3 (+1/-0).

      Je propose à mon tour mon approche de la deuxième partie du jour 3.

      Même chose : j'évite l'approche récursive en faisant une seule passe sur chaque banc de pile. On a donc une complexité en n×m mais on peut la considérer linéaire si on part du principe que le nombre de piles à combiner est constant (2 dans la première phase, 12 dans la seconde).

      Étant donné que d'une part, 20000 sera toujours supérieur à 19999, pour chaque pile dans le banc examiné, on a tout intérêt à remplacer la première pile qu'elle dépasse dans le jeu et invalider les suivantes.

      La première ligne « continue » au début de la deuxième boucle sert à gérer la fin du banc de pile : lorsqu'il reste moins de douze piles à examiner dans le banc, on ne peut plus remplacer les premières (parce qu'il n'y en aurait plus assez pour remplir le jeu) mais il en reste suffisamment pour remplacer les dernières.

      from functools import reduce

puzzle2_mode = True
row_count    = 0
total        = 0

battery_num  = 12 if puzzle2_mode else 2

with open(input_file_name) as f:
    row_count += 1
    for l in f:

        l     = l.strip()
        ll    = len(l)
        cells = [ 0 ] * battery_num

        for i,n1 in enumerate(l):
            n1 = int(n1)

            for j,n2 in enumerate(cells):
                if ll - i - battery_num + j < 0: continue
                if n2 >= n1:                     continue

                cells  = cells[0:j] + [n1]
                cells += [ 0 ] * (battery_num - len(cells))
                break

        jolts  = reduce(lambda j,c: j*10+c, cells, 0)
        total += jolts
        print(l, cells, jolts)

print("Nombre de bancs :", row_count)
print("Total des jolts :", total)

      • [^] # Re: Jour 3

        Posté par  . Évalué à 2 (+1/-0).

        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.

        • [^] # Re: Jour 3

          Posté par  . Évalué à 2 (+0/-0). Dernière modification le 03 décembre 2025 à 19:26.

          c'est moins rapide […] que celle en 12 passes.

          C'est normal, parce que l'étape retirer c2 de cells est coûteuse car il faut créer une nouvelle structure de données à chaque fois.

          Alors qu'une boucle (ou de la récursivité) sur une même structure de données, ça ne coûte pas très cher.

          • [^] # Re: Jour 3

            Posté par  . Évalué à 3 (+2/-0).

            Non, si tu utilises une pile, ça se fait en temps constant (quand je dis retirer c2, je voulais dire juste retirer l'élément en haut de la pile).

    • [^] # Re: Jour 3

      Posté par  . Évalué à 2 (+1/-0).

      Hello.

      Un peu bataille jour 1, a trop vouloir resoudre mathematiquement pour la partie 2 (alors que mes souvenirs sur le sujet commencent a se faire vieux, comme moi) et j'ai fini par me resoudre au mode bourrin. Un peu traine hier, mais sans difficulte pour autant, et aujourd'hui, en effet rien de complique.
      Ma solution partielle (en python), dans la meme veine que les premieres propositions:

          def joltage(self, batteries: int) -> int:
        s = ''
        idx = 0
        for i in range(batteries - 1, -1, -1):
            subi, nc = max([t for t in enumerate(self.batteries[idx:-i if i else None])], key=lambda t: (t[1], -t[0]))
            s += nc
            idx += subi + 1
        return int(s)

      Et si je puis me permettre un peu d'auto-promotion, la solution complete ici

      ++
      Gi)

  • # Jour 4

    Posté par  . Évalué à 2 (+0/-0).

    Je profite d'un lever matinal pour m'attacher à la quatrième tâche. :-)

    Rien de fondamentalement difficile ici. Ce qui est intéressant, en revanche, c'est la « carte » formée par l'érosion introduite par la seconde phase.
    https://imgur.com/a/aoc-2025-04-PiWHV2z

    Pour le reste, il y aurait probablement de l'optimisation à faire si l'on travaillait sur de très grandes cartes, en circonscrivant des territoires pour éviter de la traiter entièrement à chaque passe, mais rien qui justifie cet investissement en l'état, je pense.

    • [^] # Re: Jour 4

      Posté par  . Évalué à 3 (+2/-0).

      La partie 1 est facile.
      La partie 2 est un problème sur les graphes et peut être obtenu en temps linéaire de la manière suivante.

      On maintient un tableau deg qui pour chaque sommet associe le nombre de @ adjacents.
      On maintient aussi une pile des sommets à traiter.
      Pour chaque sommet v à traiter dans pile, et pour chaque voisin u de v, on décrémente deg[u] et si deg[u] == 3, on ajoute u à la pile.

      En pseudo code ça donne ça

      compteur = 0
pile = []
Calculer le tableau deg

pour chaque sommet v tel que grid[v] == @ et deg[v] <= 3
   pile.push(v)

tant que pile non vide
   v = pile.pop()
   compteur += 1
   pour chaque voisin u de v tel que grid[u] == @
      deg[u] -= 1
      si deg[u] == 3
         pile.push(u)
renvoyer compteur

      160 microsecondes pour les deux parties

      • [^] # Re: Jour 4

        Posté par  . Évalué à 2 (+0/-0).

        En effet, je pensais à quelque chose de similaire également, mais je me demandais si le coût de construction du graphe ne compensait pas le gain engendré. En réalité non, puisque la seule première passe consiste déjà à faire quasiment tout ce travail puisqu'il faut examiner tous les nœuds et, pour chacun d'eux, l'état des huit voisins…

        Ce qui est intéressant, c'est que c'est effectivement linéaire à partir du moment où l'on peut être certain que chaque nœud qui aura transité par la pile n'y aura été inséré puis supprimé qu'une seule fois. Car autrement, cela ressemblait un peu à la suite de Syracuse… :-)

        • [^] # Re: Jour 4

          Posté par  . Évalué à 2 (+1/-0).

          A vrai dire, je ne construis pas vraiment le graphe, je déduis les voisins à partir de la grille.
          Par contre, j'ai besoin de stocker un tableau des degrés.
          Je me demande si je ne peux pas réutiliser le tableau de la grille et le modifier.
          Mais je ne suis pas sûr que je gagne vraiment en temps de calcul.

          Les sommets stockés dans la pile ne le sont qu'une seule fois car ils sont insérés seulement quand leur degré vaut exactement 3 et par la suite le degré sera inférieur à 3.

          Sinon, pour les curieux, j'ai appris aujourd'hui que ce problème s'appelle k-core.
          Plus précisément, le k-core d'un graphe est le plus grand sous-graphe H où tous les sommets ont au moins k sommets voisins à l'intérieur H.
          Donc on cherche ici à trouver le nombre de sommets n'appartenant pas au 4-core.

    • [^] # Re: Jour 4

      Posté par  . Évalué à 4 (+2/-0).

      Très bon jour.

      Première partie en one shot, sans passer par l'exemple ; deuxième partie en 1 essai ; en moins de 10 minutes.

      Je suis passé par des sets, très facile à manipuler en python et plutôt efficaces en perf.

      Voici le code, un peu refactoré pour tenir en 6 lignes:

      rolls0 = rolls = {(i,j) for i,line in enumerate(open(0)) for j,c in enumerate(line) if c == '@'}
l = 999999999
while len(rolls)<l:
    l = len(rolls)
    rolls = {(x,y) for (x,y) in rolls 
        if 3<sum(((x+dx,y+dy) in rolls)
            for (dx,dy) in [(0,-1),(1,0),(0,1),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)])}
    print(len(rolls0)-len(rolls))

      Cela prend 16MB de RAM et 0.7s de CPU.

    • [^] # Re: Jour 4

      Posté par  (Mastodon) . Évalué à 3 (+1/-0).

      Jour 4 : pour des raisons personnelles, aucun accès à un ordinateur de la journée. Mais une balade, fairphone à la main.
      Armé de mon qpython, je code…
      Ici, pas de noms de variables explicites, parce que écrire sur un clavier tactile, c'est chiant, donc moins on écrit, mieux on se porte.
      Ici, un classique, pour tester les 8 directions, on définit une carte en ayant ajouté une bordure vide autour, qu'on bascule en 1 dimension, avec huit déplacements entiers.

      data = data.strip().splitlines()

H = len(data)+2
W = len(data[0])+2
map = " "*W + "".join(f" {x} " for x in data) + " "*W
dirs=[-1,1,-W,W,-W-1,-W+1,W-1,W+1]

def count(p):
    return sum(1 for d in dirs if map[p+d]=="@")

def step():
    r=[i for i,x in enumerate(map) if x=="@" and count(i)<4]
    m="".join(x if i not in r else " " for i,x in enumerate(map))
    return m,len(r)

map,n=step()
ex2=ex1=n
while n:
    map,n=step()
    ex2+=n

      Durée difficile à évaluer, c'est lent en qpython, zéro chance de brute force.
      On est à 3s environ, donc l'algo est assez bon 😉

      • Yth.

      • [^] # Re: Jour 4

        Posté par  (Mastodon) . Évalué à 2 (+0/-0).

        On peut facilement faire mieux en stockant les adresses des @ dans un ensemble, et en supprimant à chaque itération ceux qu'on a pu repérer.

        Ça évite de reconstruire une carte, et ça laisse manipuler uniquement des ensembles d'entiers, ça doit forcément être plus efficace que de jouer avec une chaîne de caractères.

        • Yth.

        • [^] # Re: Jour 4

          Posté par  . Évalué à 2 (+0/-0).

          Je te confirme que c'est plus rapide. C'était ma première version, celle avec laquelle j'ai validé les étoiles.
          Mais ça ne tient pas en 6 lignes 😄

    • [^] # Re: Jour 4

      Posté par  . Évalué à 2 (+1/-0).

      Bien traine encore ajd, un peu sur la partie 1 pour cause de boulette tellement plus grosse que moi que j'ai peine a mettre la main dessus, puis sur la partie 2 quand j'ai realise que du bete parcours de tableau, ca peut etre looooooooooooooooong, ce qui m'a valu de tt refacto.

      Au final, mes 2 fonctions:

          def count_reachable_rolls(self) -> int:
        return len(self._reachable_rolls(self.rolls))

    def count_removable_rolls(self) -> int:
        rolls = self.rolls.copy()
        while rem := self._reachable_rolls(rolls):
            rolls -= rem
        return len(self.rolls) - len(rolls)

      Et l'integralite ici

  • # jour 5

    Posté par  . Évalué à 2 (+0/-0). Dernière modification le 05 décembre 2025 à 09:48.

    Pas sur de voir une différence de difficulté entre ces cinq premiers jours.

    Aujourd'hui, première partie en oneshot. Par contre j'ai trop ramé pour faire l'algo de fusion des intervalles alors que c'est tout bête au final 😕

    Je mets le code dans le commentaire en dessous. Vous pouvez le fermer en appuyant sur [-] pour éviter le spoil.

    • [^] # Re: jour 5

      Posté par  . Évalué à 3 (+1/-0).

      Partie 1:

      I = open(0).read().strip().split("\n\n")
R = [i.split("-") for i in I[0].split("\n")]
R = [(int(a),int(b)) for (a,b) in R]
I = [int(i) for i in I[1].split("\n")]
print(sum(any(a <= i <= b for (a,b) in R) for i in I))

      Partie 2

      I = open(0).read().strip().split("\n\n")
R = [i.split("-") for i in I[0].split("\n")]
R = sorted((int(a),int(b)) for (a,b) in R)
ans = 0
t = R[0]  # tail
for r in R[1:]:
    (a,b) = t
    (c,d) = r
    if a <= c <= b: # if can merge
        t = (a, max(b,d))  # extend
    else:  # count range
        ans += b-a+1
        t = r
(a,b) = t
ans += b-a+1
print(ans)

      • [^] # Re: jour 5

        Posté par  . Évalué à 3 (+1/-0).

        Ce qui prouve encore une fois qu'en Python, il y a toujours moyen de faire plus concis que ce que l'on a réussi à faire jusque là :-)

        • [^] # Re: jour 5

          Posté par  . Évalué à 3 (+1/-0).

          Tu ne crois pas si bien dire.

          Les deux parties en 11 linges :

          I, J = open(0).read().strip().split("\n\n")
t, *R = sorted(tuple(map(int,i.split("-"))) for i in I.split("\n"))
print(sum(any(a <= int(i) <= b for (a,b) in [t]+R) for i in J.split("\n")))
ans = 0
for r in R:
    if t[0] <= r[0] <= t[1]:
        t = (t[0], max(t[1],r[1]))
    else:
        ans += t[1]-t[0]+1
        t = r
print(ans + t[1]-t[0]+1)

          • [^] # Re: jour 5

            Posté par  . Évalué à 4 (+2/-0). Dernière modification le 05 décembre 2025 à 20:56.

            Et en 4 lignes en utilisant reduce:

            I,J = open(0).read().strip().split("\n\n")
t, *R = sorted(tuple(map(int,i.split("-"))) for i in I.split("\n"))
print(sum(any(a <= int(i) <= b for (a,b) in [t]+R) for i in J.split("\n")))
print(__import__("functools").reduce(lambda a, r: a if r[1] <= a[1] else (a[0] + (r[1]-r[0]+1 if r[0]>a[1] else r[1]-a[1]), r[1]), R, (t[1]-t[0]+1,t[1]))[0])

            Pour comprendre, l'accumulateur est, à tout moment de la réduction, un tuple[la somme accumulé, le max atteint].

            • [^] # Re: jour 5

              Posté par  . Évalué à 4 (+2/-0). Dernière modification le 06 décembre 2025 à 15:58.

              Et comme le jour 6 ne m'a pas plu, je me suis vengé avec cette version de la partie 2 du jour 5 en une ligne de 199 caractères :

              print(__import__("functools").reduce(lambda a,r:(a[0]+r[1]-max(r[0]-1,a[1]),r[1])if r[1]>a[1]else a,sorted(tuple(map(int,i.split("-")))for i in open(0).read().split("\n\n")[0].split("\n")),(0,0))[0])

              🏌️

    • [^] # Re: jour 5

      Posté par  . Évalué à 2 (+1/-0).

      Pour la première partie 1, je trie les intervalles par ordre de début et je fais de la recherche dichotomique pour chaque ingrédient.

      Pour la partie 2, j'avais déjà une fonction sous le coude que j'avais implémenté pour un aoc d'une année précédente donc ça a été rapide.

      20 microsecondes pour les deux parties

      • [^] # Re: jour 5

        Posté par  . Évalué à 3 (+1/-0).

        Même chose : j'avais déjà, il y a très longtemps, écrit une petite lib en contexte professionnel pour gérer des intervalles, donc ça m'a rappelé des souvenirs. Je ne l'ai pas reprise mais par contre, j'ai géré les recouvrements dès la première partie pour produire une liste triée et unifiée.

        Pareil ensuite : recherche dichotomique dans la liste pour les ingrédients et quand est arrivée la phase 2, j'avais déjà tout sous la main.

    • [^] # Re: jour 5

      Posté par  . Évalué à 1 (+0/-0).

      Hello

      Perso, j'ai trouve l'exercice de ce jour presque plus facile que ceux des jours precedents.
      Je me suis bien embourbe un peu a vouloir gerer ca avec des sets, donc le plus long ce fut de kill mon process python pendant que sa conso memoire mettait mon systeme a mal.
      Au final, une solution assez similaire aux deux proposees plus haut a ceci pres que:

      • plus lourd car decompose en fonctions, dont parse_input et is_fresh qui sont lourdingues

      • usage de range plutot que tuple, pas sur que ca fasse une grande difference, si ce n'est que ca deplace la gestion des +1

      • un test un poil plus efficace pour l'exo 2 (a <= c ou t[0] <= r[0] sont inutiles, la liste etant triee :p)

      Ce qui donne:

      def parse_input(data: list[str]) -> tuple[list[range],list[int]]:
    fresh = []
    ingredients = []
    first = True
    for line in data:
        if line:
            if first:
                low, high = map(int, line.split('-'))
                fresh.append(range(low, high+1))
            else:
                ingredients.append(int(line))
        else:
            first = False
    return (fresh, ingredients)

def is_fresh(ingredient: int, known_fresh: list[range]) -> bool:
    for r in known_fresh:
        if ingredient in r:
            return True
    return False

def exo1(data: list[str]) -> int:
    fresh, check = parse_input(data)
    return sum([is_fresh(i, fresh) for i in check])

def exo2(data: list[str]) -> int:
    fresh, _ = parse_input(data)
    fresh.sort(key=lambda r: (r.start, r.stop), reverse=True)
    r = fresh.pop()
    count = 0
    while fresh:
        next_r = fresh.pop()
        if next_r.start > r.stop:
            count += len(r)
            r = next_r
        else:
            r = range(r.start , max([r.stop, next_r.stop]))
    return count + len(r)

      ++
      Gi)

    • [^] # Re: jour 5

      Posté par  (Mastodon) . Évalué à 2 (+0/-0).

      Jour 5, 6, 7, 8, pas d'ordinateur, résolus en balade, dans la forêt, sur un téléphone…

      Donc concis, moche, peu clair, mais un minimum performant, et je me rappelle plus de l'énoncé, alors pour expliquer…

      def range_ingredients(a,b):
    return range(min(a, b), max(a, b)+1)

ranges=[
    range_ingredients(*(int(_) for _ in l.split("-")))
    for l in data
    if "-" in l
]
ingredients={int(l) for l in data if l and "-" not in l}
ex1=sum(any(i in r for r in ranges) for i in ingredients)

ranges=sorted(sorted(int(_) for _ in l.split("-")) for l in data if "-" in l)
a=b=ranges[0][0]
ex2=0
for c, d in ranges:
    if c <= b:
        b=max(b, d)
    else:
        ex2+=b-a+1
        a,b=c,d
ex2+=b-a+1
      • Yth.

  • # Jour 6

    Posté par  . Évalué à 3 (+2/-0).

    La partie 1 est facile.
    La partie 2 n'est pas compliqué algorithmiquement mais j'ai un galéré à bien l'implémenter.
    Je ne suis pas très fan du problème de ce jour. Je préfère les problèmes avec des astuces algorithmiques (enfin, il y en a peut-être mais je ne les ai pas vu).

    Les deux parties se font en temps linéaire avec un espace proportionnel au nombre de lignes (en plus de l'input).
    25 microsecondes pour les deux parties.

    J'envoie que la partie 1. J'enverrai la partie 2 quand j'aurais un peu nettoyé le code.

    fn part1(lines: &[&[u8]]) -> u64 {
    let mut numbers: Vec<_> = lines[..lines.len()-1]
        .iter()
        .map(|line| line.iter_unsigned::<u64>())
        .collect();
    let operators = lines.last().unwrap().iter().filter(|&&c| c != b' ');

    operators.map(|&op|
        if op == b'+' {
            numbers.iter_mut().map(|it| it.next().unwrap()).sum::<u64>()
        } else {
            numbers.iter_mut().map(|it| it.next().unwrap()).product()   
        }
    ).sum()
}

    • [^] # Re: Jour 6

      Posté par  . Évalué à 2 (+0/-0).

      Je ne suis pas très fan du problème de ce jour. Je préfère les problèmes avec des astuces algorithmiques (enfin, il y en a peut-être mais je ne les ai pas vu).

      Tout pareil.

      Je mets le code de la partie 1, c'est le moins laid des deux:

      from operator import mul, add
from functools import reduce
*N, O = open(0).read().strip().split('\n')
N = [list(map(int,l.split())) for l in N]
print(sum(reduce(add if o=='+' else mul, [N[j][i] for j in range(len(N))]) for i,o in enumerate(O.split())))

    • [^] # Re: Jour 6

      Posté par  . Évalué à 2 (+1/-0).

      Hello.

      Assez d'accord avec les jugements precedents: pas de difficulte ajd, mais une transformation prealable des donnees pour la partie 2 un peu delicate (la seule fonction a ne pas faire 1 ou 2 lignes).

      from __future__ import annotations
from functools import reduce
import operator
import re
from typing import Iterable

RE_OP = re.compile(r'([+*]) +')

class Operation:
    operations = {
        '+': sum,
        '*': lambda l: reduce(operator.mul, l)
    }

    def __init__(self, operator: str, operands: Iterable[int]):
        self.operator = operator
        self.operands = operands

    @classmethod
    def from_data_1(cls, data: tuple[str]) -> Operation:
        return cls(data[-1], map(int, data[:-1]))

    def operate(self) -> int:
        return self.operations[self.operator](self.operands)


def parse_input_1(data: str) -> Iterable[tuple[str]]:
    return zip(*[line.split() for line in data.strip('\n').split('\n')])

def parse_input_2(data: str):
    def to_numbers(lines: list[str]) -> Iterable[int]:
        for i in range(len(lines[0])):
            if n := ''.join([l[i] for l in lines]).replace(' ', ''):
                yield int(n)

    lines = data.strip('\n').split('\n')
    ops = lines[-1]
    lines = lines[:-1]
    for m in RE_OP.finditer(ops):
        yield Operation(m.group(1), to_numbers(list(map(lambda s: s[::-1], map(lambda l: l[m.start():m.end()][::-1], lines)))))

def exo1(data: str) -> int:
    operations = map(Operation.from_data_1, parse_input_1(data))
    return sum(map(lambda o: o.operate(), operations))

def exo2(data: str) -> int:
    operations = parse_input_2(data)
    return sum(map(lambda o: o.operate(), operations))

      ++
      Gi)

    • [^] # Re: Jour 6

      Posté par  (Mastodon) . Évalué à 2 (+0/-0).

      Pour la partie 2, je transpose la matrice des données en inversant les X et les Y, en gros ça fait un miroir par la diagonale, pour lire dans l'autre sens.
      En ayant retiré la ligne d'opérateurs à la fin.
      Et après les nombres sont séparés par des lignes vides.
      C'est assez simple.

      from operator import mul, add
data = sys.stdin.read().strip().splitlines()

op=[{"+":add,"*":mul}[_] for _ in data[-1].split()]

r=[0 if o==add else 1 for o in op]
for l in data[:-1]:
    for i,v in enumerate(l.split()):
        r[i]=op[i](r[i],int(v))
ex1=sum(r)

d=[  # bascule de matrice
 "".join([l[j] for l in data[:-1]]).strip()
 for j in range(len(data[0]))
]
i,r=0,[0 if o==add else 1 for o in op]
for l in d:
    if not l:
        i+=1
        continue
    r[i]=op[i](r[i],int(l))
ex2=sum(r)

      Prodigieusement peu lisible, mais assez concis :)

      • Yth.

  • # Jour 7

    Posté par  . Évalué à 2 (+1/-0).

    Rien de bien complique ajd, mais j'ai quand meme perdu un peu de temps sur la premiere partie, faute de tenir compte du fait qu'un splitter devait voir passer un beam pour etre active… Ce qui donne

    from typing import Iterable, NamedTuple


class Position(NamedTuple):
    x: int
    y: int


class Manifolder:
    def __init__(self, data: list[str]) -> None:
        self.grid = data
        self.height = len(self.grid)
        self.width = len(self.grid[0])

    def is_divider(self, pos: Position) -> bool:
        return self.grid[pos.y][pos.x] == '^'

    def divisions(self) -> Iterable[int]:
        beams = {self.grid[0].index('S')}
        for y in range(2, self.height, 2):
            splitters = [p for p in map(lambda x: Position(x, y), range(self.width)) if self.is_divider(p) and p.x in beams]
            beams |= {p.x-1 for p in splitters}
            beams |= {p.x+1 for p in splitters}
            beams -= {p.x for p in splitters}
            yield len(splitters)

    def timelines(self) -> int:
        timelines = { i: int(self.grid[0][i] == 'S') for i in range(self.width)}
        for y in range(2, self.height, 2):
            splitters = [p for p in map(lambda x: Position(x, y), range(self.width)) if self.is_divider(p) and p.x in timelines.keys()]
            for s in splitters:
                v = timelines[s.x]
                timelines[s.x] = 0
                timelines[s.x-1] += v
                timelines[s.x+1] += v
        return sum(timelines.values())

def exo1(data: list[str]) -> int:
    return sum(Manifolder(data).divisions())

def exo2(data: list[str]) -> int:
    return Manifolder(data).timelines()

    ++
    Gi)

    • [^] # Re: Jour 7

      Posté par  . Évalué à 2 (+1/-0). Dernière modification le 07 décembre 2025 à 13:09.

      Même approche ici. C'est de la programmation dynamique mais assez facile.

      Je stocke un tableau timelines qui pour chaque indice i d'une ligne me donne le nombre de timelines à la position (j, i) où j est à la ligne en cours.
      Je pensais qu'il faudrait stocker un tableau des timelines de la ligne précédente mais en fait ça ne sert à rien.

      Petite astuce, lorsque l'on traite la ligne i, on a besoin juste de regarder les indices [start_pos-i-1..start_pos+i+1] ce qui accélère un peu les choses.

      Je pense que la partie 1 doit se vectoriser très bien mais je ne suis pas compétent en SIMD.
      https://fr.wikipedia.org/wiki/Single_instruction_multiple_data

      Le code pour les deux parties (~3 microsecondes).

      pub fn solve(input: &str) -> (u32, u64) {
    let input = input.as_bytes();
    let width = input.iter().position(|&b| b == b'\n').unwrap() + 1;
    let start_pos = input.iter().position(|&b| b == b'S').unwrap();
    let mut p1 = 0;
    let mut count = vec![0; width];
    count[start_pos] = 1;
    for (delta, line_start) in (2*width..input.len()).step_by(2*width).enumerate() {
        let start = start_pos - delta - 1;
        let end = start_pos + delta + 2;
        for i in start..end {
            if input[line_start+i] == b'^' {
                p1 += (count[i] != 0) as u32;
                count[i-1] += count[i];
                count[i+1] += count[i];
                count[i] = 0;
            }
        }
    }

    let p2 = count.iter().sum();

    (p1, p2)
}

      • [^] # Re: Jour 7

        Posté par  . Évalué à 2 (+0/-0).

        Sans surprise, j'ai fait quelque chose de similaire, mais ce sont surtout les pièges qui étaient intéressants à relever.

        Première partie

        En premier lieu, si on raisonne en termes de tachyons et pas de chemins entiers, il faut résister à l'envie de travailler « en profondeur d'abord ». Il est tentant de dépiler un tachyon d'une pile, d'en ré-empiler deux juste derrière s'il traverse un splitter, et de refaire un tour de boucle tant que la pile n'est pas vide. Seulement, cela nous empêche de détecter la coalescence des tachyons émis simultanément à une même position (par deux splitters distincts distants d'exactement deux positions horizontales).

        Ensuite, la question était en fait « combien de fois le rayon a-t-il été divisé ? ». La subtilité était que si un tachyon voyage d'une position à l'autre, le « rayon », lui, est considéré unique du point de départ à celui d'arrivée. Et cela a de l'importance parce si deux tachyons se retrouvant à la même position s'écrasent mutuellement pour n'en former qu'un seul, ils peuvent aussi se suivre et faire en sorte qu'un même splitter soit franchi plusieurs fois.

        Par conséquent, puisque seul un splitter peut diviser un rayon, il fallait penser à faire le bilan du nombre de splitters atteints au moins une fois et pas seulement incrémenter un compteur chaque fois que l'on en franchit un.

        C'est important parce que j'obtiens respectivement 21 et 22 cas avec les données d'exemple, mais 13245 et 1607 avec les données réelles, ce qui est très différent… le premier nombre dépassant largement celui des splitters en jeu.

         Deuxième partie

        La tentation était grande d'écrire directement une fonction récursive et de la lancer à partir du point de départ. Bien sûr, comme chaque année, on fait face à une explosion combinatoire et c'est une bonne chose ici (c'est aussi l'un des rares intérêts à utiliser des langages lents).

        D'abord, il était tentant également d'écrire quelque chose comme :

        if splitter:
        return fn((x-1,y)) + fn((x+1,y)
        else:
        return fn((x,y+1))

        … en particulier parce que c'est propre et concis, mais cela encombre quand même la pile sur un trajet en ligne droite pour rien et il ne faut pas attendre ici du langage qu'il détecte et optimise automatiquement la récursivité terminale, donc il était intéressant de mettre une boucle quand même.

        Ensuite, la solution consiste surtout à ne pas recalculer plusieurs fois ce qui est déjà long à obtenir, donc à associer à chaque splitter le nombre de chemins qui en dérivent dès qu'on l'obtient et le renvoyer directement si on repasse dessus par la suite.

        Ce qui donne de mon côté (en faisant abstraction des inits) :

        hit_splitters  = {}

# Fonction récursive
def number_of_ways(tachyon):
    x,y = tachyon

    while True:
        tachyon = (x,y)

        if not ((0 <= x < width) and (0 <= y)):
            return 0

        if y >= height:
            return 1

        c = split_map[y][x]

        if c == "^":
            if tachyon not in hit_splitters:
                hit_splitters[tachyon] = number_of_ways((x-1,y)) \
                                       + number_of_ways((x+1,y))

            return hit_splitters[tachyon]

        if c not in ".S":
            print("Unknown character:", c)
            raise("Unknown character")

        y += 1

# Lancement des parcours
total = number_of_ways(point_de_depart)
print("Splitters atteints :", len(hit_splitters))
print(" Total des chemins :", total)

        Avec deux petites remarques :

        • la décomposition « x,y = tachyon » m'a conduit à une petite erreur d'inattention : lors de la rencontre avec un splitter, j'utilise la variable tachyon comme index pour hit_splitters mais à cause de la boucle décrite plus tôt, j'avais oublié qu'elle n'était plus forcément à jour. Donc j'enregistrais les points de départ de chaque tachyon et pas la position des splitters…
        • J'ai l'habitude d'écrire le total final après toutes les autres sorties mais dans ce cas précis, j'appelais la fonction directement depuis le print. Je ne comprenais donc pas pourquoi le nombre de splitters atteints, donné juste avant, était toujours nul… :-)

        Ce sont des broutilles, bien sûr, mais ça montre à quel point une erreur légère peut devenir critique en environnement sensible, aéronautique ou nucléaire par exemple, même lorsque l'on a de la pratique et que l'on porte du soin à son algorithme principal, et pourquoi les méthodes formelles et preuves de programmes sont utiles dans ce type de situation.

        C'est une des choses que j'aime le plus dans l'AoC. Même quand les exercices sont « simples », on reçoit régulièrement ce genre de piqûre de rappel alors qu'il est plus difficile d'y être confronté en contexte professionnel.

      • [^] # Re: Jour 7

        Posté par  . Évalué à 1 (+0/-0). Dernière modification le 07 décembre 2025 à 22:02.

        Finalement, j'ai essayé de vectoriser mon code pour la partie 1 via instruction SIMD.
        L'idée est de stocker chaque ligne sous forme de bitset de 192bits.
        On peut les extraire de manière très rapide en utilisant des instructions SIMD qui vont travailler sur les caractères par pack de 64.
        On stocke aussi un tableau de beams (i.e beams[i] = true s'il passe un beam à la position i.

        Cela donne le code suivant en oubliant les détails.

        pub fn part1(input: &str) -> u32 {
    let input = input.as_bytes();
    let mut beams = U192::new(0, 0, 0);
    beams.second |= 1 << (MID - 64);

    (2*WIDTH..input.len()).step_by(2*WIDTH).map(|line_start| {
        let splits = U192::from_slice(&input[line_start..line_start+WIDTH-1]);
        let beam_on_split = beams & splits;
        beams = (beams | beam_on_split.shift_left() | beam_on_split.shift_right()) & !splits;
        beam_on_split.count_ones()
    }).sum()
}

        Il n'y a au final pas tant de SIMD que ça mais plutôt un travail sur les bitsets.
        250 nanosecondes, en dessous de la microsecondes :)

    • [^] # Re: Jour 7

      Posté par  . Évalué à 2 (+0/-0).

      Première partie très simple, pour chaque line, à chaque fois qu'on split, incrémenter de 1.

      Seconde partie, je n'ai pas vu la technique de programmation dynamique que vous évoqués.

      J'ai vu un parcours de graphe.

      Par flemme de l'implémenter moi même, j'ai voulu le faire avec une lib. Grosse erreur, elle a tournée pendant des plombes et de retour de promenade, je l'ai killé (heureusement que c'est l'hiver et qu'on chauffe).

      J'ai finalement implémenté moi même et ça s'est bien passé. Pour éviter l'explosion combinatoire, j'ai utilisé un cache.

      • [^] # Re: Jour 7

        Posté par  . Évalué à 2 (+1/-0).

        Ca peut, en effet, être vu comme un algorithme sur un graphe.

        Ca consiste à compter le nombre de chemins dans un graphe orienté acyclique et ça se fait en temps linéaire.

        Je n'ai pas l'impression que networkx propose cet algorithme mais ça se fait aussi … par programmation dynamique :)

        • [^] # Re: Jour 7

          Posté par  . Évalué à 2 (+0/-0).

          Ca consiste à compter le nombre de chemins dans un graphe orienté acyclique

          Exactement

          et ça se fait en temps linéaire.

          Je n'ai pas l'impression que networkx propose cet algorithme

          Il propose all_simple_path(source, destination) et je voulais juste les compter mais du coup, ça explose en combinatoire.

          ça se fait aussi … par programmation dynamique :)

          Je suis tristement pas très familier de cette technique mais de ma compréhension, un algo récursif avec mise en cache, ça s'en rapproche grandement.

          • [^] # Re: Jour 7

            Posté par  . Évalué à 3 (+2/-0).

            Oui, la récursion avec cache, c'est assez similaire à la programmation dynamique.
            La différence c'est qu'en version récursive, on part du problème initial pour descendre dans l'arbre des appels récursifs alors qu'avec la programmation dynamique, on dérécursifie l'algorithme en partant des feuilles de l'arbre et en remontant à la racine (le problème initial).

            En général, un algorithme en programmation dynamique est un peu plus rapide que sa version récursive avec cache (car pas de récursion et on utilise en général un tableau dont l'accès est plus rapide qu'un cache qui est en général implémenté par un hashset).
            C'est aussi parfois beaucoup plus économe en mémoire.

    • [^] # Re: Jour 7

      Posté par  (Mastodon) . Évalué à 2 (+0/-0). Dernière modification le 09 décembre 2025 à 19:18.

      Je ne crois pas avoir spécialement utilisé mon cerveau pour cet exercice, un code sur smartphone, peu lisible, mais efficace.
      Je crois avoir été naïf en première approche, mais la naïveté ici est explosive : on ne peut pas compter les 357 525 737 893 560 rayons de l'exercice 2 de façon indépendante.

      data = sys.stdin.read().strip().splitlines()

w,h=len(data[0]),len(data)
map="".join(data)
b={map.index("S")}   # exercice 1
c={map.index("S"):1} # exercice 2: 1 seul rayon au départ

ex1 = 0
for _ in range(h-1):
    n={i+w for i in b if map[i+w]=="."} # ligne droite
    s={i+w for i in b if map[i+w]=="^"} # split
    ex1+=len(s)
    # Tous les endroits où on a des rayons, pour les 2 exercices
    b=n.union({i+1 for i in s},{i-1 for i in s}) # ex1
    d={i:c[i-w] if i in n else 0 for i in b} # On reprend les rayons directs
    for i in s:  # On ajoute les rayons splittés
        d[i-1]+=c[i-w]
        d[i+1]+=c[i-w]
    c=d

ex2=sum(c.values())
      • Yth.

  • # Jour 8

    Posté par  . Évalué à 3 (+1/-0).

    J'étais ravi d'ouvrir un problème en 3D, ça fait des jolies illustrations.

    J'ai trouvé rapidement l'algo mais j'ai perdu énormément de temps sur:

    1/ une mauvaise lecture du calcul qu'il fallait produire pour la première partie ; my bad

    2/ le fait qu'il fallait compter comme un connexion le fait de ne rien faire :/
    à force de tâtonner, j'ai finit par incrémenter dans tous les cas pour voir et je suis tombé sur la solution ; pas agréable

    La deuxième partie après cela était triviale.

    • [^] # Re: Jour 8

      Posté par  . Évalué à 3 (+2/-0).

      J'ai trouvé ce problème assez intéressant.

      Mon défi était d'avoir un temps d'exécution inférieur à 1ms.

      Première approche, on calcule toutes les paires de sommets et leur distance euclidienne (en fait, on a pas besoin de faire la racine carrée qui est coûteuse en temps).
      Ensuite, on fait un algorithme similaire à Kruskal.
      https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal

      On utilise une structure union-find
      https://fr.wikipedia.org/wiki/Union-find
      et on rajoute progressivement chaque arête en faisant un join sur les deux extrémités de l'arête. Pour la partie 2, on a besoin de trier les arêtes ce qui est vraiment le goulot d'étranglement de l'algo. Pour la partie 1, on a juste besoin de garantir que les 1000 premières arêtes aient la distance euclidienne la plus petite. En Rust, cela peut être fait avec la méthode select_unstable(1000) et c'est beaucoup plus efficace que trier le tableau. Avec cette approche, 2ms pour la partie 1 et 15ms pour la partie 2.

      Deuxième approche uniquement pour la partie 2.
      On cherche un arbre couvrant de poids minimum mais cette fois, au lieu de se baser sur Kruskal qui est en temps O(m log n) = O(n² log n) comme le graphe est dense, on se base sur l'algorithme de Prim qui est en temps O(n²).https://fr.wikipedia.org/wiki/Algorithme_de_Prim
      Du coup, on réduit le temps à 3ms.

      Dernière approche, on revient sur Kruskal mais cette fois, on ne va pas considérer toutes les arêtes.
      On va diviser l'espace en blocs 8x8x8 et pour chaque sommet, on va regarder les sommets qui sont dans le même bloc ou dans un bloc voisin (diagonal compris).
      On passe de (1000*999) / 2 ~ 500_000 paires d'arêtes à environ 10000.
      En appliquant le même principe que la première méthode, on obtient un temps d'exécution de 650 microsecondes pour les deux parties.
      Ca ne marche pas tout le temps, il ne faut pas qu'il y ait de gros trous dans l'espace de points mais ça semble être le cas dans les différentes inputs car les points sont uniformément répartis.

    • [^] # Re: Jour 8

      Posté par  . Évalué à 2 (+0/-0).

      Beaucoup moins académique que Guillaume, très itératif, les deux parties en 22 lignes:

      boxes = [tuple(map(int, line.split(","))) for line in open(0).read().strip().split('\n')]
clusters = dict()
for c, (_,(i,j)) in enumerate(
    sorted(((x-l)**2+(y-m)**2+(z-n)**2, (i,i+1+j))
        for i, (x,y,z) in enumerate(boxes)
            for j, (l,m,n) in enumerate(boxes[i+1:]))):
    icl = [[k for (k,v) in clusters.items() if i in v] or ["ALONE"]][0][0]
    jcl = [[k for (k,v) in clusters.items() if j in v] or ["ALONE"]][0][0]
    match (icl == "ALONE", jcl == "ALONE", icl == jcl):
        case (False, False, False): # both belongs to different clusters, merge clusters
            clusters[f'{i}_{j}'] = clusters[icl] | clusters[jcl]
            del clusters[icl]
            del clusters[jcl]
        case (False, True, _):
            clusters[icl].add(j)
        case (True, False, _):
            clusters[jcl].add(i)
        case (True, True, _): # both out of clusters, create a new cluster with them
            clusters[f'{i}_{j}'] = {i, j}
        # else (False, False, True), i and j are in the same cluster
    if c == 1000:
        s = sorted(map(len, clusters.values()))
        print(s[-1]*s[-2]*s[-3])
    if c > 1000 and len(clusters) == 1:
        print(boxes[i][0]*boxes[j][0]) # 5267 conns
        break

    • [^] # Re: Jour 8

      Posté par  . Évalué à 3 (+1/-0).

      ça fait des jolies illustrations

      toutes les prises connectées, en 3D, dans openscad

    • [^] # Re: Jour 8

      Posté par  . Évalué à 2 (+1/-0).

      J'aurai bien traine aussi ce soir pour plier le bouzin, en partie pour cause de boulettes a traquer, puis pour polish ensuite et reiterer sur la partie boulette.
      Au final, rien de bien original (mais promis, j'ai pas copie):

      from __future__ import annotations
from functools import reduce
from itertools import combinations, count
from operator import mul
from typing import NamedTuple


class SpaceCoord(NamedTuple):
    x: int
    y: int
    z: int

    def square_distance(self, other: SpaceCoord) -> int:
        return pow(other.x - self.x, 2) + pow(other.y - self.y, 2) + pow(other.z - self.z, 2)

    @classmethod
    def from_data(cls, data: str) -> SpaceCoord:
        return cls(*map(int, data.split(',')))

class Junction:
    def __init__(self, data: list[str]) -> None:
        self.boxes = [SpaceCoord.from_data(line) for line in data]
        self.ordered_pairs = sorted(combinations(self.boxes, 2), key=lambda t: t[0].square_distance(t[1]))

    def _join(self, steps: int|None = None) -> tuple[list[int],tuple[SpaceCoord,SpaceCoord]]:
        groups: list[list[SpaceCoord]] = []
        length = len(self.boxes)

        def in_group(box: SpaceCoord) -> int|None:
            for i, g in enumerate(groups):
                if box in g:
                    return i
            return None

        for i in count():
            b1, b2 = self.ordered_pairs[i]
            g1 = in_group(b1)
            g2 = in_group(b2)
            match g1, g2:
                case None, None:
                    groups.append([b1, b2])
                case None, int():
                    groups[g2].append(b1)
                case int(), None:
                    groups[g1].append(b2)
                case _:
                    if g2 != g1:
                        groups[g1] += groups[g2]
                        groups.remove(groups[g2])
            if steps and i == steps -1:
                break
            elif len(groups) == 1 and len(groups[0]) == length:
                break
        return ([len(g) for g in groups], (b1, b2)) # pyright: ignore[reportPossiblyUnboundVariable]

    def join_steps(self, steps: int) -> list[int]:
        return sorted(self._join(steps)[0], reverse=True)

    def join_all(self) -> tuple[SpaceCoord,SpaceCoord]:
        return self._join()[1]

def exo1(data: list[str], steps: int) -> int:
    lengths = Junction(data).join_steps(steps)
    return reduce(mul, lengths[:3])

def exo2(data: list[str]) -> int:
    b1, b2 = Junction(data).join_all()
    return b1.x * b2.x

      ++
      Gi)

    • [^] # Re: Jour 8

      Posté par  (Mastodon) . Évalué à 2 (+0/-0).

      Ici, j'ai réfléchi au fait que si on a deux boîtes de dérivation qui ne sont pas reliées par le fil le plus petit existant, alors on peut raccourcir le réseau total.
      Donc il apparaît clair qu'il faut ajouter les liens du plus petit au plus grand, jusqu'à compléter l'exercice.

      J'ai un peu lutté sur la représentation des données, je voulais être intelligent, mais je me suis retrouvé avec des cas où des sous-graphes étaient encore référencés.
      Là, j'aurais été plus à l'aise en C, à manipuler proprement des pointeurs, pour modifier directement les données à plusieurs endroits à la fois.
      Bon, je le fais aussi en Python, mais j'ai des trucs qui m'ont embêté, et j'ai perdu l'élégance que j'espérais avoir.

      Au final, j'ai quand même un truc pas super optimisé qui s'exécute en 3,5s, c'est très laid.
      Et comme ça prend seulement 1s en PyPy, je sais que j'ai fait du mauvais travail :D

      from dataclasses import dataclass
import math
import itertools

MAX=1000 # 10 pour l'exemple
data = sys.stdin.read().strip().splitlines()

@dataclass(frozen=True)
class Box:
    x:int
    y:int
    z:int
    def __mul__(self, x):  # distance euclidienne: a*b
        return (self.x-x.x)**2+(self.y-x.y)**2+(self.z-x.z)**2
boxes={
    Box(*(int(_) for _ in l.split(",")))
    for l in data
}
dist=sorted({
    (a*b,frozenset((a,b)))
    for a,b in itertools.product(boxes,boxes)
    if b!=a
})
circuits={b:{b} for b in boxes}

for i,(d,(a,b)) in enumerate(dist):
    if b not in circuits[a]:
        c=circuits[a].union(circuits[b])
        if len(c)==len(boxes):
            break  # On a fini
        for _ in c:
            circuits[_]=c
    if i==MAX-1:
        ex1={(len(_),frozenset(_)) for _ in circuits.values()}

ex1=math.prod(sorted(l for l,_ in ex1)[-3:])
ex2=a.x*b.x

  • # jour 9

    Posté par  . Évalué à 2 (+0/-0). Dernière modification le 09 décembre 2025 à 11:25.

    Partie 1 triviale.

    Partie 2, j'ai triché en ayant recours à la bibliothèque shapely qui permet de faire, entre autres, des opérations sur les polygones.

    Le code dans le commentaire ci-dessous que vous pouvez plier ([-]) pour éviter le spoil.

    • [^] # Re: jour 9

      Posté par  . Évalué à 2 (+0/-0). Dernière modification le 09 décembre 2025 à 11:54.

      Partie 1 en 2 lignes

      from itertools import product as prod
P = [tuple(map(int,line.split(","))) for line in open(0).read().strip().split('\n')]
print(max((1+abs(a-c))*(1+abs(b-d)) for (a,b),(c,d) in prod(P,P)))

      Au moins deux fois trop de calculs, mais l'optimisation ne valait pas la peine, ça reste très rapide.

      Partie 1 et 2

      from shapely.geometry.polygon import Polygon
from shapely.geometry import Point
from itertools import product as prod
P = [tuple(map(int,line.split(","))) for line in open(0).read().strip().split('\n')]
shape = Polygon(P)
ans1 = ans2 = 0
for (a,b),(c,d) in prod(P,P):
    if (a,b)>=(c,d):  # avoid comapring a pair twice
        continue
    area = (1+abs(a-c))*(1+abs(b-d))
    ans1 = max(ans1, area)
    if area <= ans2:  # avoid more computation if not a new max
        continue
    rect = Polygon([(a,b),(a,d),(c,d),(c,b)])
    if shape.contains(rect):
        ans2 = area
print(ans1, ans2)

      Pas trop d'intérêt à compacter le code puisque je n'ai pas implémenté le gros morceau qu'est le contains.

      • [^] # Re: jour 9

        Posté par  (Mastodon) . Évalué à 3 (+1/-0).

        Ah, c'est bien ça, shapely.
        Parce que bon, j'ai salement polioté sur cette partie, et au final j'ai une solution en faisant une hypothèse de travail et 9 minutes de calculs avec PyPy.
        Il faut beaucoup trop réfléchir pour modéliser le bidule proprement, savoir ce qui est dedans et dehors, dépatouiller les sous-ensembles etc.

        Et mon code aurait foiré s'il y avait eu des « crochets » du genre ça, en considérant le rectangle entre les deux O, la case avec un _ rend le rectangle impossible, mais n'est pas « vue » par mon algo :

        ######.
#....#.
#O##.#.
##_#.O#
...#..#
.###..#
.######

        Bref, c'est moche, je montre pas, mais dans l'idée, je liste toutes les arêtes, puis pour chaque x possible (0 à 100000 en gros) on regarde le y maximal et minimal, et on fait idem pour les les y possible avec les x maximal et minimal.
        L'hypothèse ici c'est qu'on voit toutes les arêtes depuis l'extérieur de la surface, nord, sud, est ouest, on a soit une arête dans l'axe et on voit une seule case, soit elle est entièrement visible face à nous.

        Là dessus, pour chaque rectangle possible, triés par superficie décroissante, on regarde si les sommets sont « à l'intérieur », c'est à dire si pour le x du sommet, le y est entre le max et le min, et si pour le y du sommet le x est entre le min et le max.
        Si c'est le cas, on pousse plus loin, et on teste tous les bords du rectangle (nous avons ici une optimisation d'échelle, permettant d'éliminer très rapidement la majorité des rectangles, et de se concentrer sur ceux qui ont un potentiel !).
        Dès qu'on est 100% OK, on a le bon résultat, et ça fonctionne.

        C'est brutal, je ne suis pas sûr de pourquoi ça prend tant de temps, je suppose que je pourrais optimiser mon calcul initial des bornes, j'ai utiliser un cache de fonction, puis j'ai forcé le remplissage du cache au début pour voir pourquoi c'était long.
        Et la version Python (non PyPy donc) bloque au calcul du bon rectangle.

        D'expérience, si la version Python est plus lente que la version PyPy, c'est qu'on a fait de la boue…

        Une bonne optimisation serait de simplifier le terrain par tous les x et y existant dans les coordonnées.
        Dans l'exemple on a x dans [2, 7, 9, 11] et y dans [1, 3, 5, 7], et en réalité le « terrain » fait 4x4 et non 11x7. Dans le cas réel, on a un terrain de moins de 250x250 (496 lignes et chaque coordonnées y est normalement au moins représentée deux fois), et là c'est plutôt facile de parcourir un peu en force sur une terrain minuscule (60 000 cases contre 10 milliards…).
        Mais ça demande de bien réfléchir à ne pas tomber sur des effets de bords.

        Et ceci m'a - enfin - amené à une optimisation intermédiaire : je reprend exactement mon algo, mais après avoir testé les sommets des différents rectangles, au lieu de tester les côtés entiers, je ne teste que les points dont les coordonnées sont dans cette fameuse liste réduite de ~250 x et ~250 y.
        Je tombe à 3s avec PyPy, ce qui prouve qu'on doit pouvoir optimiser pour aller à une vitesse raisonnable.

        Mais…
        Mais est-ce que ça répond au problème dans le cas général ? Est-ce que j'ai un biais de chez-moi-ça-marche ? Parce que je peux décrire des situations où ça ne fonctionne pas, typiquement mon exemple plus haut. J'ai quand même une simplification qui n'est absolument pas prévue par l'énoncé du problème.

        Bref, shapely c'est officiellement une bonne solution…

        • Yth, et je ne parle pas de la partie 1, triviale.

    • [^] # Re: jour 9

      Posté par  . Évalué à 2 (+1/-0). Dernière modification le 09 décembre 2025 à 17:10.

      Pour ma part, j'ai essayé de ne pas utiliser de librairies externes même si c'est très pratique.
      La partie 1 est facile.
      J'ai mis beaucoup de temps à débugguer la partie 2 à cause de bugs stupides.

      Voici l'idée pour la partie 2.
      Bien sûr, on ne peut pas représenter la grille des points de l'input car elle est beaucoup trop grande.
      Ce qu'on va faire, c'est qu'on va utiliser une grille plus petite.
      On trie les coordonnées x et y par ordre croissant et dans la grille au lieu d'utiliser la position (x, y), on va utiliser la position (i, j) où i est la position de x dans son tableau trié et j est la position de y dans son tableau trié.
      Ce qui nous permet d'avoir une grille de taille environ 250x250, ce qui est raisonnable.
      Ensuite, on trace des lignes dans la grille en fonction des segments données en input et on remplit le polygone en utilisant le classique flood-filling.

      Maintenant, il y a une astuce pour déterminer en temps constant si un rectangle est contenu dans le polygone.
      L'idée est de calculer, par programmation dynamique, un tableau empty_table qui pour chaque (x, y) donne combien de cases vides contient le rectangle (0, 0) -- (x, y).
      A partir de là, on peut déterminer déterminer le nombre de cellules vides dans un rectangle (x1, y1, x2, y2) en faisant le calcul
      empty_table[x2, y2] - empty_table[x1-1, y2] - empty_table[x2, y1-1] + empty_table[x1-1, y1-1].
      Si le nombre de cellules vides est 0, cela signifie que le rectangle est contenu dans le polygone.

      Ca donne un algorithme en temps O(n²) et un temps d'exécution de 650 microsecondes pour les deux parties.
      Je ne fais pas de supposition sur l'input, on peut sans doute faire mieux en en faisant.

      • [^] # Re: jour 9

        Posté par  (site web personnel) . Évalué à 3 (+0/-0). Dernière modification le 09 décembre 2025 à 18:03.

        Pas encore fini de coder la partie 2, mais je pars sur des idées semblables :

        • pour chaque position (x, y) mentionnée dans le fichier d'entrée, je considère que les abscisses x et x + 1 seront utiles, et que les ordonnées y et y + 1 seront utiles ;
        • je considère également comme utiles les abscisses min(x) - 1 et max(x) + 1 et les ordonnées min(y) - 1 et max(y) + 1.

        Le premier point, c'est parce que, dans ma représentation, chaque case du tableau réduit est censée représenter fidèlement tout l’intervalle jusqu'à la case suivante exclue.

        Le second point, c'est que peindre l'intérieur d'une courbe fermée par inondation, ce n'est facile qu'à condition de partir d'un point dont on sait qu'il est à l'intérieur, ce que je ne sais pas faire. En revanche, peindre l'extérieur, c'est pareil à deux conditions :

        • partir d'un point dont on sait qu'il est à l'extérieur, ce qui est facile si on a agrandi la zone d'au moins une case d'un côté ou d'un autre ;
        • que l'extérieur soit connexe, ce qui est garanti si on a étendu la zone de tous les côtés.

        Bref, peindre l'intérieur de quelque chose, je ne sais pas faire. Peindre l'extérieur, je sais faire : il faut ajouter une bordure vierge et inonder depuis un point de cette bordure.

        • [^] # Re: jour 9

          Posté par  . Évalué à 1 (+0/-0).

          que l'extérieur soit connexe, ce qui est garanti si on a étendu la zone de tous les côtés.

          Oui, c'est ce que je fais.
          Et en effet, peindre l'intérieur, c'est compliqué même si on connait un point à l'intérieur.

      • [^] # Re: jour 9

        Posté par  (Mastodon) . Évalué à 2 (+0/-0).

        Je me pose des questions sur un truc comme ça :

        #######    ┌─────┐
#.....#    │.....│
#.###.# => │.┌─┐.│
#.#.#.#    │.│.│.│
###.###    └─┘.└─┘

        Qui se « simplifie » en ne considérant que les coordonnées des 8 sommets, en ça :

        ####    ┌──┐
#### => │┌┐│
####    └┘└┘

        Et nous dis assez facilement que le rectangle complet est valide alors que pas vraiment, en vrai.

        • Yth.

        • [^] # Re: jour 9

          Posté par  . Évalué à 1 (+0/-0).

          Oui, tu as raison, je n'avais pas pensé à ce cas de figure.
          J'ai été chanceux sur l'input.
          Va falloir que je corrige mon algo si je veux qu'il soit correct dans le cas général.
          Je pense qu'ajouter les points (x+1, y) et (x, y+1) doit suffire à régler le problème.

    • [^] # Re: jour 9

      Posté par  . Évalué à 2 (+0/-0).

      Je me doutais un peu que l'input avait un pattern particulier qui devrait permettre d'être plus efficace qu'avec un input plus aléatoire. Qqun a senti la même chose et l'a fait.

      Voici annimation de l'input

      • [^] # Re: jour 9

        Posté par  . Évalué à 1 (+0/-0).

        Je ne l'ai pas fait mais je connais des gens qui arrivent à répondre au problème (sur 5 inputs différentes) en ne lisant que 8 lignes bien choisies de l'input.
        La réponse se fait en quelques nanosecondes.

  • # Jour 10

    Posté par  (site web personnel) . Évalué à 3 (+0/-0). Dernière modification le 10 décembre 2025 à 13:31.

    Le jour 10 me fait furieusement penser à de l'arithmétique, et plus précisément à de l'arithmétique des polynômes.

    Pour la première partie, on n'a pas besoin de telles considérations. Mais pour la seconde, c'est déjà plus flagrant. On a des boutons dont chacun augmente des coefficients de joltage précis. Ça rappelle des additions de nombres constitués de chiffres illimités sans notion de retenue : c'est précisément ça, l'arithmétique des polynômes.

    Après, c'est bien beau, mais ça n'aide pas à résoudre. Si les boutons fournis constituaient une base, on pourrait faire de la factorisation sachant qu'il y aurait un seul résultat possible. Sauf que ça ne constitue justement pas une base. Est-ce qu'on peut faire mieux que tâtonner ? Forcément, sinon on ne pourrait pas finir, mais pour le moment, ça m'échappe. :-)

    • [^] # Re: Jour 10

      Posté par  (site web personnel) . Évalué à 3 (+0/-0).

      Je ne sais pas pourquoi j'ai pensé tout de suite à l'arithmétique des polynômes. On peut aussi bien voir ça comme un bête espace vectoriel, ce qui n'avance pas plus le schmilblick.

    • [^] # Re: Jour 10

      Posté par  . Évalué à 1 (+0/-0).

      Je ne vois pas le rapport avec les polynômes mais avec l'espace vectoriel je le vois clairement.

      Le problème consiste à résoudre un système d'équations linéaire MX = B
      où
      - X est le vecteur inconnu que l'on cherche, c'est à dire X[i] est le nombre de fois qu'on a appuyé sur le bouton i.
      - B est le vecteur des "joltage levels"
      - M est une matrice telle M[(i, j)] = 1 si le bouton i active le compteur j et 0 sinon.

      On veut que les valeurs de X soient entière et positives et on veut minimiser la somme des valeurs de X.

      On peut résoudre le système d'équations en utilisant par exemple le pivot de Gauss.
      Le problème est que la solution obtenue ne contient pas forcément des valeurs positives et entières.

      Du coup, je suis passé par un solveur de programmation linéaire en nombre entiers.
      Mais je suis en train de travailler sur une solution qui ne nécessite pas de librairies externes. En espérant que ça marche …

    • [^] # Re: Jour 10

      Posté par  . Évalué à 2 (+1/-0).

      Pour la partie 1, il faut remarquer que l'ordre d'appui sur les boutons importe peu et qu'il ne sert à rien d'appuyer deux fois sur le même bouton.

      Donc on peut tout encoder sous forme de bitset et faire un parcours en largeur sur les configurations possibles.

      J'ai pris beaucoup de temps mais je suis finalement arrivé à avoir une solution pour la partie 2 sans utiliser de solveurs externes (j'ai d'abord utilisé Z3).

      L'idée est qu'il faut résoudre un système d'équations linéaires comme dit dans un post plus haut en cherchant une solution avec des valeurs entières positives et qui minimisent la somme totale.

      Le problème, c'est que la matrice n'est forcément carrée, pas forcément invertible donc il peut y avoir une infinité de solutions.
      Le pivot de Gauss peut nous donner une solution mais ce n'est pas forcément la bonne.

      Imaginons qu'on est ce système d'équations

      1 1 1 0 1 1 0 1 1 0 0 0 55
1 1 0 1 0 1 0 0 0 0 0 0 42
1 0 1 1 0 0 1 0 0 0 1 1 71
1 0 1 1 0 0 1 0 1 1 0 1 79
1 0 1 1 0 1 1 0 0 0 0 1 70
0 0 1 1 0 1 0 1 0 0 0 0 41
1 1 1 0 1 0 1 0 0 1 0 1 60
0 0 1 0 1 1 0 0 0 1 0 1 45
1 0 1 1 0 0 1 1 0 1 0 0 58
0 1 0 0 0 1 1 0 0 1 0 1 53

      On va appliquer le pivot de gauss sur cette matrice et obtenir la matrice "échelonnée":

      1  1  1  0  1  1  0  1  1  0  0  0  55 
0 -1  0  1 -1 -1  1 -1 -1  0  1  1  16 
0  0 -1  1 -1  0  0 -1 -1  0  0  0 -13 
0  0  0 -2  1 -1  0  0  1  0  0  0 -28 
0  0  0  0  1  1  0 -2 -1  2  0  2  36 
0  0  0  0  0 -1  1 -1 -1  1  0  1  5 
0  0  0  0  0  0  1 -1 -1  1 -1  1  4 
0  0  0  0  0  0  0 -1  0 -1  1  1  13 
0  0  0  0  0  0  0  0 -1 -1  1  0  -8 
0  0  0  0  0  0  0  0  0  2 -8 -2 -114

      Si on oublie la dernière colonne, on dit qu'une colonne est pivot si l'élément non nul le plus bas de cette colonne a la propriété suivante, il y a que des 0 à gauche et en dessous.
      Donc, on voit ici que toutes les colonnes sont pivots sauf les deux avant-dernières.

      L'algorithme se base sur le fait qu'il y a peu de colonnes non pivots.

      Si la matrice n'a aucune colonne non pivot alors il existe une solution et donc on n'a pas besoin de cherche plus loin.
      Sinon, on va partir d'en bas à droite et affectant les valeurs de la solution de droite à gauche.
      Si une colonne j est pivot et que les variables à droite ont déjà affectés alors il n'y a qu'une seule valeur possible pour la variable x_j.

      Par contre, si la colonne j n'est pas pivot, il peut y avoir plusieurs valeurs affectables à la variable x_j. On va donc affecter à cette variable, une valeur entre 0 et une certaine limite et faire du backtracking.
      Comme il y a au plus 3 colonnes non pivots dans chaque matrice du jeu de données, il n'y pas une grande profondeur de backtracking.

      Pour la limite, j'ai choisi une valeur qui allait bien pour le jeu de données, à savoir 200 si il y a au plus de colonnes non pivots et 30 si il y a 3 colonnes non pivots.

      En parallélisant, le temps d'exécution est 4ms.

    • [^] # Re: Jour 10

      Posté par  (site web personnel) . Évalué à 4 (+1/-0). Dernière modification le 11 décembre 2025 à 18:05.

      Pfiou, j'en suis venu à bout, mais pas tout seul. Ça a fini par me rappeler des notions d'optimisation linéaire, du coup j'ai été rafraîchir mes connaissances sur le sujet.

      Un problème d'optimisation linéaire est défini par :

      • une fonction de coût (en fait un vecteur, dont on prend le produit scalaire avec chaque solution possible) ;
      • des contraintes d'inégalité sur les variables, individuellement ou collectivement (une matrice et un vecteur borne supérieure) ;
      • des contraintes d'égalité collectives sur les variables (une matrice et un vecteur résultat).

      Il se trouve que ça colle plutôt bien avec notre problème :

      • le coût, qu'on cherche à minimiser, c'est la somme des pressions sur chaque bouton, autrement dit un vecteur dont chaque coordonnée vaut un ;
      • les contraintes d'inégalité individuelles, c'est plus grand que zéro et moins grand que le plus petit joltage cible piloté par le bouton considéré ;
      • la contrainte d'égalité collective, c'est la matrice de pilotage et les joltages cibles.

      Avec scipy.optimize.linprog, ça marche super bien. À un petit détail près : ça sort des résultats qui ne sont pas toujours entiers. Mais ça tombe bien, il a aussi une option pour définir des contraintes d'entièreté pour les variable. Et hop, on a le résultat cherché.

      Clairement, j'aurais été incapable de résoudre ça sans recourir à un optimiseur linéaire. Mais je reste satisfait d'avoir d'une part déterminé que ça correspondait à un problème d'optimisation linéaire et d'avoir correctement spécifié tout ça pour l'entrer dans ledit solveur.

    • [^] # Re: Jour 10

      Posté par  (Mastodon) . Évalué à 3 (+1/-0).

      Ben j'ai fini par bricoler un truc qui fonctionne, mais bigre, j'ai pas les maths bien à plat sur ce problème.

      Au début j'avais cherché les boutons avec le moins de choix possibles.
      Exemple :

      [1, 0, 0, 1, 1, 1, 1, 1, 1, 0] = 55
[1, 0, 0, 0, 0, 1, 0, 1, 1, 0] = 25
[1, 1, 1, 0, 1, 1, 1, 0, 0, 1] = 58
[1, 1, 0, 1, 0, 0, 0, 1, 0, 1] = 54
[1, 0, 0, 1, 1, 1, 1, 1, 0, 0] = 55
[1, 1, 1, 1, 0, 1, 1, 0, 0, 0] = 53
[0, 0, 1, 1, 1, 0, 1, 0, 0, 1] = 44
[0, 1, 1, 1, 1, 0, 0, 1, 0, 0] = 43
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0] = 42

      On voit que pour obtenir le résultat de la ligne 2, 25, on a quatre boutons possibles, notés a, b, c, d. On a a+b+c+d=25, ça fait pas beaucoup de combinaisons, ici 3276, calculées en python avec itertools.combinations_with_replacement([a,b,c,d],25).
      Et après je brute-force un peu en espérant avoir suffisamment réduit le champs des possibles.
      Ça simplifie suffisamment le problème pour permettre de résoudre la plupart des problèmes parfois en assez longtemps, mais clairement pas tous, j'ai oublié mon programme deux jours, et j'ai un problème qui tournait encore.

      Donc là il faut simplifier la matrice. Je fais avec une diagonale, en gardant des nombres entiers positifs, donc je n'ai plus uniquement des 1 dedans.
      Je réduis à ça, en réorganisant les lignes, mais l'ordre des boutons n'a pas d'importance, on a juste besoin du nombre total de boutons appuyés :

      [24,  0, 0,  0,  0,  0,  0, 0, 0,  60] =  864
[ 0, 48, 0,  0,  0,  0,  0, 0, 0, -36] =  168
[ 0,  0, 4,  0,  0,  0,  0, 0, 0,   4] =   56
[ 0,  0, 0, 24,  0,  0,  0, 0, 0, -12] =  144
[ 0,  0, 0,  0, 24,  0,  0, 0, 0,  12] =  264
[ 0,  0, 0,  0,  0, 24,  0, 0, 0, -54] = -468
[ 0,  0, 0,  0,  0,  0, 12, 0, 0,   0] =  156
[ 0,  0, 0,  0,  0,  0,  0, 4, 0,  -1] =   34
[ 0,  0, 0,  0,  0,  0,  0, 0, 1,   0] =    0

      Ensuite, bah j'ai ma dernière colonne qui casse les pieds, on voit un maximum à 864/60, ou 56/4, ou 264/12, et un minimum à -468/-54, donc une valeur entre 9 et 14.
      Alors on remplace, on regarde si notre solution devenue triviale (matrice diagonale, ça va :)) est entière, on jette, et on calcule la solution avec le minimum de boutons appuyés.
      Facile.

      Parfois, on n'a même pas de dernière colonne et la matrice est diagonale directement, super.
      Et puis parfois on en a 2 ou 3, et ça devient casse-pied.
      Les calculs de maxima et minima ne tiennent plus, puisque les boutons rebelles influent les uns sur les autres.
      Au final j'ai énuméré toutes les possibilités d'appuyer de 0 à 200 fois sur chacun des derniers boutons et résolu, comme au dessus, solution entière, que des valeurs positives, et on prend la plus petite.

      Le tout optimisé comme un projet Microsoft, ça prend 2 minutes 36s, et le résultat est valide.
      Je n'arrive déjà plus à relire mon code, et ça sent qu'il faudrait utiliser une bibliothèque d'algèbre linéaire, au moins pour les simplifications, et manipulations de lignes et colonnes, un numpy avec des matrices propres serait probablement une grande avancée dans la lisibilité et les performances.

      À noter qu'avec un solveur, dans l'exemple au dessus, il suffit de rajouter une ligne [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] = (valeur de 9 à 14), et de lui dire « c'est bon, c'est carré, alors c'est quoi ma solution ? », de vérifier qu'elle est entière et de passer à la suite.
      Mais bon, la résolution d'une matrice diagonale, c'est pas vraiment le plus difficile !

      Bref, j'aurais bien pataugé dans ce problème, pour au final ne pas avoir trouvé de truc sensiblement différent des autres, moins bien fait et en plus longtemps.
      Officiellement la cuvée 2025 n'est pas la meilleure pour moi ;)

      • Yth.

      • [^] # Re: Jour 10

        Posté par  . Évalué à 1 (+0/-0).

        Perso, j'ai utilisé Z3. Tu poses juste les équations et tu indiques le type d'optimisation que tu veux.
        çà m'a pris moins d'1h une fois que j'ai compris qu'il fallait que je pose çà sous forme d'équation.

        Tu obtiens le résultat très rapidement.

        • [^] # Re: Jour 10

          Posté par  (Mastodon) . Évalué à 2 (+0/-0).

          Ouais, ça va plus vite.
          Jaime bien me creuser la tête sur l'advent of code, un minimum de libs externes, ou de trucs tout faits.

          D'ailleurs on doit pouvoir remarquer que plus on appuie sur les boutons rebelles, moins on appuie sur plein d'autres boutons.
          Dans un cas avec une seule colonne en trop, on doit pouvoir prouver que la solution maximise la valeur pour cette colonne, en respectant la règle de de n'avoir que des solutions entières.
          Donc parcourir depuis le maximum possible en descendant, et s'arrêter dès qu'on a une solution.
          Mais ça accélère le cas le plus simple, rien de bien utile en somme.

          • Yth.

          • [^] # Re: Jour 10

            Posté par  . Évalué à 1 (+0/-0).

            Après, si tu veux chercher l'optimum à la main. Tu peux envisager un "Recuis simulé".
            https://fr.wikipedia.org/wiki/Recuit_simul%C3%A9

            Mais dans ce cas , tu n'es peut être pas obligé de simplifier ta matrice (sauf peut être pour des raison de performances)

            En gros, à chaque tour de boucle , tu fais varié aléatoirement le nombre de pression d'un des bouttons & petit à petit , tu réduis le seuil de tes
            variations

            La difficulté de cette algo, c'est d'exprimer le choix de l'aléatoire voisin car il faut envisager que tu diminues un au profit d'un autre ce qui peut être lourd à caler.

            • [^] # Re: Jour 10

              Posté par  . Évalué à 1 (+0/-0). Dernière modification le 15 décembre 2025 à 19:17.

              Je voulais tester pour m'amuser le recuis simulé , mais çà ne marche pas. Définitivement une mauvaise idée :-p

  • # Jour 11

    Posté par  . Évalué à 2 (+0/-0). Dernière modification le 11 décembre 2025 à 16:16.

    Bonne tranche de rigolade aujourd'hui. On est sur du parcours de graphes.

    Première partie implémentée en deux minutes, sans erreurs, directement sur l'input et hop une étoile. On commence à être rôdé.

    Partie deux, sur ce bon élan, j'adapte ma solution pour partir d'un autre nœud et ne compter que les chemins qui contiennent les nœuds imposés. Trivial. Je vais faire la journée 11 en moins de dix minutes.

    Sauf que le script ne me rend pas la main. Et là, je me dis que je me suis fait avoir.
    Je trace le graphe avec Graphviz et je vois l'étendue des dégâts. Le nœud de départ de la première partie est tout près du nœud de sortie. Mais pour la seconde partie, il est très très loin. Donc la combinatoire explose.

    Je tente une mise en cache, mais ça ne semble rien améliorer.

    J'ai donc exploité la structure du graphe proposé qui 1/ est acyclique, 2/ présente des "couches". J'ai donc calculé un graph plus simple avec seulement les nœuds qui matérialisent les couches et le cout pour passer de l'un à l'autre. Puis lancé le calcul du nombre de chemins sur ce graphe plus simple (18 nœuds versus 644).

    Forcément, ça m'a pris une bonne paire d'heures.

    Je ne sais pas s'il y avait plus malin à faire ; je lirai avec plaisir d'autres solutions.

    • [^] # Re: Jour 11

      Posté par  (site web personnel) . Évalué à 3 (+0/-0).

      Pour ma part, je n'ai même pas considéré les chemins possibles, seulement leur nombre. Le nombre de chemins possibles pour aller de A à B, c'est :

      • un seul si A égale B ;
      • la somme du nombre de chemins de chaque fils de A à B.

      Évidemment, ce genre de truc part en récursion infinie s'il n'existe pas de chemin ou s'il y a une boucle. Mais les données d'entrées sont faites pour éviter cela. :-)

      Par ailleurs, ça se cache très bien.

      Pour la deuxième partie, ma foi, aucune difficulté supplémentaire, rien de plus à coder ou presque, puisque le nombre de chemins de A à D en passant par B puis C ou par C puis B, c'est simplement la somme de :

      • le produit du nombre de chemins de A à B, du nombre de chemins de B à C et du nombre de chemins de C à D ;
      • le produit du nombre de chemins de A à C, du nombre de chemins de C à B et du nombre de chemins de B à D.

    • [^] # Re: Jour 11

      Posté par  . Évalué à 1 (+0/-0).

      Déjà, il faut remarquer que le graphe est acyclique.

      Du coup, on peut faire un tri topologique dessus.
      C'est à dire que chaque arête va d'un sommet vers un sommet plus grand selon cet ordre.

      A partir de là, c'est facile de compter le nombre de chemins.
      En pseudo-code.

      fonction nb_chemins(graphe, source, dest):
   initialiser un tableau t de graphe.len() éléments à 0
   t[source] = 1
   pour chaque sommet i du graphe selon l'ordre topologique
       pour chaque voisin j de i
           t[j] += t[i]
   renvoyer t[dest]

      Pour la partie 2, on peut le trouver avec la formule suivante

      c(svr, dac) * c(dac, fft) * c(fft, out) + c(svr, fft) * c(fft, dac), c(dac, out)

      où c(a, b) est le nombre de chemins de a à b.
      sachant qu'une des parties de la somme est forcément nulle.

      50 microsecondes pour les deux parties.

    • [^] # Re: Jour 11

      Posté par  . Évalué à 2 (+0/-0).

      graphe global

      graphe simplifié

    • [^] # Re: Jour 11

      Posté par  . Évalué à 3 (+1/-0). Dernière modification le 11 décembre 2025 à 18:38.

      Bon, je sais pas ce que j'ai merdé mais c'est en effet trivial, en 10 lignes:

      from functools import cache

G = dict()
for line in open(0).read().strip().split('\n'):
    p, c = line.split(":")
    G[p] = c.strip().split()
G["out"] = []

@cache
def count_paths(node, target):
    return 1 if node == target else sum(count_paths(c, target) for c in G[node])

print(count_paths("you","out"), count_paths("svr","fft")* count_paths("fft","dac")* count_paths("dac","out"))

      En 13MB et 0.05s

      • [^] # Re: Jour 11

        Posté par  . Évalué à 2 (+0/-0).

        451 microsecondes pour les deux parties en version compilée.

    • [^] # Re: Jour 11

      Posté par  (Mastodon) . Évalué à 2 (+0/-0).

      Une journée - encore - sans ordinateur, avec une résolution en très peu de temps de réflexion, et un calcul instantané sur téléphone.

      Pour l'exercice 2, un cache bien posé, un découpage en trois sous-graphes entre svr->fft->dac->out, et la supposition qu'il n'y avait pas de boucles.
      En fait, avec des boucles, de toute façon l'énoncé est infaisable, puisqu'on doit dénombrer les chemins possible, une seule boucle où que ce soit sur un seul chemin permet un nombre infini de chemins.
      Les boucles ça se gère en cas de recherche du plus court chemin.

      Si j'avais eu 0 entre fft et dac, j'aurais inversé les deux, et pour le cas général, additionner les deux semble pertinent.

      J'ai aussi fait une fonction d'analyse des données pour faire le cas d'exemple, où les données sont différentes entre l'exercice 1 et le 2, d'où le clear_cache aussi.

      Ma multiplication finale c'est 3241 * 22130172 * 7345, donc avec un algo plus naïf, et surtout sans cache, on arrive à trouver les valeurs de svr à fft et de dac à out, mais pas de fft à dac, avec 22 millions de chemins.
      En pratique, ma fonction paths est appelée 3102 fois entre les deux exercices, avec 1891 fois où le cache a répondu et 1211 fois où le contenu de la fonction a été exécuté, autant dire que c'est assez négligeable pour le dénombrement total de ~500 billions de chemins, et ça ne prend rien en RAM.

      data = sys.stdin.read().strip().splitlines()
@cache
def paths(src="you",dst="out"):
    return 1 if src==dst else sum(paths(i,dst) for i in servers.get(src,[]))

def getservers(data):
    paths.cache_clear()
    return {
        a: b.strip().split()
        for l in data
        for a,b in [l.split(":")]
    }
servers=getservers(data)
ex1 = paths()

srv=paths("svr","fft")
fft=paths("fft","dac")
dac=paths("dac","out")
ex2 = srv*fft*dac
      • Yth.

  • # Jour 12

    Posté par  . Évalué à 1 (+0/-0).

    Bon, j'ai craqué!

    Je m'y suis mis Mercredi soir dans le train.
    En voyant des collègues qui galérait dessus.

    Très sympa, ce dernier jour, j'ai trouvé une solution pas du tt opti: 32min

    Des km de Java générait en grand partie par Mistral. J'ai tenté de lui expliquait l'algo mais j'ai du finalement abandonner
    pour le coder moi-même.

    Je suis partie sur l'idée d'un parcours en profondeur piloté par une fonction de scoring

    En gros, j'ai une fonction récursive qui pose pièce par une pièce

    poseLesPiecesDisponible
       J'établie la liste des pieces disponibles
       Si il n'y a plus de piece disponible
           return true;

       J'établie une liste points à gauche de l'air de jeu occupé une bande de 2 pixel qui contient des occupés et innocupés

       listPlacementValide = [...] 
       Pour point, je calcule tous les placements & rotations possible des pieces disponible 
       A chaque placement , je calcule un score & je stocke le résultat dans listPlacementValide.
       Si listPlacementValide alors return false;

       Je trie la liste des placements possible par le score obtenu

       Je conserve le meilleur // J'ai essayé dans conservé 2 ou 3 , mais j'explose en temps d'execution

       Pour chaque placementValide de listPlacementValide 
           J'applique le placement
           Si poseLesPiecesDisponible alors return true
           Je revert le placement

       // Aucune solution convient
       return false

    Vu que j'explosais en temps à 2 ou 3. J'ai du améliorer ma fonction de scoring + un bonus pour les pieces 4 & 5

            public static long getScoreSpace(int[][] destMatrix) {
        int score=0;    
        int width= destMatrix[0].length;
        int height = destMatrix.length;
        for(int y=0;y < height;y++) {           
            for(int x=0;x < width;x++) {
                if(destMatrix[y][x] < 0) {
                    score += 3;
                    if(x+1 < width) {
                        if(destMatrix[y][x+1] >= 0) {
                            score--;
                        }
                    }
                    if(y+1 < height) {
                        if(destMatrix[y+1][x] >= 0) {
                            score--;
                        }
                    }
                } 
                 }
        }
        return score;
    }

    c'est sale mais çà a marché :-p

    Vous avez trouvé mieux ?

    • [^] # Re: Jour 12

      Posté par  . Évalué à 2 (+1/-0). Dernière modification le 12 décembre 2025 à 15:54.

      En fait, il y avait encore plus simple.

      On peut totalement de pas prendre en compte la forme des tuiles et juste regarder combien de carrés 3x3 qu'on peut mettre dans la grille. Donc une simple division par 3 suffit.
      Totalement bidon comme problème (mais vraiment compliqué si on ne fait pas cette supposition et qu'on veut une solution générale).

      Voici mon code

      pub fn solve(input: &str) -> (usize, u32) {
    let p1 = input
        .lines()
        .skip(30)
        .filter(|&line| {
            let mut it = line.iter_unsigned::<u32>();
            let (x, y) = it.next_tuple().unwrap();
            (x / 3) * (y / 3) >= it.sum() 
        }).count();
    (p1, 0)
}

      • [^] # Re: Jour 12

        Posté par  . Évalué à 1 (+0/-0).

        Ce qui est marrant,c'est que ton code ne fonctionne pas pour le jeu de test.

        Mais finalement , çà ne me surprend pas car j'étais surpris que mon code marche alors que je suis loin de trouver un optimum
        Et on voit que je ne fais pas toujours le meilleur choix. Je calcule des distributions de ce type
        ```
        . 1 1 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 3 3 3 4 4 4 3 3 3 4 4 4 3 3 3 4 4 4 3 3 3 .
        1 1 . 0 0 . . 0 0 0 0 2 2 . 4 4 4 4 4 3 3 4 4 4 4 3 3 4 4 4 4 3 3 4 4 4 4 3 3 .
        1 1 1 0 5 5 5 . 0 0 2 2 4 4 4 4 4 4 4 3 3 4 4 4 4 3 3 4 4 4 4 3 3 4 4 4 4 3 3 .
        1 1 5 5 5 5 0 0 0 . 2 2 2 4 4 4 4 4 4 . . . 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
        1 1 1 5 5 5 5 0 0 . 4 4 4 4 4 4 4 4 4 4 . . . 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 . 4
        1 1 5 5 5 0 0 0 0 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 . 4 4 4 4 4 4 . 4 4 4
        1 1 1 . . 0 0 . . 4 4 4 4 . 4 4 4 4 4 4 4 3 3 3 4 4 4 . 4 . 4 . 4 4 4 4 4 4 . .
        1 1 5 5 5 0 5 5 5 4 4 4 2 2 . . . . 4 4 4 . . . . . . . . . . . . . . . . . . .
        1 1 1 5 5 5 5 5 0 0 0 2 2 2 2 2 . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 5 5 5 5 5 5 5 0 0 2 2 2 2 2 . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 1 . 5 5 5 0 0 0 0 2 2 2 2 . . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 5 5 5 . . 0 0 . 2 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 1 5 5 5 5 0 . . 2 2 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 5 5 5 5 5 5 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 1 . 5 5 5 5 5 5 5 . . . . 2 2 2 . . . . . . . . 2 2 2 . 2 2 2 . . . . . . .
        1 1 5 5 5 . 5 5 5 5 0 0 0 . . . 2 2 . . . . . . . . . 2 2 2 2 2 2 . . . . . . .
        1 1 1 5 5 5 5 . 5 5 5 0 0 3 3 2 2 3 3 3 . . . . 2 2 2 2 2 2 2 2 . . . . . . . .
        1 1 5 5 5 5 0 0 0 0 0 0 0 3 3 3 3 3 3 3 2 . 2 2 2 . 2 2 2 2 2 . . . . . . . . .
        1 1 1 . 5 5 5 0 0 0 0 . . 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 . . . . . . . . .
        1 1 0 0 0 0 0 0 0 0 . 4 4 4 3 3 3 3 3 3 3 2 2 3 3 2 2 2 2 2 2 2 . 2 2 2 . . . .
        1 1 1 0 0 0 0 0 0 0 4 4 4 4 3 3 2 2 2 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 . . . .
        1 1 1 1 0 0 . . 0 0 4 4 4 4 3 3 3 2 2 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 . . . . .
        1 1 1 1 1 0 0 0 0 0 4 4 4 3 3 3 2 2 3 3 . 3 3 3 3 3 3 . . 2 2 2 2 2 2 2 . . . .
        1 1 1 1 1 0 0 . 0 0 . 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 2 . 2 . 2 . 2 2 2 2 . . .
        1 1 1 1 1 0 . . 0 0 0 4 . 4 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 . 2 2 2 2 . 2 . . .
        1 1 1 1 1 0 0 0 0 0 0 4 3 4 2 2 3 3 3 2 2 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 . . . .
        1 1 1 1 1 0 0 . 0 0 3 3 3 2 2 3 3 3 2 2 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 . . .
        1 1 1 1 1 0 . . 0 0 3 3 3 2 2 2 3 3 2 2 2 3 3 3 3 3 2 . 2 2 2 2 2 2 2 . 2 . . .
        1 1 1 1 1 0 0 0 0 0 0 0 0 0 . . 3 3 . . . 3 3 3 . . . . . . . 2 2 . . . . . . .
        1 1 1 1 1 0 0 0 0 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . .
        1 1 1 1 1 0 . 5 5 5 0 0 0 0 5 5 5 . . . . . . . . 3 3 3 . . . . 2 2 3 3 3 . . .
        1 1 1 1 1 0 0 0 5 0 0 0 0 0 0 5 5 5 5 . 5 5 5 . . 3 3 3 . . . . 2 2 2 3 3 . . .
        1 1 1 1 1 0 0 5 5 5 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 3 3 3 3 3 3 2 2 2 2 3 3 3 3 .
        1 1 1 1 1 0 . 5 5 5 . 0 0 5 5 5 5 5 5 5 5 5 5 5 4 4 4 3 3 3 3 2 2 2 3 3 3 3 3 .
        1 1 1 1 1 0 0 0 5 0 0 0 . . 5 . . . 5 5 5 . 5 5 5 . 4 3 3 3 3 3 2 2 3 3 3 3 3 3
        1 1 1 1 1 0 0 5 5 5 0 0 0 5 5 5 5 5 5 . 5 5 5 . 4 4 4 3 3 3 . 3 3 3 3 3 3 3 . .
        1 1 1 1 1 0 . 5 5 5 . 0 0 0 5 5 5 5 5 5 5 5 5 5 5 . . 3 3 3 . 3 3 3 . 3 3 3 . .
        1 1 1 1 1 0 0 0 5 5 5 5 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 3 5 5 5 3 5 5 5 3 5 5 5 .
        1 1 1 1 1 0 0 5 5 5 5 0 0 0 5 5 5 . 5 5 5 . 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 . .
        1 1 1 1 1 0 0 0 0 5 5 5 0 0 4 4 4 4 4 4 4 4 4 . 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 .
        1 1 1 . . . 0 0 . . . . . 0 4 . . 4 . . 4 . . . . . 5 5 5 . 5 5 5 . 5 5 5 . . .
        . 1 . . . . 0 . . . . . . . 4 4 4 4 4 4 4 4 4 . . . . . . . . . . . . . . . . .

    • [^] # Re: Jour 12

      Posté par  . Évalué à 2 (+0/-0). Dernière modification le 13 décembre 2025 à 10:35.

      Moi aussi j'ai craqué…

      Je me suis dis qu'il fallait réaliser tous les arrangements possibles de tous les cadeaux, par décalage dans la grille et par inversions. Et que si au moins un passe, ça fait +1. Je me suis aussi dit, si au total, les cadeaux prennent plus de place que la boite, même en arrangeant, ça passera pas, on peut mettre directement 0.

      Pas trop le goût de me lancer dans l'implem tout de suite, je suis allé voir sur Reddit et je tombe sur :

      answer = 0
for parts in [line.strip().split() for line in open(0, "rt") if "x" in line]:
    size = [int(x) for x in parts[0][:-1].split("x")]
    presents = sum([int(x) for x in parts[1:]])
    answer +=  (size[0] * size[1])>= presents*9
print(answer)

      Donc qu'en gros, si il y a assez de place au global, c'est bon. Pas besoin de regarder la forme des cadeaux. Sans y croire, j'essaye sur mon input et la réponse est la bonne :/

      Lapin compris.

      • [^] # Re: Jour 12

        Posté par  (Mastodon) . Évalué à 2 (+0/-0). Dernière modification le 13 décembre 2025 à 15:53.

        Ah ouais, j'ai juste eu le temps de réfléchir au problème, mais c'est tellement con au final.
        Me reste plus qu'à prendre le temps de finir le jour 10 maintenant, parce que sur téléphone c'est trop galère, donc je dois retrouver mon PC, et mon Linux :)

        • Yth.

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.