Forum Programmation.autre Advent of Code 2023, jour 12

Posté par  (Mastodon) . Licence CC By‑SA.
Étiquettes :
1
12
déc.
2023

Nous arrivons enfin aux sources chaudes !

On laisse de côté l'Onsen, le bain chaud à l'asiatique, agréable et reposant.
On va plutôt aller à côté, vers un bâtiment qui ressemble à un gros bloc de métal tout moche, et froid.

Froid ?
Ben oui, on s'attendait à quoi !
La lave ne s'écoule plus pour chauffer les sources froides…

Pour aller réparer ça, on doit grosso-modo s’asseoir sur un geyser et se faire propulser vers l'île du magma.
Sauf qu'elles sont en piteux états, et que les indications sur leur état sont elles-mêmes en piteux état. Avec ça on n'est pas rendus.

On a un truc du genre, avec . une source en bon état, # une source endommagée, et ? illisible :

???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

Les séries de nombre indique des séries non contiguës de sources endommagées.
Sur la première on voit bien qu'il y a une solution possible : #.#.###. Sur la seconde, bah on a plusieurs solutions possibles.
La question est de savoir combien ?

Ici, la réponse est 1, 4, 1, 1, 4 et 10, sot 21 au total.

On va jouer avec 1000 lignes plus complexes que ça, pour un résultat autour de 8000.

The plot twist

Bon, en fait c'était une blagounette, comme d'habitude, il faut démultiplier toutes les données 5 fois, en séparant les plans par des ?, la ligne 1 donne ça :
???.###????.###????.###????.###????.### 1,1,3,1,1,3,1,1,3,1,1,3,1,1,3
Tout de suite, c'est moins court, même s'il n'y a toujours qu'une seule solution.
Sauf que sur les données d'exemple complète ça donne :
1, 16384, 1, 16, 2500, 506250 = 525152

Et sur les données réelles, on est plutôt vers 18000 milliards.

Alors on laisse tomber les idées à base d'expressions rationnelles, même si ça avait l'air adapté, il va falloir être intelligent, malin, futé, et très organisé.
Sinon c'est pas qu'on va faire fondre du processeur, c'est surtout qu'on va mourir avant d'avoir une réponse.

Bon courage, celui-ci est vraiment plus difficile, et chapeau Guillaume Bagan sur le leaderboard pour avoir fini avant moi !

  • Yth.

PS: je ne sais pas où vous trouvez les jolies n'images, mais elles sont jolies, alors faut pas hésiter à les mettre en commentaire !

  • # Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

    Posté par  (Mastodon) . Évalué à 3. Dernière modification le 12 décembre 2023 à 13:22.

    J'ai commencé par utiliser des expressions rationnelles, et itertools.combinations(), pour le fun, je savais que ça aller rater en exercice 2, mais c'était assez rapide pour avoir le twist et réfléchir directement au vrai problème, alors j'ai joué, et j'ai évidemment perdu :)

    On regarde les sources à l'état inconnu U(nknown), les sources endommagées non répertoriées M(iss), et on va ordonner M positions parmi U grâce à cette fonction super cool.
    On recompose donc une ligne, et on applique notre regexp dessus : si ça matche on comptabilise.

    C'est mignon, c'est intelligent, ça fait un peu brûler des bogomips sur la première partie, mais ça va.
    C'est intelligent, mais pas très malin.
    Et il faut être malin, futé, et organisé pour s'en sortir.

    Alors on laisse tomber les regexp.

    import sys
import re
from functools import cached_property
import math
import itertools

MUL = int(argv[1] if len(argv) > 1 else 2)
data = sys.stdin.read().strip().splitlines()

class Spring:
        def __init__(self, puzzle, clues, mul=1):
        puzzle = "?".join(puzzle for _ in range(mul))
        self.puzzle = list(puzzle.replace(".", " "))
        self.clues = [int(_) for i in range(mul) for _ in clues.split(",")]
        self.unknown = self.puzzle.count("?")
        self.known = self.puzzle.count("#")
        self.miss = sum(self.clues) - self.known
        if self.unknown == self.miss:
            self.puzzle = [" " if _ == " " else "#" for _ in self.puzzle]
            self.miss = self.unknown = 0
            self.known = sum(self.clues)
        self.str = "".join(self.puzzle)


    @cached_property
    def reg(self):
        return re.compile(" *" + " +".join("#" * i for i in self.clues) + " *")

    def __str__(self):
        return f"Spring: {self.str} {self.clues} [{self.reg.pattern}] -> {self.possibilities}"

    @property
    def possibilities(self):
        # C(miss, unknown): combinations of missing clues into unknwon elements
        return math.factorial(self.unknown) / (
            math.factorial(self.miss) * math.factorial(self.unknown - self.miss))

    def __iter__(self):
        puzzle = self.str.replace("?", " ")
        for combination in itertools.combinations(
            [i for i, _ in enumerate(self.puzzle) if _ == "?"],
            self.miss
        ):
            yield "".join("#" if i in combination else _ for i, _ in enumerate(puzzle))

springs = [Spring(*line.split(), MUL) for line in data]
nb = 0
for s in springs:
    print(s)
    for c in s:
        if s.reg.match(c):
            nb += 1
print(nb)

    Voilà l'affichage des Springs des données de test :

    Spring: ??? ###???? ###???? ###???? ###???? ### [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3] [ *# +# +### +# +# +### +# +# +### +# +# +### +# +# +### *] -> 92378.0
