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

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.