Yth a écrit 2692 commentaires

Pour la première partie, je fais des jolies eval avec des fonction lambda, pour avoir une résolution simple et élégante.

from sys import stdin
from dataclasses import dataclass
data = stdin.read().strip().splitlines()

class Workflow:
  def __init__(self, x):
    def dest(r):
      if r == 'A':
        return None  # No more rules, accepted
      if r == 'R':
        return False  # Rejected
      return r  # Next rule
    self.name, rules = line.strip("}").split("{")
    rules = [_.split(":") for _ in rules.split(",")]
    self.default = dest(rules.pop()[-1])
    self.rules = {eval(f"lambda x: x.{t}"): dest(d) for t, d in rules}
    self.infos = [(t[0], t[1], int(t[2:]), dest(d)) for t, d in rules]  # for ex2
  def __call__(self, part):  # Applying this whole workflow to a part
    for rule, dst in self.rules.items():
      if rule(part):
        return dst
    return self.default

@dataclass(frozen=True)
class Parts:
  x: int = 0
  m: int = 0
  a: int = 0
  s: int = 0
  @property
  def val(self):
    return self.x + self.m + self.a + self.s
  def __bool__(self):  # Following workflows until accepted or rejected
    next = 'in'
    while next:  # Neither None nor False
      next = workflows[next](self)
    return next is None  # Acepted

# Data analysis
workflows = {}
parts = False
for line in data:
  if not line:
    parts = []
    continue
  if parts is False:
    w = Workflow(line)
    workflows[w.name] = w
  else:
    parts.append(eval(f"Parts({line[1:-1]})"))

# 1st problem
ex1 = sum(part.val for part in parts if part)