Spring:  ??  ??   ?## ? ??  ??   ?## ? ??  ??   ?## ? ??  ??   ?## ? ??  ??   ?##  [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3] [ *# +# +### +# +# +### +# +# +### +# +# +### +# +# +### *] -> 77558760.0
Spring: ?#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#? [1, 3, 1, 6, 1, 3, 1, 6, 1, 3, 1, 6, 1, 3, 1, 6, 1, 3, 1, 6] [ *# +### +# +###### +# +### +# +###### +# +### +# +###### +# +### +# +###### +# +### +# +###### *] -> 1761039350070.0
Spring: ???? #   #   ????? #   #   ????? #   #   ????? #   #   ????? #   #    [4, 1, 1, 4, 1, 1, 4, 1, 1, 4, 1, 1, 4, 1, 1] [ *#### +# +# +#### +# +# +#### +# +# +#### +# +# +#### +# +# *] -> 10626.0
Spring: ???? ######  ##### ????? ######  ##### ????? ######  ##### ????? ######  ##### ????? ######  #####  [1, 6, 5, 1, 6, 5, 1, 6, 5, 1, 6, 5, 1, 6, 5] [ *# +###### +##### +# +###### +##### +# +###### +##### +# +###### +##### +# +###### +##### *] -> 42504.0
Spring: ?###??????????###??????????###??????????###??????????###???????? [3, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1] [ *### +## +# +### +## +# +### +## +# +### +## +# +### +## +# *] -> 1575580702584.0

    Le nombre à la fin c'est le nombre de combinaisons, le nombre d'itérations de notre itertools.combinations().
    On pourrait certainement optimiser la génération des puzzle dans l'itération, mais ça ne nous mènera nulle part, avec plus de 3 milliard d'itérations, on sait on ça va mener. Et il ne s'agit que des données de test…

    Déjà pour un coefficient de pliage de 3 on en a pour un peu plus d'une minute, j'ai coupé le processus que j'avais oublié après 1h45 avec un coefficient à 4. Sur les données de test.

    J'étais bien sûr parti sur autre chose.
    Et un autre chose terriblement plus efficace mais encore largement pas assez efficace, parce qu'alors je n'avais été qu'intelligent et malin, il manquait la ruse (qui n'a pas fonctionné), et enfin l'organisation.

    Mais bon, c'était fun :)

    • Yth, qui fait durer le plaisir tant qu'on n'est que deux à avoir terminé la partie 2.

    • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

      Posté par  (site web personnel) . Évalué à 4. Dernière modification le 12 décembre 2023 à 13:51.

      Ayé, j'ai résolu la partie 2. Mais je ne suis pas du tout satisfait de ma solution, c'est super efficace mais j'ai l'impression d'avoir triché.

      Je vous explique. Pour la partie 1, j'ai écrit une fonction récursive qui donne le nombre de possibilités d'arrangements restants étant donné des choix déjà faits sur un certain nombre de sources. Elle prend en entrée un état d'avancement, qui indique :

      • l'état de fonctionnement de la dernière source considérée (fonctionnelle ou hors service, pas inconnue, comme on va le voir.) ;
      • la position de la dernière source considérée ;
      • l'index du groupe courant de sources hors service ;
      • le nombre de sources hors service actuellement comptabilisée dans le groupe courant.

      Si on a considéré toutes les sources, ça renvoie directement 1 si le compte est bon (on a atteint le dernier groupe de sources cassées et il est exactement rempli) et 0 sinon.

      Si on n'a pas encore considéré toutes les sources, ça regarde la suivante et ça itère sur ses états possibles (une source en état ne peut être qu'en état, une source cassée ne peut être que cassée et une source en état inconnu peut être les deux, évidemment) :
      * pour un état hors service, si la dernière source considérée était en état, ça ouvre un nouveau groupe… si possible, c'est à dire s'il reste des groupes non considérés, sinon on est dans une impasse et ça continue ;
      * pour un état en état (hmm…), si la dernière source considérée était hors service, ça vérifie si le compte de sources hors service correspond au groupe courant et si ce n'est pas le cas on est dans une impasse et ça continue ;
      * dans les cas où on n'a pas continueé, on appelle la même fonction récursive pour l'étape d'après et on ajoute sa valeur de retour à celle qu'on va renvoyer.

      Ce sera peut-être plus clair avec le code :

      from collections.abc import Iterable, Iterator
from typing import Optional, Self
from enum import Enum

class Condition(Enum):
    OPE='.'
    BRK='#'
    UNK='?'

    def states(self) -> Iterator[Self]:
        if self is self.OPE:
            yield self
        elif self is self.BRK:
            yield self
        else:
            yield self.OPE  # type: ignore
            yield self.BRK  # type: ignore

