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

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.