Pour le second, je suis tombé dans le piège : < et > ne sont pas l'inverse l'un de l'autre, j'ai souffert pour voir ça :(
Là on considère des range, des intervalles. Comme on code en python, [1, 4000] ça va être range(1, 4001), d'où les 4001 dans le code.
Pour l'algo, je considère un état : 4 ranges pour x, m, s et a, un workflow et une étape dans le workflow, ce qui donne donc une règle (rule).
Je prends mes états courants, je leur applique une règle ce qui va diviser chacun de ces états en au mieux deux états : celui qui respecte la règle en cours, et celui qui ne la respecte pas. Chacun progressant, soit vers une nouvelle règle, soit vers l'étape suivante du workflow.
Je trie les états ayant une règle à appliquer pour mon itération suivante, et je garde de côté les états étant au stade accepté. Les rejetés sont donc abandonnés là.

Après il reste à bien lire l'énoncé : non, on ne cherche pas la valeur de toutes les pièces qui sont valables, mais juste à les dénombrer, donc il suffit de multiplier entre eux les tailles des 4 intervalles d'un état accepté.

Comme on découpe toujours en deux morceaux disjoints, nos états ne se chevauchent jamais, donc on peut tous les dénombrer et additionner.

@dataclass
class PartRange:
  x: tuple = (1, 4001)
  m: tuple = (1, 4001)
  a: tuple = (1, 4001)
  s: tuple = (1, 4001)
  rule: str = 'in'
  step: int = 0

  def split(self):
    rule = workflows[self.rule]
    if self.step == len(rule.infos):
      self.rule, self.step = rule.default, 0
      yield self
      return
    key, test, num, dest = rule.infos[self.step]
    if test == ">":  # ...
      num += 1
    a, b = getattr(self, key)
    if num > a:  # range before num
      new = self.__dict__.copy()
      new[key] = (a, num)
      new["rule"], new["step"] = (dest, 0) if test == "<" else (self.rule, self.step + 1)
      yield PartRange(**new)
    if num <= b:  # range after num
      new = self.__dict__.copy()
      new[key] = (num, b)
      new["rule"], new["step"] = (dest, 0) if test == ">" else (self.rule, self.step + 1)
      yield PartRange(**new)
  @property
  def value(self):
    x = len(range(*self.x))
    m = len(range(*self.m))
    a = len(range(*self.a))
    s = len(range(*self.s))
    return x * m * a * s

parts = [PartRange()]
accepted = []
while parts:
  parts = [part for _ in parts for part in _.split()]
  accepted.extend(_ for _ in parts if _.rule is None)  # Saving accepted
  parts = [_ for _ in parts if _.rule]  # Pruning accepted and rejected

ex2 = sum(_.value for _ in accepted)

Le temps d'exécution est négligeable, ~90ms.
J'ai quand même pas été super rapide pour débugger mes âneries.

Yth.

Hier encore, j'ai sévèrement lutté pour coder : repas d'entreprise en montagne (dur la vie…), donc j'ai eu rien de temps pour coder, à moitié sur PC, à moitié sur téléphone.
En pratique, j'ai honte un peu, j'ai fini de coder en voiture (au volant oui, oui), avec un algo sous-optimisé qui a mit un bon quart d'heure à s'exécuter, et m'a sorti le bon résultat.
Le même code prend 70s sur mon petit PC.

Mais j'ai eu le temps de réfléchir à une autre approche, que je n'avais pas eu le temps de coder, mais que j'ai validé le soir.
Et là c'est magique, une fonction de 12 lignes, 3 lignes pour les deux jeux de données, et 2 structures constantes, allez 22 lignes avec le she-bang python3.
Le résultat sort en rien de temps, O(n).

L'idée c'est de considérer une unique zone rectangulaire qu'on va agrandir ou rétrécir au fur et à mesure de l'exploration des sommets, en notant ce qu'on a tranché, ou rajouté.
Voilà les données de test et quelques itérations :

####### 0# 1####### 2####### 3#####__ 4##### 5#####** 8##
#+++++#              #######  #####__  #####  #####**  ##
###+++#              #######  #####__  #####  #####**  ##
..#+++#              #######  #####__  #####  #####**  ##
..#+++#              #######  #####__  #####  #####**  ##
###+###              #######  #####__  #####  #####**  ##
#+++#..                                #####  #####**  ##
##++###                                #####  #######  ##
.#++++#                                                .*
.######                                                .*

Étape 0 j'ai la zone (0, 0) -> (0, 0), facile.
Étape 1 j'étends vers la droite de 6 cases, rien à faire, ma zone fini en (6, 0), je prends tout.
Étape 2, pas mieux, j'étends vers le bas jusque (6, 5), je prends encore tout (je ne sais pas encore ce qui se passe à la fin, on enlèvera plus tard, sommet par sommet).
Étape 3, je réduis vers la gauche vers (4, 5) ! Là je perd une zone, indiquée avec des _, elle fait 12 cases, donc je la supprime du problème mais je note une superficie de 12.
Étape 4, j'étends vers le bas, rien à dire, ma zone se termine en (4, 7).
Étape 5, j'étends vers la droite encore, jusque (6, 7), et là on voit bien qu'on a agrandit dans une zone de vide, les *, il faut les retirer, mais attention, les # en bas sont l'épaisseur du trait, on les garde ! Donc on note que notre superficie est de 14 trop grand maintenant, notre superficie de côté est donc 12-14 = -2, ce qui correspond bien aux deux . à droite du résultat cherché.
Je saute, étape 6 on descends vers (6, 9) rien à faire, étape 7 on va vers la droite jusque (1, 9) donc on ajoute à notre superficie stockée 50 cases, on est à 48.
Étape 8, on remonte vers (1, 7) ! On doit considérer l'épaisseur du trait qui va disparaître, ici 2, mais le reste était en dehors de notre résultat, donc la superficie augmente simplement de 2 pour arriver à 50.

On a vu les 4 règles, on termine les 14 étapes ainsi :
Étape 9 : gauche de 1 vers (0, 7) superficie + 8 = 58
Étape 10 : haut de 2 vers (0, 5) superficie + 2 = 60
Étape 11 : droite de 2 vers (2, 5) superficie - 10 = 50
Étape 12 : haut de 3 vers (2, 2) superficie + 3 = 53
Étape 13 : gauche de 2 vers (0, 2) superficie + 6 = 59
Étape 14 : haut de 2 vers (0, 0) superficie + 2 = 61
Et enfin, il nous reste la zone qui se termine en (0, 0) et qui fait donc # et a une superficie de 1.
J'ajoute 1 : 62, youpi.

Cet algo est pensé sur un départ à gauche et en bas, avec le (0, 0) qui est dans le coin.
Pour valider que ça marche un peu partout, surtout en débordant à gauche ou en haut, on peut constater que les instructions peuvent cycler, on peut commencer à la seconde instruction et reboucler jusque la 1ère, etc.
Donc j'ai validé avec toutes les positions de départ : 62 tout le temps, on est bons.
Ok, bah plus qu'à tester en grand et sur données réelles : ça marche, bingo.

Le code :

from sys import stdin
import re
data = re.findall(r"([UDLR]) (\d+) [(]#([0-9abcdef]+)[)]", stdin.read().strip())
DIR = [(1, 0), (0, 1), (-1, 0), (0, -1)]
Dir = {"R": DIR[0], "D": DIR[1], "L": DIR[2], "U": DIR[3]}
data1 = [(int(b), Dir[a]) for a, b, _ in data]
data2 = [(int(d[:-1], 16), DIR[int(d[-1])]) for *_, d in data]
def run(d):
  x = y = s = 0
  for n, (a, b) in d:
    x1, y1 = x + n * a, y + n * b
    if a == -1:
      s += (y + 1) * (x - x1)
    elif a == 1:
      s -= y * (x1 - x)
    elif b == -1:
      s += y - y1
    x, y = x1, y1
  return s + 1
ex1 = run(data1)
ex2 = run(data2)

Voilà, voilà, sans théorème, sans connaissances particulières, sans module externe, juste des méninges torturées pendant des heures à ne pas pouvoir coder les algos qui tournent dans la tête.
Inutile de dire que le temps d'exécution c'est l'overhead python, et c'est tout.

Par contre difficile de bien coder ça en vrac, dehors, dans la neige et le froid, avec un téléphone, on est mieux sur un bureau, avec un papier, et un clavier.

• Yth.

J'ai encore codé sur téléphone aujourd'hui, et ça m'a encore pas trop réussi. Le weekend est pas mon ami cette année, et je sais pas comment je vais faire les 23, 24 et 25, mais bon.

J'ai donc tout fait de tête, à inventer des algos avec mes gros doigts sur mon petit écran, sans rien réutiliser de pratique que du python chocolat, ou vanille peut-être…

Et ça a bien bien foiré.
Parce que le coup de la position et du booléen horizontal/vertical je l'ai vu direct, mais pour l'implémentation, j'ai tout raté, et laissé tomber.
J'arrivais pas à modéliser, trop long, trop chiant d'écrire sur le petit écran fêlé.
Et pourtant j'avais presque le résultat de la partie 1 très vite, mais j'avais 104, 107, 111, jamais 102, donc un bug fondamental dans l'algo quelque part.

Et au bout du compte, sur données réelles, j'ai 12s sur l'exo 1 et 5s sur l'exo 2, donc un algo absurde mais qui roule mieux sur le second exercice que sur le premier.
J'ai eu très très peu à adapter pour résoudre l'exo 2, et le rendre efficace pour les deux exercices, ce truc m'a pris 5 minutes et j'ai eu directement la bonne réponse.

Mais à l'évidence, il y a un truc dans mon approche que j'ai raté, parce que ça a beaucoup planté quand même, et je n'ai jamais réussi à raccrocher le fait qu'on s'en moque d'arriver par la droite ou la gauche puisqu'on va à la fois en haut et en bas après dans les deux cas.

Bref, code pourri, beaucoup de temps passé à me casser les orteils, et les dents, sur le périphérique mobile, et une conclusion : c'est vraiment pas un bon outil de programmation.

Bilan j'ai repris mon truc au propre, sur un ordinateur, et j'ai réussi ma modélisation avec uniquement horizontal ou vertical, en refaisant ça calmement, et avec un vrai clavier.

Bah ça fonctionne, et je tombe à 7s et 4s.
On notera que j'ai tellement mal codé mon bidule que PyPy est indispensable , en CPython on monte à 1 minute 42, c'est dire si c'est moche.
Et après, au lieu de stocker mes scores dans un dictionnaire d'états (un dataclass(int x, int y, bool horizontal)) j'ai repris un tableau en x*y*horizontal, et l'indexation étant nettement plus efficace comme ça on tombe à 6s au total.
Ça reste pourri.
Avec un petit compteur pour comptabiliser les appels à mon itérateur d'Explorateur, j'en ai 1 100 226 sur la partie 1 et 247 885 sur la 2.

from sys import stdin
from dataclasses import dataclass
data = stdin.read().strip().splitlines()
plan = [[int(_) for _ in line] for line in data]
WIDTH = len(plan[0])
HEIGHT = len(plan)
MAX = sum(sum(_) for _ in plan)
@dataclass(frozen=True)
class Explorer:
  x: int = 0
  y: int = 0
  h: bool = True
  SKIP = 0
  NB = 3
  @property
  def val(self):
    return plan[self.y][self.x]
  @property
  def score(self):
    return SCORE[self.y][self.x][self.h]
  def __repr__(self):
    return f"{self.x:02}:{self.y:02}{'↔' if self.h else '↕'}{self.score:03}"
  def __bool__(self):
    return self.x >= 0 and self.y >= 0 and self.x < WIDTH and self.y < HEIGHT
  def __add__(self, n):
    v = not self.h
    return Explorer(self.x + n * self.h, self.y + n * v, v)
  def __sub__(self, n):
    v = not self.h
    return Explorer(self.x - n * self.h, self.y - n * v, v)
  def __call__(self, score):
    score += self.val
    if self.score < score:
      return False, score
    SCORE[self.y][self.x][self.h] = score
    return True, score
  def up(self, n=1):
    x = self
    s = self.score
    for _ in range(1, n + 1):
      x = self + _
      if not x:
        return False
      s += x.val
    return s
  def down(self, n=1):
    x = self
    s = self.score
    for _ in range(1, n + 1):
      x = self - _
      if not x:
        return False
      s += x.val
    return s
  def __iter__(self):
    s = self.up(self.SKIP)
    if s is not False:
      n = [self + i for i in range(self.SKIP + 1, self.SKIP + self.NB + 1) if self + i]
      for x in n:
        b, s = x(s)
        if b:
          yield x
    s = self.down(self.SKIP)
    if s is not False:
      n = [self - i for i in range(self.SKIP + 1, self.SKIP + self.NB + 1) if self - i]
      for x in n:
        b, s = x(s)
        if b:
          yield x

def run(skip, nb):
  Explorer.SKIP = skip
  Explorer.NB = nb
  states = {Explorer(0, 0, True), Explorer(0, 0, False)}
  SCORE[0][0] = [0, 0]
  while states:
    states = set(ns for s in states for ns in s)
  return min(SCORE[-1][-1])

SCORE = [[[MAX, MAX] for __ in range(WIDTH)] for _ in range(HEIGHT)]
ex1 = run(0, 3)

SCORE = [[[MAX, MAX] for __ in range(WIDTH)] for _ in range(HEIGHT)]
ex2 = run(3, 7)

Allez, demain, je dois tout faire entre 9h30 et 10h30, sur un PC qui n'est pas à moi :)

• Yth.

J'ai encore codé en marchant, sur mon téléphone.
D'ailleurs, pour les masochistes dans mon genre, je conseille : Qpython, on ne le trouve pas sur fdroid, je ne l'ai pas non plus trouvé sur Aurora, mais on peut installer l'apk depuis github. Il ne demande aucune autorisation, mais ne fonctionnera pas sans un accès aux fichiers, qu'on doit activer soi-même : il installe des trucs dans un répertoire accessible ([userdata]/qpython/).
C'est bien moins casse-pied qu'un éditeur en ligne, plus rapide, et on peut partager facilement les fichiers avec un PC par exemple avec Syncthing

Trêve de publicités, ce genre d'algo, à débugger comme un brontosaure, sur un téléphone, c'est galère, et je n'ai vraiment pu le finir qu'une fois devant un vrai clavier, mais j'étais pas loin !
Par contre, pas lourd d'optimisations, j'avais pas le temps d'y réfléchir, par chance le code tourne malgré tout en 3,5 secondes, donc ça va.
Après trois secondes de réflexion, je me suis dis qu'un cache serait inutile, en pratique un cache n'est pas entièrement inutile, et me fait redescendre à 1,95s, sachant qu'il est assez crétinement utilisé.

Bref, voici du code :

from sys import stdin
from dataclasses import dataclass
from functools import cache
data = stdin.read().strip().splitlines()
WIDTH = len(data[0])
HEIGHT = len(data)

@dataclass(frozen=True)
class coord:
  x: int = 0
  y: int = 0
  def __add__(self, o):
    return coord(self.x + o.x, self.y + o.y)
  def __bool__(self):
    return self.x >= 0 and self.y >= 0 and self.x < WIDTH and self.y < HEIGHT
  def __repr__(self):
    return f"{self.x}:{self.y}"

class direction(coord):
  def __repr__(self):
    return self.s

@cache
def move(*beams):
  for b, d in beams:
    m = data[b.y][b.x]
    if m == ".":
      yield b + d, d
    elif m == "|":
      if d.y:
        yield b + d, d
      else:
        yield b + N, N
        yield b + S, S
    elif m == "-":
      if d.x:
        yield b + d, d
      else:
        yield b + E, E
        yield b + W, W
    elif m == "/":
      d = {N: E, S: W, E: N, W: S}.get(d)
      yield b + d, d
    elif m == "\\":
      d = {N: W, S: E, E: S, W: N}.get(d)
      yield b + d, d

def energize(p, d):
  beams = [(p, d)]
  visited = set()
  while beams:
    visited.update(beams)
    beams = set((b, d) for b, d in move(*beams) if b)
    beams.difference_update(visited)
  return len(set(p for p, d in visited))

# cleaner code, cleaner debug using Direction class
N, S, E, W = direction(0, -1), direction(0, 1), direction(1, 0), direction(-1, 0)
N.s, S.s, E.s, W.s = "N", "S", "E", "W"

ex1 = energize(coord(0, 0), E)
ex2 = max([
  max(energize(coord(x, 0), S) for x in range(WIDTH)),
  max(energize(coord(x, HEIGHT - 1), N) for x in range(WIDTH)),
  max(energize(coord(0, y), E) for y in range(HEIGHT)),
  max(energize(coord(WIDTH - 1, y), W) for y in range(HEIGHT)),
])

Donc l'idée est un peu la même : on stocke des couples (position, direction), une coordonnée est True si elle n'est pas hors champs, on peut additionner deux coordonnées, les directions sont des coordonnées qui se représentent avec une autre valeur à définir soi-même, et j'ai donc quatre instances N, S, E et W, qui vont simplement s'afficher en N, S, E et W lors des débuggages.
La fonction energize prend un rayon de départ (position, direction), et retourne le nombre de cases allumées, donc c'est la résolution d'un problème n°1, on en a 440 à résoudre pour le n°2.

Après c'est un poil du brute force : on teste vraiment toutes les positions de départ possible.
Et le cache est sur un ensemble de rayons (couple position/direction), donc il n'y a pas tellement de chances de retomber exactement sur le même ensemble (en fait c'est pas si mal), et ça n'optimise pas du tout sur un trajet qu'on retrouverait dans pleins de parcours.
Mais ça divise le temps quasiment par deux, donc ce n'est pas entièrement inutile !