class Condition(Enum):
    OPE='.'
    BRK='#'
    UNK='?'

    def states(self) -> Iterator[Self]:
        if self is self.OPE:
            yield self
        elif self is self.BRK:
            yield self
        else:
            yield self.OPE  # type: ignore
            yield self.BRK  # type: ignore

    def arrangements(self) -> int:
        def aux(condition: Condition, spring: int, group: int, count: int) -> int:
            if spring == len(self.springs) - 1:
                # Last spring has just been accounted for, time to check:
                # - we are at last group;
                # - that group is full.
                if (group == len(self.groups) - 1
                    and count == self.groups[-1]):
                    return 1
                return 0
            # Some springs have not been checked yet.
            next_spring = spring + 1
            next_group = group
            next_count = count
            possibilities = 0
            for next_condition in self.springs[next_spring].states():
                if next_condition is Condition.BRK:
                    if condition is Condition.OPE:
                        # Broken spring after an operational one opens
                        # new group… if possible.
                        if group == len(self.groups) - 1:
                            # Last group has already been checked and closed:
                            # dead end.
                            continue
                        # We can open next group
                        next_group += 1
                        next_count = 0
                    # Regardless of previous spring condition, increase current
                    # group count.
                    next_count += 1
                    if next_count > self.groups[next_group]:
                        # New current group is overfull: dead end.
                        continue
                if next_condition is Condition.OPE:
                    if condition is Condition.BRK:
                        # Operational spring after a broken one closes current
                        # group, time to check group count.
                        if count != self.groups[group]:
                            # Dead end
                            continue
                possibilities += aux(next_condition, next_spring, next_group, next_count)
            return possibilities
        return aux(Condition.OPE, -1, -1, 0)

      Bon, pour la partie 2, c'est beaucoup trop long, évidemment. Et donc, faute de trouver une astuce, vu le genre de paramètres de la fonction, j'ai bêtement utilisé un…

      • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

        Posté par  (Mastodon) . Évalué à 4.

        mais j'ai l'impression d'avoir triché.

        Ce n'est pas de la triche de ne pas recalculer une tonne de fois la même chose.
        Si c'est déjà calculé, c'est déjà calculé, garde-le en mémoire et réutilise-le.

        Faut juste s'assurer que ça ne va pas faire trop de données enregistrées, sinon il faut gérer ces données de façon un poil intelligentes, pour essayer de ne conserver que ce qui peut être pertinent.
        Mais de toute façon, à faire du récursif, on n'a plus une utilisation fixe de la RAM, et on peut exploser.

        La seule question qui se pose c'est de savoir si l'ampleur du travail est telle qu'on peut le faire ou pas.

        Ici, ça va, et on le sait, on n'a pas tant que ça de données à se souvenir, les entrées sont des entiers, la sortie aussi.

        • Yth.

        • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

          Posté par  (site web personnel) . Évalué à 4. Dernière modification le 12 décembre 2023 à 14:28.

          Bon, voilà quoi. J'ai utilisé un cache, évidemment.

          Pour info, avec un coefficient de pliage de 10 et en utilisant CPython, j'obtiens une réponse 1 498 094 344 344 361 041 914 985 222 578 (1,5×10³⁰ soit 1,5 millier de milliards de milliards de milliards) en 3,3 secondes et une consommation mémoire de 22 Mio :

          % /usr/bin/time -v bin/12.py -2 < in/12.in 
Solving part 2:
1498094344344361041914985222578
    Command being timed: "bin/12.py -2"
    User time (seconds): 2.86
    System time (seconds): 0.41
    Percent of CPU this job got: 99%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.29
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 22772
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 111390
    Voluntary context switches: 1
    Involuntary context switches: 305
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0

          • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

            Posté par  (Mastodon) . Évalué à 2.

            C'est intéressant ces discussion, parce qu'on trouve toujours des bidouilles pour améliorer son code, j'en ai rajouté quelques-unes et au final, en taille 10, je suis passé de 6 secondes et 326Mo de RAM à 0,9 secondes et 12,5Mo de RAM.
            C'est pas spécialement négligeable pour un code sensiblement identique.

            1. Ne pas être récursif avec un paramètre self, mais utiliser une fonction pure, qui sera la fonction récursive, dans la méthode de classe, qui est appelée de l'extérieur.
            2. Réduire les paramètres, j'ai diminué à deux paramètres : la position et le nombre de blocs de sources endommagées restant à placer. Si on regarde, mon plus gros problème a une complexité de 12540, en multipliant les positions de départ possible par le nombre d'indices, c'est la plus grand valeur, donc jamais je n'aurais un cache plus gros que ça.
            3. traiter les sources endommagées par bloc, plutôt que de consomme un par un les éléments jusqu'à remplir le bon nombre. Là l'idée de Guillaume est pas mal ça accélère bien les choses.
            4. simplifier les données en entrée pour réduire les suites de . à un seul ., en pratique c'est strictement équivalent. Par contre j'en rajoute aussi un à la fin, ça simplifie le code. En pratique on y gagne un peu, pas négligeable !
            5. Noter la position de la dernière source endommagée, comme ça quand on a posé le dernier bloc, on peut vérifier immédiatement s'il reste une source endommagée plus loin, et valider un peu plus rapidement une fin de chemin (en pratique ça ne fait rien gagner, mais ça aurait pu).
            6. Mon dernier point a consisté à me débarrasser de cette idée de rappeler la fonction récursive en forçant la source courante, inconnue, à fonctionnelle ou endommagée, ça réduit le nombre d'arguments à 2, la complexité de l'ensemble, la taille du cache, et même le temps d'exécution. On doit rejoindre ce que tu fais Tanguy, avec ton Condition.States qui yield OPE et BRK. M'aura fallut du temps pour en arriver là.

            Par contre je suis resté avec des -1/0/1 au lieu d'un Enum, j'y perd avec un Enum. Peut-être un IntEnum, pour avoir le meilleur des deux mondes ?

            Au bout du compte, toujours en taille 10 je suis descendu à moins d'une seconde et ~16Mo de RAM.
            Il y a 488 387 récursions calculées, et le cache en a épargné 245 314, qui chacune en ont épargnées récursivement un nombre probablement assez incommensurable, parce que déjà en taille 2, sans le cache on monte à 5 secondes, et en taille 3 à 11 minutes.
            Sans cache, point de salut dans cet exercice.

            Le code final, avec les statistiques des caches :

            from sys import stdin, argv