Une meilleure approche serait une fonction qui retourne tous les rayons générés à partir d'un rayon, et là, on sait qu'on va repasser par les mêmes endroits lors de chaque exploration, rayon par rayon quand il y a bifurcation, et ça peut accélérer énormément.
Le terrain faisant 110*110, soit 12100 cases, donc 48400 rayons possibles, la plus grosse exploration en générant déjà 12246 chez moi, on a rapidement fait le tour quand même, et ça peut certainement aller plus vite au bout du compte.

En pratique, ma fonction move est appelée 167654 fois sans cache et 61561 fois avec cache, donc entre 48200 et 61561, ya pas si lourd à gagner que ça. Allez, je passerais allègrement sous la seconde et voilà, rien de plus. Peut-être que l'implémentation réelle montrerait que pas mal de rayons n'existent pas (sont inaccessibles depuis le bord), et qu'on pourrait vraiment y gagner.

Après, c'est assez marrant d'utiliser un cache sur une fonction qui yield, il doit cacher un générateur, ou peut-être toutes les valeurs, sinon ça cache pas, puisqu'un générateur c'est transitoire. Franchement je ne sais pas comment il se débrouille en interne, mais ça fonctionne !

• Yth.

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.

J'ai en effet oublié un terme dans mon calcul de combinaison, qui m'amène plutôt vers les 7e2010.