from functools import cache
import re
MUL = int(argv[1] if len(argv) > 1 else 2)
data = stdin.read().strip().splitlines()
class Spring:
  def __init__(self, puzzle, clues, mul=1):
    self.clues = [int(_) for i in range(mul) for _ in clues.split(",")]
    self.str = "?".join(re.sub("[.]+", ".", puzzle) for _ in range(mul)) + "."
    self.size = len(self.str)
    self.puzzle = [
      {"?": 0, ".": 1, "#": -1}.get(_)
      for _ in (self.str)
    ]
    self.nextfunctional = [self.puzzle[n:].index(1) for n in range(self.size)]
    self.lastdamaged = ([n for n, _ in enumerate(self.puzzle) if _ == -1] or [0])[-1]
    self.clue_max_pos = [
      self.size - sum(self.clues[-n:]) - (n - 1)
      for n in range(len(self.clues) + 1)
    ]
    self.clue_max_pos[0] = self.size

  def run(self):
    @cache
    def _run(pos, clueleft):
      if pos > self.clue_max_pos[clueleft]:
        return 0  # Not enough space remaining
      if pos == len(self.puzzle):
        return 1
      value = self.puzzle[pos]
      # spring could be functional
      r = _run(pos + 1, clueleft) if value >= 0 else 0
      if value > 0:
        return r
      # spring could be damaged
      if not clueleft:  # None is available, wrong path
        return r
      clue = self.clues[-clueleft]
      # no space for clue
      if clue > self.nextfunctional[pos]:
        return r
      # clue cannot be followed by a damaged spring
      if self.puzzle[pos + clue] == -1:
        return r
      # No clue left, but still damaged springs
      if clueleft == 1 and pos + clue < self.lastdamaged:
        return r
      return r + _run(pos + clue + 1, clueleft - 1)
    return _run(0, len(self.clues))
    r = _run(0, len(self.clues))
    self.cache_info = _run.cache_info()
    return r