• Yth ^{^ ^}

Le dictionnaire est utilisé à l'intérieur des boîtes, pour ne pas réinventer tes méthodes Box.remove() ou Box.put().

Je range les lentilles dans un dictionnaire, mais les boîte sont dans une liste : boxes = [{} for _ in range(256)], ou boxes = [OrderedDict() for _ in range(256)] si on veut utiliser ça, mais ça revient au même.
Dans chaque boîte j'ai un dictionnaire {label: lens}

• Yth.

Hmm, on a moins de 100x100 possibilités pour chaque pierre-qui-roule (chez moi c'est 8459).
Mais comme on a quelques 2000 pierres-qui-roulent (2011 dans mes données), ça fait un paquet de combinaisons possibles.
Chez moi ça a l'air d'être de l'ordre de 5e7784, soit… trop.

Mais je pense que ton raisonnement sur pourquoi on en est absolument sûr, est faux.

Perso, je n'ai qu'une double forte suspicion : ça à l'air de boucler à vue de nez, et si ça boucle pas on va flinguer notre CPU, or il y a une solution raisonnable en temps CPU, selon les principes de l'AoC.

• Yth.

En python3 récent (je sais plus trop quelle version, mais c'est pas si récent en vrai), les dict() conservent l'ordre des données.
Donc j'aurais pu utiliser le dict() standard.
J'ai opté pour l'OrderedDict parce que l'énoncé est assez confus, j'avais cru que quand on remplaçait une lentille, elle repassait devant, et l'OrderedDict a une fonction move_to_end pour pile poil ça.
Alors que pas du tout en vrai, c'est vraiment hyper simple et sans subtilité.

Bref, dans mon code on remplace OrderedDict par dict et ça fonctionne pareil.

C'est vraiment le seul point qui m'a un poil ralenti : la lecture, et mauvaise compréhension, de l'énoncé.

• Yth.

from sys import stdin
from collections import OrderedDict
def HASH(step):
  r = 0
  for x in step:
    r = ((r + ord(x)) * 17) % 256
  return r

sequence = stdin.read()).strip().split(",")
ex1 = sum(HASH(step) for step in sequence)
boxes = [OrderedDict() for _ in range(256)]
for step in sequence:
  if step[-1] == "-":
    label = step[:-1]
    boxes[HASH(label)].pop(label, 0)
  else:
    label = step[:-2]
    boxes[HASH(label)][label] = int(step[-1])
ex2 = sum(
  (i + 1) * (j + 1) * lens
  for i, box in enumerate(boxes)
  for j, lens in enumerate(box.values())
)

Si le problème était vraiment très grand, on pourrait mettre un cache sur la fonction HASH, puisqu'on va pas mal tourner avec les mêmes HASH.
Là, bof, ça fait peut-être passer de 0,04+-0,005 à 0,03+-0,005 secondes, autant dire que le CPU a refroidi pendant le traitement.

• Yth, à la rigueur, si j'avais eu ce problème demain, vu que je vais devoir coder sur mon téléphone, en marchant, j'aurais pas été déçu, mais là…

Ouais, faut enregistrer les états après un tour complet pour retourner dans une situation équivalente.
Un tour complet ne dépend que de l'état initial, alors qu'un déplacement c'est l'état initial puis la direction.
Ça marche mais faut enregistrer les deux infos, et comparer les deux infos.

• Yth.

Non, non, j'enregistre un état après un tour complet nord, ouest sud, et est.
Si on retombe sur un état rigoureusement identique, alors on a forcément bouclé, on ne conserve pas d'information d'un tour à l'autre, un tour de manivelle ne dépend que de l'état des pierres-qui-roulent au début du tour.

Ça veut dire qu'après 10 on a forcément 11.

Ya pas possible de se tromper là…

• Yth.

Par contre, on peut noter qu'ici PyPy fait descendre de 1,6s à 0,5s, ce qui n'est pas négligeable du tout, trois fois plus rapide, pas mal.
Avec ou sans cache, on a bien vu qu'il ne servait rigoureusement à rien de toute façon, pas la peine de ressasser hein, j'ai compris.

En modélisant avec un Enum Rock, et en utilisant un tuple au lieu d'une str pour gérer les données (on converti en liste avant de déplacer les pierres puis on remet en tuple, et on calcule un hash d'un tuple de Rock), c'est affreux.
On passe à 4s en python !
Mais on reste à 0,6s en PyPy.