springs = [Spring(*line.split(), MUL) for line in data]
print(sum(s.run() for s in springs))
hits = sum(s.cache_info.hits for s in springs)
misses = sum(s.cache_info.misses for s in springs)
print(f"Functions called = {misses}, calls cached = {hits}")

            Il faut retirer les infos de cache et ne conserver que la liste des Spring, pour réduire la RAM à 12,5Mo :

            print(sum(Spring(*line.split(), MUL).run() for line in data))
            • Yth.

    • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

      Posté par  (Mastodon) . Évalué à 3. Dernière modification le 12 décembre 2023 à 14:07.

      Et donc voici ma solution, en python, et là encore, de façon surprenante, PyPy est quasiment équivalent à CPython, malgré les gros gros calculs !

      Juste pour info, avec un coefficient de pliage à 10, et une réponse de 739 944 601 532 013 104 445 095 536 (740 millions de milliards de milliards), mon programme final sort la réponse en 5 secondes.
      L'exercice 2 normal prend 2 secondes.

      On oublie les regexp, on va simplement faire un parcours récursif.
      On va de gauche à droite et on va consommer les indices, et brancher sur chaque ? qui n'a pas une valeur contrainte en considérant soit une source en bon état . soit une source endommagée #.
      Dès qu'on est au bout du chemin avec tous les indices consommés, on a trouvé une solution, on remonte donc 1. En cas d'impossibilité, on s'arrête et on remonte 0.

      Ça c'est malin.
      Ça ne suffit pas, il faut être rusé, et optimiser les conditions d'arrêt, sinon on peut avoir un résultat faux déjà, et puis explorer des trucs assez loin pour réaliser au bout que c'est pas bon, parce qu'il nous reste des indices non exploités.
      Donc calculer l'espace minimal nécessaire à placer les indices non utilisés, et si on dépasse, on sait qu'on va dans le mur, on s'arrête tout de suite.

      Ça fait gagner du temps, mais fichtre, pas encore assez, ça turbine, ça turbine, j'ai envisagé de sortir la grosse machine, 4 cœurs, 1 quart du programme chacun, mais non, déjà avec un facteur de 4 ça va être long, à 5 c'est mort.

      Alors ruser encore plus ?
      Et si à chaque branchement :

      • on teste avec une source en bon état.
      • si on a des solutions, alors on sait que l'indice suivant pouvait être décalé d'un cran vers la gauche, donc on peut multiplier par deux !
      • sinon on teste le chemin avec une source endommagée.

      Ça va beaucoup plus vite, beaucoup beaucoup.
      Mais c'est faux, il va falloir encore plus d'intelligence, de ruse, pour comprendre les effets de bords, pourquoi ça ne fonctionne pas.
      J'ai plus de cerveau, je suis fatigué, ça ne va pas fonctionner…

      Allez, encore un effort, il faut une idée !

      Et là c'est l'évidence, ma fonction récursive est mauvaise mais elle peut être bonne, j'ai fait en sorte de transmettre uniquement le strict nécessaire pour passer à l'étape d'après :

      • La position actuelle dans le parcours du plan ;
      • ce qu'il me reste à consommer dans l'indice actuel, cette valeur est négative si je suis entre deux indices ;
      • le numéro de l'indice en cours de consommation ;
      • la gueule du puzzle en l'état pour le débuggage ;
      • la valeur de remplacement pour une source inconnue (lors d'un branchement j'appelle à l'identique avec . puis #, ça remplace le ? des données initiales).

      Le calcul de ce qui reste à parcourir ne dépend pas de ce qui s'est passé avant, mais uniquement de ces paramètres : (position, reste de l'indice actuel, numéro de l'indice actuel, valeur de remplacement).
      On vire le puzzle, et on dégage tout le débuggage, de toute façon on sait que notre algo fonctionne.

      Et là, on utilise @cache sur notre fonction récursive.

      Et voilà.

      Une dernière ruse lors de la rédaction de ce message pour réaliser que le reste à consommer peut être optimisé en étant toujours à -1 comme valeur négative, je faisais un x -= 1 donc la valeur pouvait être à -2, -3 etc, mais ça n'a pas de valeur autre que : je ne suis pas en train de parcourir un indice.
      Ça fait passer de 5 à 2 secondes, et divise la RAM consommée par 4.

      Voici le code :

      from sys import stdin, argv
from functools import cache
MUL = int(argv[1] if len(argv) > 1 else 1)
data = stdin.read().strip().splitlines()

class Spring:
  def __init__(self, puzzle, clues, mul=1):
    self.clues = [int(_) for i in range(mul) for _ in clues.split(",")]
    self.str = "?".join(puzzle for _ in range(mul))
    self.size = len(self.str)
    self.puzzle = [
      {"?": 0, ".": 1, "#": -1}.get(_)
      for _ in (self.str)
    ]

  def __str__(self):
    return f"Spring: {self.str} {self.clues}"

  def run(self):
    r = self._run(0, -1, 0, 0)
    return r

  @cache
  def clue_max_pos(self, n):
    return self.size - sum(self.clues[n:]) - len(self.clues[n + 1:])

  @cache
  def _run(self, pos, clue, clue_id, force_value=0):
    if clue < 0:
      if pos > self.clue_max_pos(clue_id):
        return 0  # Not enough space remaining
    else:
      if pos > self.clue_max_pos(clue_id + 1) - clue:
        return 0  # Not enough space remaining
    if pos == len(self.puzzle):
      return 1  # That path is working, yay!
    value = force_value or self.puzzle[pos]
    if value == -1:  # Damaged
      if clue < 0:  # We are starting to consumate a new clue
        if clue_id >= len(self.clues):  # None is available, wrong path
          return 0
        clue = self.clues[clue_id]
      if clue:  # We consumate an active clue
        return self._run(pos + 1, clue - 1, clue_id)
      else:  # the clue was zero, the path is wrong
        return 0
    elif value == 1:  # functional, current clue must be <= 0
      if clue > 0:  # wrong path
        return 0
      # If we just finished a clue, preparing for the next one
      # clue will now be < 0 until starting the next clue
      return self._run(pos + 1, -1, clue_id + (clue == 0))
    else:  # unknown
      if clue > 0:  # this *must* be a damaged one
        return self._run(pos, clue, clue_id, -1)
      elif clue == 0:  # this must be a proper one
        return self._run(pos, clue, clue_id, 1)
      else:  # trying both possibilities
        return (
          self._run(pos, clue, clue_id, 1)
          + self._run(pos, clue, clue_id, -1)
        )

springs = [Spring(*line.split(), MUL) for line in data]
print(sum(s.run() for s in springs))

      Côté RAM, avec MUL = 10 on monte à 300Mo, c'est 120Mo pour le problème réel, et PyPy consomme plus de RAM que CPython (800Mo et 270Mo).
      Bref, les 120Mo pour le problème à résoudre sont assez raisonnables, on est loin du OOM.

      • Yth.

      • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

        Posté par  (site web personnel) . Évalué à 4.

        Et si à chaque branchement :

        • on teste avec une source en bon état.
        • si on a des solutions, alors on sait que l'indice suivant pouvait être décalé d'un cran > vers la gauche, donc on peut multiplier par deux !
        • sinon on teste le chemin avec une source endommagée.

        Ça va beaucoup plus vite, beaucoup beaucoup.
        Mais c'est faux, il va falloir encore plus d'intelligence, de ruse, pour comprendre les effets de bords, pourquoi ça ne fonctionne pas.

        En fait je ne vois pas pourquoi ce serait vrai. Si tu as des solutions avec une source inconnue donnée considérée comme en bon état, il n'y a aucune raison qu'en prenant ces solutions, et en les décalant d'un cran vers la gauche, ça corresponde toujours au schéma de la ligne donnée.

        • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

          Posté par  (Mastodon) . Évalué à 3.

          Tu as des sources inconnues.
          Et un indice au bout, puisque tu as remplacé récursivement un maximum de sources inconnues en sources actives.
          Tu peux décaler ton indice vers la gauche pour chacune des sources inconnues que tu as traversé.
          Et à chaque fois tu doubles le nombre de chemin possible après ton indice.

          Mais il faut bien vérifier que tu ne prends pas des sources actives pour des sources inconnues rendues actives.
          Et puis il y a d'autres cas où en décalant suffisamment vers la gauche, tu libères de la place pour faire plus de chemins à droite parce que l'indice suivant peut « sauter » à gauche au dessus d'un trou de sources actives.

          Bon, je ne sais pas si c'est clair, mais j'ai exploré ça en essayant de voir si j'arrivais à trouver les conditions pour savoir quand ça fonctionne ou pas. Le premier problème soulevé est assez simple à résoudre, mais le second pas du tout.
          Et ça devient compliqué de savoir quand on doit finalement explorer une nouvelle branche ou pas, mais il suffit de regarder l'indice suivant, puisque tout se fera ensuite de proche en proche.

          C'est à ce moment là que j'ai réalisé que mon idée était équivalente à « on se moque de ce qui a été fait à gauche, tout ce qui compte c'est où on en est précisément à la position actuelle », et là l'utilisation du cache était évidente.

          Exemple ??.?#? 1,2, tu as .#..##, .#.##., #...## et #..##..
          Quand tu es sur le troisième ? en 4è place, ce que tu vas trouver derrière c'est .## ou ##., et ça ne dépend pas du tout de ce qui s'est passé avant, soit .#. ou #...
          donc dans ta récursion, quand tu vas explorer .#. et #.., le calcul de ce qui se passe à droite va être strictement le même, tu auras 2 chemins : .## et ##., inutile de recalculer, donc l'utilisation d'un cache devient la bonne façon de faire, puisqu'on sait qu'on va passer notre temps à recalculer la même chose.

          • Yth.

      • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

        Posté par  (site web personnel) . Évalué à 4.

        Et donc voici ma solution, en python, et là encore, de façon surprenante, PyPy est quasiment équivalent à CPython, malgré les gros gros calculs !

        Ça ne m'étonne pas trop. Les gros calculs en question sont surtout des appels de fonctions, des branchements, des tests et des additions d'entiers. Je doute que ça soit les points forts de PyPy, si ?

        • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

          Posté par  (Mastodon) . Évalué à 3.

          Ouaip.

          Pour le moment, PyPy n'a été efficace qu'en jour 10 dans mes algos.
          Et c'est parce que j'ai opté pour une exploration de cases adjacentes non optimisée, avec des gros ensembles, et des traitements de masses.
          Je divise par 7 la durée avec PyPy, mais en optimisant, sans changer de méthode de résolution, peut-être que j'aurais pu faire mieux et que la différence aurait été plus faible.

          Soit les algos de l'an passés s'y prêtaient plus, soit je codais comme un bourrin, ça m'avait semblé plus souvent utile.
          Faut dire, pour l'instant, je n'ai que deux programmes qui mettent plus d'une seconde à se terminer.

          • Yth.

      • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

        Posté par  (site web personnel) . Évalué à 5.

        Ah, je crois que j'ai trouvé ce qui consomme de la mémoire dans ton cache. Et qui doit peut-être pas mal le ralentir aussi. Tu as self parmi les arguments de la fonction sur laquelle le cache travaille.

        Intuitivement, je dirais que pour un maximum d'efficacité, il faut minimiser les arguments d'une fonction sur laquelle on veut appliquer un cache. Quitte à définir une fonction auxiliaire locale et que ce soit celle-là qui soit cachée.

        • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

          Posté par  (Mastodon) . Évalué à 3.

          Et bien après vérification, tu as amplement raison.
          Avec MUL = 10

          • Cpython + self 6,03s et 326Mo
          • Cpython - self 3,22s et 49Mo
          • PyPy + self 5,34s et 847Mo
          • PyPy - self 3,96s et 91Mo

          On gagne largement du temps, et énormément de la RAM.
          Finalement la résolution prend 1,14s et 16Mo ce qui est largement petit.

          Côté code c'est facile :

            def run(self):
    @cache
    def _run(pos, clue, clue_id, force_value=0):
      [on remplace juste les self._run() par _run()]
    return _run(0, -1, 0, 0)

          Bien vu, merci, je garderai ça en tête !
          - Yth.

          • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

            Posté par  . Évalué à 2. Dernière modification le 16 décembre 2023 à 00:29.

            Je met mon message en réponse à vous 2 au cas où vous auriez un peu de temps. Je bute sur la partie 2 et je voudrais pas lire une solution directement donc j'ai essayé de ne lire que le minimum de vos échanges pour savoir si vous aviez une solution vraiment plus efficace que la mienne et c'est le cas.

            Pour la partie 1 j'ai fais du bête de chez bête j'itère de 0 à 2 puissance le nombre de ? et je place de # là où j'ai des 1 et des . là où j'ai des 0 dans le nombre courant.

            Évidement O(2n) ça marche pas pour la partie 2. J'ai repris la question autrement et je conçois les solutions possibles comme un arbre binaire je fais un parcours en largeur de l'arbre pour pouvoir couper les branches dès que je vois qu'elles ne marchent pas.

            Si je montre ça en pseudo code python ça donne :

            paths=['???.###????.###????.###????.###????.###']

result=0
while len(paths) > 0:
    current_path=pop(paths)
    switch one_step(current_path, [1,1,3,1,1,3,1,1,3,1,1,3,1,1,3]:
        case Success:
            result += 1
        case Fail:
            pass
        case Path(p1, p2):
            paths.append(p1)
            paths.append(p2)

            avec one_step() qui vérifie s'il y a encore des ? si ce n'est pas le cas il vérifie si c'est bon ou non et renvoie Success/Fail

            s'il reste des ? il vérifie si c'est partiellement valide (il ne vérifie pas que tous les blocs sont présents) si ça ne l'est pas Fail si oui il renvoie la chaine qu'il a en argument 2 fois : une en ayant remplacé le prochain ? par un # et une ou c'est par un .

            Pour moi je suis en O(log2(N)) et ça marche bien sur l'exemple mais pas du tout sur le puzzle.

            Je suis complètement à côté de la plaque ? (là ça tourne depuis 23 minutes… :( )

            https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

            • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

              Posté par  . Évalué à 2.

              J'ai mal calculé la complexité du premier, mais je pense que mon calcul de validation partielle pourrait être plus agressif (pour le moment il s'arrête au premier ?, alors qu'il pourrait regarder le reste. Je vois au moins 1 raccourcis : considérer tous les ? comme des . et voir si c'est valide (au quel cas on s'arrête immédiatement) ou partiellement valide (et là on continue).

              En l'écrivant je me dis que la validation partielle pourrait indiquer jusqu'où est-ce que la validation est exact et que ça permettrait de faire des sauts dans l'arbre.

              https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

            • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

              Posté par  (Mastodon) . Évalué à 2.

              Déjà c'est un problème où tu as absolument besoin d'un cache, sinon ça explose.
              Si tu considères ton problème en fixant des états pour tes ? de gauche à droite, ce qui se passe à droite de ton ? actuel ne dépend que du nombre d'indices (groupes de valves endommagées) restant à placer.
              C'est ça qui te permet de simplifier, et de cumuler tout tes chemins possibles à droite de là où tu en es, avec ce que tu es en train de faire à gauche, mais sans les recalculer.

              En virant le cache, je ne sais pas si j'arrive à obtenir la réponse en repliant 4 fois !
              5 c'est pas la peine…

              • Yth.

              • [^] # Re: Rien de vraiment compliqué, il faut juste utiliser tout ce qu'on sait faire.

                Posté par  . Évalué à 2.

                Ah oui c'est un cache des branches de l'arbre.

                J'aimerais bien tout de même aller plus loin dans l'approche constructiviste. Voir jusqu'où ça peut mener. Il y a un paquet de possibilité d'optimisations, mais ça augmente la complexité algorithmique de l'implémentation.

                Je vais par contre mettre ça de côté, vu le retard que j'ai et mon manque de temps…

                Merci beaucoup je vais prendre le temps de lire vos échanges.

                https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

  • # Solution en Haskell

    Posté par  . Évalué à 4.

    Solution en Haskell par programmation dynamique.
    La partie 1 prend 5ms et la partie 2 prend 30ms

    import           AOC.Prelude
import           AOC (aoc)
import           AOC.Parser (Parser, sepEndBy1, some, eol, decimal, hspace)
import qualified Data.Vector as V
import           Data.Array (listArray, range, (!))

data Spring = Operational | Damaged | Unknown deriving (Eq, Show)
type Row = ([Spring], [Int])

parser :: Parser [Row]
parser = row `sepEndBy1` eol where
    row = (,) <$> some spring <* hspace <*> decimal `sepEndBy1` ","
    spring = Operational <$ "." <|> Damaged <$ "#" <|> Unknown <$ "?"

countArrangements :: Row -> Integer
countArrangements (springs, groups) = arr ! (0, 0) where
    vsprings = V.fromList (springs ++ [Operational])
    springsLength = V.length vsprings
    vGroups = V.fromList groups
    groupsLength = V.length vGroups
    nextOperational = V.generate springsLength \i ->
        if vsprings V.! i == Operational then i else nextOperational V.! (i+1)
    arr = listArray bds [
        let currentSpring = vsprings V.! pos
            currentGroupSize = vGroups V.! groupPos
        in
        if pos == springsLength then
            if groupPos == groupsLength then 1 else 0
        else
            let nextOp = nextOperational V.! pos
                pos' =  pos + currentGroupSize
                x = if currentSpring /= Damaged then arr ! (pos + 1, groupPos) else 0
                y = if groupPos < groupsLength && nextOp >= pos' && vsprings V.! pos' /= Damaged
                    then arr ! (pos' + 1, groupPos + 1)
                    else 0
                in x + y
        | (pos, groupPos) <- range bds
        ]
    bds = ((0, 0), (springsLength, groupsLength))

part1 :: [Row] -> Integer
part1 = sum . map countArrangements

part2 :: [Row] -> Integer
part2 = sum . map (countArrangements . unfold) where
    unfold = bimap (intercalate [Unknown] . replicate 5) (concat . replicate 5)

    • [^] # Re: Solution en Haskell

      Posté par  . Évalué à 2.

      Quelques commentaires sur ce que j'ai fait.

      Tout d'abord, par soucis de simplicité, je rajoute un symbole Operational (".") à la fin de la liste des sources.
      Ensuite, je calcule un tableau nextOperational qui pour chaque index dans la liste des sources me renvoie l'index de la prochaine source opérationnelle. Ca se fait aisément en temps linéaire et ça me permet d'optimiser le temps de calcul dans la programmation dynamique.

      Maintenant vient la programmation dynamique.
      Je note springs et groups la liste des sources et des groupes respectivement.
      J'essaie de résoudre récursivement le problème suivant:
      étant donné pos et groupPos combien y a-t-il d'arrangemnts dans la sous liste springs[pos:] satisfaisant les contraintes groups[groupPos:]. Je note f une telle fonction.
      Le cas de base est quand pos == taille(springs). Si groupPos = taille(groups), ça veut dire que les listes springs[pos:] et groups[groupPos:] sont vides. Ca match bien donc f(pos, groupPos) = 1. Sinon, f(pos, groupPos) = 0.
      Dans le cas récursif, il y a deux possibilités (non mutuellement excluses).
      Si la source à la position springs[pos] est opérationnelle ou inconnue alors je rajoute
      f(pos, groupPos+1) à f(pos, groupPos).
      L'autre cas est quand le bloc groups[groupPos] peut rentrer à la position pos.
      Pour vérifier cela, j'utilise mon tableau nextOperational et le fait donc en temps constant.
      Si le bloc rentre, je rajoute f(pos+groups[groupPos]+1, groupPos+1) à f(pos, groupPos).

      Je ne vais pas rentrer dans les détails mais j'obtiens au final une complexité en O(|springs| . |groups|) et du coup une résolution en 30ms pour la partie 2.

      • [^] # Re: Solution en Haskell

        Posté par  (Mastodon) . Évalué à 3.

        Comme je n'ai jamais codé en Haskell, je ne pige pas toutes les subtilités du code.
        Mais c'est un langage fonctionnel, donc il va de lui-même optimiser les récursion ?
        En fait t'as une fonction pure, c'est à dire qu'avec les mêmes données en entrées ça donne le même résultat, et Haskell fait de lui-même les optimisations, l'éventuel cache, et zou ?

        Ça doit revenir à peu de chose près au même que ce à quoi on est arrivés en Python avec Tanguy, en utilisant le cache : ne pas recalculer plein de fois exactement la même chose.

        J'ai repris l'idée du nextOperational et modifié mon code pour placer les intervalles de sources endommagées directement, avec le même nextOperational, et globalement je double la vitesse d'exécution en réduisant la RAM.

        • Yth.

        • [^] # Re: Solution en Haskell

          Posté par  . Évalué à 1.

          En fait, j'utilise des lazy arrays à deux dimensions (la variable arr).

          Je peux écrire un truc du genre à l'initialisation du tableau.
          arr[x][y] = quelque chose avec arr[x+1][y].
          Si arr[x+1][y] n'est pas encore calculé, il va le faire et le stocker en mémoire dans le tableau. Sinon, il renvoit directement la valeur.

          Je pense que c'est similaire au cache en python, comme tu disais.

          • [^] # Re: Solution en Haskell

            Posté par  (Mastodon) . Évalué à 2.

            Ouais, ça revient à ça, ton tableau est un générateur de valeur et il ne prend que ce que tu vas chercher.
            En Python, la fonction est un générateur de valeur, et elle a un cache (un tableau en deux dimensions aussi, quand on fait bien les choses) pour te retourner directement une valeur déjà calculée.

            • Yth.

  • # J'en ai bavé.

    Posté par  . Évalué à 1.

    6h au total ! J'ai commencé par prendre le problème de travers.

    J'ai fait substitution récursive des '?' ,c'était mon erreur.

    C'est après que j'ai compris qu'il fallait distribuer les espaces restant entre les groupes.

    çà permet d'exprimer le problème avec une fonction recursive pour lequel on peut mettre en place un cache des valeurs par rapport au reste à évaluer.

    Environ 414ms sur ma machine (après avoir commenté les println)

    package aoc2023;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.atomic.AtomicLong;

public class Aoc2023s12v4 { 
    public static record Evaluation(List<Integer> groupes, int totalDot, String dstSpring) {                    
    }

    public static Evaluation[] cache = new Evaluation[1_000_000];
    public static long[] cacheValue = new long[1_000_000];

    public static void main(String[] args) {                        
        assert (countExpandedPossibility("??# 2") == 16L);

        assert (countExpandedPossibility("???.### 1,1,3") == 1L); 
        assert (countExpandedPossibility(".??..??...?##. 1,1,3") == 16384L);
        assert (countExpandedPossibility("????.#...#... 4,1,1") == 16L);
        assert (countExpandedPossibility("????.######..#####. 1,6,5") == 2500L);
        assert (countExpandedPossibility("?###???????? 3,2,1") == 506250L);
        //assert (countExpandedPossibility("???.?#?????##?#????? 1,2,7,1") == 506250L);

        System.out.println("-----------          -----------");
        System.out.println("----------- END TEST -----------");
        System.out.println("-----------          -----------");


        try (Scanner in = new Scanner(Aoc2023s12v4.class.getResourceAsStream("res/t12.txt"))) {
            List<String> map = new ArrayList<>();

            while (in.hasNext()) {
                String row = in.nextLine();
                map.add(row);
            }

            long count = 0;

            for (String row : map) {
                count += countExpandedPossibility(row);
            }
            System.out.println(count);
        }
    }
        private static long countExpandedPossibility(String row) {
        String srcSprings = row.split(" ")[0];
        int[] srcRules = Arrays.stream(row.split(" ")[1].split(",")).mapToInt(s -> Integer.parseInt(s)).toArray();

        long r = countExpanded(srcSprings, srcRules, 5);
        System.out.println(r);
        return r;
    }
        private static long countExpanded(String srcSprings, int[] srcRules, int i) {
        int[] dstRules = new int[srcRules.length * 5];
        for (int x = 0; x < i; x++) {
            for (int y = 0; y < srcRules.length; y++) {
                dstRules[x * srcRules.length + y] = srcRules[y];
            }
        }

        String dstSpring = srcSprings;
        for(int x=0;x < i-1;x++) {
            dstSpring += '?' + srcSprings;
        }               
        System.out.println("Pattern:");
        System.out.println(dstSpring);

        int total = Arrays.stream(dstRules).sum();
        int totalDot = dstSpring.length() - total;

        System.out.println(total + " + " + totalDot + " => " + dstSpring.length());


        return distributeDotBetweenGroup(
                Arrays.stream(dstRules).mapToObj(Integer::valueOf).toList(),
                true,
                totalDot,               
                dstSpring);             
    }
        private static long distributeDotBetweenGroup(List<Integer> groupes, boolean first, int totalDot, String dstSpring) {           
        if(0 == groupes.size() ) {
            String current = "";
            for(int j=0;j < totalDot;j++) {
                current += '.';
            }
            //System.out.println(sb);
            if(match(current, dstSpring)) {             
                return 1;           
            }
            return 0;
        }

        int size = groupes.get(0);

        StringBuilder sb = new StringBuilder();
        long sum  = 0;
        for(int ud=(first? 0:1);ud <= totalDot;ud++) {
            sb.setLength(0);            
            for(int j=0;j < ud;j++) {
                sb.append('.');             
            }           
            for(int j=0;j < size;j++) {
                sb.append('#');
            }


            if(! match(sb, dstSpring, sb.length())) {
                continue;
            }

            Evaluation eva= new Evaluation(groupes.subList(1, groupes.size()), totalDot-ud, dstSpring.substring(sb.length()));

            int indexCache =Math.abs(eva.hashCode())% cache.length;
            if(cache[indexCache] !=null && cache[indexCache].equals(eva)) {
                sum += cacheValue[indexCache];
            } else {
                long i= distributeDotBetweenGroup(eva.groupes, false, eva.totalDot, eva.dstSpring);
                cache[indexCache] = eva;
                cacheValue[indexCache] = i;
                sum += i;
            }           

        }
        return sum;

    }
        private static boolean match(String test, String refPattern) {
        if(test.length() != refPattern.length()) {
            return false;
        }
        for (int x = 0; x < test.length(); x++) {
            char c = refPattern.charAt(x);
            if (c != '?') {
                if (test.charAt(x) != c) {
                    return false;
                }
            }
        }
        return true;
    }
        private static boolean match(StringBuilder test, String refPattern, int wi) {       
        for (int x = 0; x < wi; x++) {
            char c = refPattern.charAt(x);
            if (c != '?') {
                if (test.charAt(x) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}

  • # recurcif et cache

    Posté par  . Évalué à 1.

    J'ai eu du mal sur cette partie.
    J'ai commencé par une fonction récursive, finalement assez simple à coder.
    Par contre, au niveau repliage, au bout du 2 ou 3e ca ne finissait pas.
    En regardant les traces, j'ai vu qu'il faisait plein de fois la meme chose et j'ai pensé au cache.
    Et la, quasiment instantané même avec un pliage x5.
    Je pensais limiter le cache en taille pour éviter une trop grande conso mémoire mais j'ai tenté le coup sans le réduire et c'est passé sans pb !
    Mais plusieurs heures se sont écoulées avant que je trouve ça…

Suivre le flux des commentaires

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