Conclusion: PyPy ne déteste pas la modélisation.

Avec ou sans cache, puisque je vous dis qu'il ne sert absolument à rien, rhaaa !

Et donc après m'être bien pris la tête à virer mes histoires de hashes, tout le cache et essayer de simplifier, on réalise que de toute façon on doit passer par des enregistrements d'états immuables (on ne peut pas states.append(mon état mutable), parce que ça stocke la référence, donc l'état stocké est modifié), et donc permettre à python de calculer un hash, par exemple en stockant un tuple().
Et ça sert à rien, on n'y gagne rien, mon approche initiale était finalement la plus optimisée : rester sur des string, et les transformer en liste pour les modifier puis les recoller à la fin, est plus efficace.
Sauf avec PyPy qui s'en fout, les hashes de str, tuple, les conversions dans un sens, l'autre, retour etc, c'est pareil pour lui, ça prend rien de temps, donc toutes les approches sont équivalentes.

• Yth.

Comme dans tout les films avec une action répétées pleins de fois, comme de lustrer et frotter, ou peindre des palissades, on a une option pointillés, qui permet de sauter des deux-trois premières itérations directement à la dernière, et de constater, ébahis, les résultats de l'entraînement des padawans, devenu des adultes.

Tout ça pour dire que même avec un cache efficace, tester le cache un milliard de fois, même si on ne calcule vraiment que quelques centaines, ou milliers, d'opérations, ça va être très, très, très long.

Ça ne veut pas dire que le cache est inutile, mais totalement insuffisant.
En pratique, que je le mette ou pas, et ce coup-ci j'ai absolument pensé ma modélisation et toutes mes fonctions, pour avoir un cache le plus efficace possible, ben on gagne quedalle en vitesse, et on sagouine même pas sa RAM, en fait, comme j'ai fait ça super bien, le cache, les caches, ben ils utilisent rien en mémoire.

En fait, tout ce qui compte, c'est de faire des cycles, et de voir quand est-ce qu'on retombe sur un état vu précédemment.
Là on a deux informations : les étapes préalables au démarrage d'un cycle de cycles, et la longueur de ce cycle de cycles.
Si quelqu'un pense, là, maintenant, que j'ai mal choisi mes appellations, il a sans doute raison, c'est bien toute la difficulté du choix d'un bon nom de variable, choix qui n'est pas toujours en O(temps disponible).

Chez moi, on calcule 160 cycles, on boucle sur 77 cycles après 83 cycles de mise en jambe.
Donc avec (1 000 000 000 - 83) modulo 77 = 70, on va chercher le 70^ème cycle de notre cycle de cycles, soit le 83+70=153^ème cycle calculé, c'est l'état final, on le pèse.
Et avec les données de test, on retombe bien sur le 64 prévu, avec un cycle de 7 cycles, et 3 cycles de mise en route, donc 10 cycles calculés, et le milliardième est le 6^ème, youpi !

Mon code est pas super joli, je n'ai pas cherché à factoriser mes fonctions pour glisser vers le nord, sud, est et ouest, donc j'en ai quatre, presque identiques.
Ce qui est plus intéressant, ce sont mes efforts (inutile, mais jolis) pour préparer un cache super efficace et peu gourmand, comme quoi j'ai à la fois appris de mes erreurs passées, et pas du tout appris à anticiper où la difficulté se trouve dans un exercice.
Par contre ça résout l'exercice 1 fastoche avec le code du 2.

Pour comprendre, je considère les problèmes remis à plat, donc une seule chaîne de caractères et on navigue en connaissant la largeur et la hauteur.
Et je stocke ces problèmes dans une dictionnaire avec le hash() en clé. Donc j'appelle mes fonctions avec la valeur de platform qui est un hash(), donc un entier.
Ça veut dire que chaque fonction qui fait glisser les pierres prend en entrée un unique entier, et sort un autre entier.
Autant dire que le cache il pèse pas lourd, il est optimisé, il est efficace (et il est inutile).

Allez, souffrez lecteurs :

from sys import stdin
from functools import cache

def renumerate(sequence, start=None):
  """Reversed enumerate() function
  Can work with generators only if start is given
  """
  n = start
  if start is None:
    n = len(sequence) - 1
  for elem in sequence[::-1]:
    yield n, elem
    n -= 1

class Platform:
  def __init__(self, problem):
    self.width = len(problem[0])
    self.height = len(problem)
    self.size = self.width * self.height
    self.hashes = {}
    self.platform = self.hash("".join(problem))
    # self.print()

  def print(self, platform=None):
    problem = self.hashes[platform or self.platform]
    for y in range(self.height):
      print("|", problem[self.height * y:self.height * (y + 1)])

  def hash(self, problem):
    h = hash(problem)
    if h not in self.hashes:
      self.hashes[h] = problem
    return h

  def get_load(self, platform):
    problem = self.hashes[platform]
    total = [0] * self.width
    for pos, rock in enumerate(problem):
      if rock == "O":
        total[pos % self.width] += self.height - pos // self.width
    return sum(total)

  def turn(self, platform=None):
    @cache
    def _turn(platform):
      platform = self.push_north(platform)
      platform = self.push_west(platform)
      platform = self.push_south(platform)
      platform = self.push_east(platform)
      return platform
    return _turn(platform or self.platform)

  def push_north(self, platform=None):
    @cache
    def _north(platform):
      problem = list(self.hashes[platform])
      empty = list(range(self.width))
      for pos, rock in enumerate(problem):
        x = pos % self.width
        if rock == "O":
          if empty[x] != pos:
            problem[pos] = "."
            problem[empty[x]] = "O"
          empty[x] += self.width
        elif rock == "#":
          empty[x] = pos + self.width
      return self.hash("".join(problem))
    return _north(platform or self.platform)

  def push_south(self, platform=None):
    @cache
    def _south(platform):
      problem = list(self.hashes[platform])
      empty = [self.size - self.width + i for i in range(self.width)]
      for pos, rock in renumerate(problem, self.size - 1):
        x = pos % self.width
        if rock == "O":
          if empty[x] != pos:
            problem[pos] = "."
            problem[empty[x]] = "O"
          empty[x] -= self.width
        elif rock == "#":
          empty[x] = pos - self.width
      return self.hash("".join(problem))
    return _south(platform or self.platform)

  def push_west(self, platform=None):
    @cache
    def _west(platform):
      problem = list(self.hashes[platform])
      empty = [self.height * i for i in range(self.height)]
      for pos, rock in enumerate(problem):
        y = pos // self.width
        if rock == "O":
          if empty[y] != pos:
            problem[pos] = "."
            problem[empty[y]] = "O"
          empty[y] += 1
        elif rock == "#":
          empty[y] = pos + 1
      return self.hash("".join(problem))
    return _west(platform or self.platform)

  def push_east(self, platform=None):
    @cache
    def _east(platform):
      problem = list(self.hashes[platform])
      empty = [self.height * (i + 1) - 1 for i in range(self.height)]
      for pos, rock in renumerate(problem, self.size - 1):
        y = pos // self.width
        if rock == "O":
          if empty[y] != pos:
            problem[pos] = "."
            problem[empty[y]] = "O"
          empty[y] -= 1
        elif rock == "#":
          empty[y] = pos - 1
      return self.hash("".join(problem))
    return _east(platform or self.platform)


resolution = Platform(data)
# Exercice 1 tout facile
print(resolution.get_load(resolution.push_north()))
# Exercice 2
state = resolution.platform
states = [state]
while True:
  state = resolution.turn(state)
  if state in states:
    skip = states.index(state)
    loop = len(states) - skip
    print(f"looping in {loop} cycles after {skip} cycles")
    break
  states.append(state)
state = states[skip + (1000000000 - skip) % loop]
print(resolution.get_load(state))

Bilan : 1,6 secondes et 15Mo de RAM, avec ou sans le cache, c'est pareil, et pas de mauvaise surprise, quand ça a validé les données de test, ça a validé le problème complet.

• Yth.

PS: pour faire plaisir à Tanguy, mon premier jet pour passer l'étape 1 modélisait avec un Enum Rock.RND/SQR/NOP, et ma fonction, unique, était un mix de mes méthodes north et load, tout en une passe, rapide, efficace, pour aller vite fait à l'étape 2.

PPS: je suis resté sur des str au bout du compte, parce qu'une list c'est unhashable, donc je pouvais pas utiliser hash() pour optimiser mes caches (inutiles). Je suppose qu'en revenant à un truc qui fait moins d'explosion de str en list et vice-versa ça doit pouvoir marcher, voire en utilisant un tuple plutôt qu'une liste pour le cache, et une transformation tuple->list->roule_tes_pierres->tuple pour conserver le cache.

Je vois deux types de caractères, je pense binaire.
Transformer les lignes en nombre, ça permet des comparaisons d'entiers plutôt que de chaînes : ça me plaît.

Alors voilà une partie 1 assez rapide, faut surtout (surtout) bien mesurer ses indices de listes, ses ranges, etc.

D'abord les données, on va retourner une liste de nombres horizontaux et la même chose en vertical, les . sont des 0 et les # des 1.

def patterns():
  _h, _v = [], []
  for line in stdin.read().strip().splitlines() + [""]:
    if line:
      line = line.translate(str.maketrans(".#", "01"))
      _h.append(int(line, 2))
      _v.append(list(line))
      continue
    _v = [int("".join(col), 2) for col in zip(*_v)]
    yield _h, _v
    _h, _v = [], []

data = list(patterns())

Ensuite j'ai deux fonctions de calcul de symétries, différentes pour les deux exercices, ça se factorisait assez mal chez moi.

def symetry(search):
  for axe in range(len(search) - 1, 0, -1):
    size = min(axe, len(search) - axe)
    for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1]):
      if a != b:
        break
    else:
      yield axe

ex1 = sum(
  sum(list(symetry(h))) * 100 + sum(list(symetry(v)))
  for h, v in data
)

L'exercice 2 est un peu plus complexe, puisque je n'ai plus vraiment accès aux données d'origine, je n'ai plus que mes nombres :

POWEROF2 = {2**i for i in range(20)}
def almost_symetry(search):
  for axe in range(len(search) - 1, 0, -1):
    size = min(axe, len(search) - axe)
    diffs = [
      (a, b)
      for a, b in zip(search[axe - size:axe], search[axe + size - 1:axe - 1:-1])
      if a != b
    ]
    # looking for exactly one different line
    if len(diffs) != 1:
      continue
    # And one difference between the two lines
    a, b = diffs[0]
    diff = abs(a - b) * 2
    if diff in POWEROF2 and (a & diff) == (b & diff):
      yield axe

ex2 = sum(
  sum(list(almost_symetry(h))) * 100 + sum(list(almost_symetry(v)))
  for h, v in data
)

La réflexion est simple : si deux lignes diffèrent d'un seul élément, alors leur représentation binaire diffère d'un seul bit, donc leur différence est une puissance de 2. Les puzzles ne dépassent pas 17x17, donc avec mon ensemble qui va jusque 2²⁰ je suis suffisamment large.

Par contre c'est une condition nécessaire, mais pas suffisante. Presque, en tout cas avec les données de test on ne trouve pas l'erreur.
Ben oui, si deux lignes diffèrent sur deux cases côte à côte, une à 1 d'un côté et l'autre de l'autre, la différence fait 2ⁿ⁺¹ - 2ⁿ = 2^n, qui est puissance de 2.
En regardant bien, pour une différence de 2ⁿ on a forcément le bit n différent, mais si le bit n+1 est identique alors les deux nombres sont identiques (sinon on peut même en avoir plein : 32-16-8=8 !).

Bref, encore une fois je veux faire vite, je teste une idée sans même la valider dans ma tête, c'est faux et je me demande pourquoi.

Mais voilà, finalement on a un truc assez simple, trivialement rapide (0,3s on tombe jamais vraiment en dessous de ça en démarrant un interpréteur python), donc pas trop chercher à optimiser, on ne saurait pas vraiment si on y gagne ou pas.

Par contre côté lisibilité c'est mort, il faut réfléchir à tout ce que ces indices, ces parcours à l'envers ou pas, etc, signifient vraiment, pour comprendre quoi que ce soit.

• Yth.

Je me suis pris la tête à cause d'une erreur de raisonnement et du fait que je n'ai rien modélisé.
J'avais un algo qui détectait de très bons candidats à la presque-symétrie, en fait j'avais 103 candidats sur 100.
Et pour ces 3 là je dois fouiller un peu plus loin pour valider la presque symétrie, et là, si j'avais fait une classe Pattern avec les données dedans, je serais allé bien plus vite.

En fait, sur le principe (mais pas tellement sur la résolution dans mon cas, j'ai été lent), on voit tout de suite un truc dans les données, et ça suggère des idées.

Bref, si j'avais pris le temps de faire quelque chose de propre, je serais allé plus vite :)

• Yth.

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.

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.

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.

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.

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.

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.

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.

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.

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.