Yth a écrit 2604 commentaires

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.

Ouais.
En écrivant le commentaire, j'ai pensé à mieux, et voilà :

def run(starmap, expansion):
  stars = [(x, y) for y, line in enumerate(starmap) for x, _ in enumerate(line) if _ == "#"]
  Xs = sorted({x for x, y in stars})
  Ys = sorted({y for x, y in stars})
  stars = [
    (
      sum(1 if _ in Xs else expansion for _ in range(x + 1)),
      sum(1 if _ in Ys else expansion for _ in range(y + 1)),
    )
    for x, y in stars
  ]
  return sum(
    abs(x2 - x1) + abs(y2 - y1)
    for x1, y1 in stars
    for x2, y2 in stars
  )//2

On calcule directement les coordonnées en parcourant les lignes/colonnes vides ou pleines.
Parfois on a beau essayer de simplifier notre vision du problème, on reste bloqué sur un truc, et on voit pas qu'il y a plus simple.

• Yth.

Aujourd'hui, j'ai fait assez simple, et c'est passé immédiatement pour la seconde partie.

Il me semble qu'on a déjà fait un bidule similaire l'an passé, avec des expansions de galaxies, et peut-être même des distances de Manhattan aussi, mais c'était peut-être dans deux problèmes différents…

Bref, je n'ai jamais cherché à doubler les lignes vides, mais à doubler les espaces vides.
En fait j'ai considéré la liste des galaxies, avec leurs positions.
Ensuite je travaille sur les abscisses, puis les ordonnées, l'un après l'autre, donc j'ai une liste de nombres, croissants, d'abord en Y puis en X.
Et pour chaque espace non nul entre deux de ces nombres, j'ajoute la taille de cet espace à tout ce qui est après : galaxies (en X ou en Y selon l'étape) et aux nombres restants. Bref, j'étends vers le bas, puis vers la droite.

Ajouter la taille à la taille ça double.
Pour l'exercice 2, on n'ajoute pas la taille mais (1 million moins 1) de fois cette taille. Exercice terminé.

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

def run(starmap, mult):
  stars = [(x, y) for y, line in enumerate(starmap) for x, _ in enumerate(line) if _ == "#"]
  Xs = sorted({x for x, y in stars})
  Ys = sorted({y for x, y in stars})
  y0 = 0
  while Ys:
    adding = (Ys[0] - y0) * mult
    stars = [(x, y if y < y0 else y + adding) for x, y in stars]
    Ys = [y + adding for y in Ys]
    y0 = Ys.pop(0) + 1
  x0 = 0
  while Xs:
    adding = (Xs[0] - x0) * mult
    stars = [(x if x < x0 else x + adding, y) for x, y in stars]
    Xs = [x + adding for x in Xs]
    x0 = Xs.pop(0) + 1
  return sum(
    abs(x2 - x1) + abs(y2 - y1)
    for x1, y1 in stars
    for x2, y2 in stars
  )//2

ex1 = run(data, 1)
ex2 = run(data, 1000000-1)

• Yth.

T'aime bien faire plus générique que l'énoncé, parce qu'on sait sans regarder les données que les tuyaux sont à deux entrées, jamais de bifurcations, alors joli travail hyper générique, et proprement modélisé :)
J'aime bien les enum.Flags, ça peut être vraiment utile.
J'ai conçu une super machine à états avec un enum.Flags dans mon projet professionnel actuel, c'est tout propre et tout le monde comprend le code !

Et je constate aussi que je suis finalement le seul bourrin à avoir zoomé sur la carte pour la voir plus en détail, c'est bien propre comme résolution de la partie 2. Et plus rapide que ma solution aussi, mais que je n'ai pas optimisée du tout (du tout (elle prend toute une longue seconde à s'exécuter !!)).

• Yth.

Vous verrez ici le rendu exploratoire de ma carte doublée, on voit très bien les zones :
https://ythogtha.org/advent_of_code/aoc-2023-10.html

• Yth.

Attention, spoiler pour ceux qui luttent sur la partie 2 !

Partie 1

Pour la première c'est pas très difficile, on parcours le bidule.
J'ai très mal dormi, je me suis pris la tête à partir dans les deux directions à la fois et à trouver le moment de la rencontre, alors qu'il suffit de parcourir une seule boucle et de diviser la longueur par deux, voici un algorithme assez efficace, même si probablement trop modélisé.
Au passage, j'ai aplati la carte pour qu'elle soit en 1 dimension, c'est plus facile, mais pas autant pour la partie 2 :

data = stdin.read()).strip().splitlines()
LARGEUR = len(data[0])
HAUTEUR = len(data)
data = "".join(data)

class Dir(IntEnum):
  X = 0
  N = -LARGEUR
  S = LARGEUR
  E = 1
  O = -1

def tuile(N=Dir.X, S=Dir.X, E=Dir.X, O=Dir.X, sides=None):
  return {Dir.N: N, Dir.S: S, Dir.E: E, Dir.O: O}

# changement de direction en fonction de la direction d'entrée dans une portion de tuyau
vers_tuile = {
  ".": tuile(),
  "S": tuile(N=Dir.N, S=Dir.S, E=Dir.E, O=Dir.O),
  "|": tuile(N=Dir.N, S=Dir.S),
  "-": tuile(E=Dir.E, O=Dir.O),
  "L": tuile(S=Dir.E, O=Dir.N),
  "J": tuile(S=Dir.O, E=Dir.N),
  "7": tuile(N=Dir.O, E=Dir.S),
  "F": tuile(N=Dir.E, O=Dir.S),
}
Carte = [vers_tuile[_] for _ in data]
start = data.index("S")
explored = {start}
explorer, direction = list(
  (start + direction, direction)
  for direction in Dir
  if direction and Carte[start + direction][direction]
)[0]
while True:
  explored.add(explorer)
  direction = Carte[explorer][direction]
  explorer = explorer + direction
  if explorer == start:
    break
ex1 = len(explored) // 2

Pour la suite, j'ai dû voir les choses et donc représenter mon bidule plus visuellement, on remplace |-LJ7F par │─└┘┐┌. J'ai totalement triché en remplaçant S par son symbole, après avoir observé les données, mais c'est pas si difficile de déterminer ça, et le rendu sur les données de test.

data = "".join([
  _ if p in explored else "  "
  for p, _ in enumerate(data.translate(str.maketrans("|-LJ7F", "│─└┘┐┌")))
])
for i in range(HAUTEUR):
  print(data[i * LARGEUR:(i + 1) * LARGEUR])

 ┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌───┐
 │└┘││││││││││││┌──┘
 └─┐└┘└┘││││││└┘└─┐ 
┌──┘┌──┐││└┘└┘ ┌┐┌┘ 
└───┘┌─┘└┘    ┌┘└┘  
   ┌─┘┌───┐   └┐    
  ┌┘┌┐└┐┌─┘┌┐  └───┐
  └─┘└┐││┌┐│└┐┌─┐┌┐│
     ┌┘│││││┌┘└┐││└┘
     └─┘└┘└┘└──┘└┘  

  ┌┐ 
 ┌┘│ 
┌┘ └┐
│┌──┘
└┘

Partie 2, et maintenant pour le spoiler !

J'ai doublé la carte et reconstruit les tuyaux manquants. Ensuite il suffit d'explorer la zone vide à l'extérieur, on peut se faufiler partout vu qu'on a créé de l'espace entre les tuyaux.
On transforme une case en quatre cases, on garde celle d'origine, et on étend logiquement à droite et en dessous, la 4è en bas à droite étant forcément vide.
Les cartes d'exemple doublées donnent ça :

┌: ┌─, ┐: ┐., └:└─, ┘:┘., │:│., ─:──
   │.     │.    ..    ..    │.    ..

..┌─┐.┌─┐.┌─┐.┌─┐.┌─┐.┌─┐.┌─┐.┌───────┐.
..│█│.│█│.│█│.│█│.│█│.│█│.│█│.│███████│.
..│█└─┘█│.│█│.│█│.│█│.│█│.│█│.│█┌─────┘.
..│█████│.│█│.│█│.│█│.│█│.│█│.│█│.......
..└───┐█└─┘█└─┘█│.│█│.│█│.│█└─┘█└───┐...
......│█████████│.│█│.│█│.│█████████│...
┌─────┘█┌─────┐█│.│█└─┘█└─┘███┌─┐█┌─┘...
│███████│.....│█│.│███████████│.│█│.....
└───────┘.┌───┘█└─┘█████████┌─┘.└─┘.....
..........│█████████████████│...........
......┌───┘█┌───────┐███████└─┐.........
......│█████│.......│█████████│.........
....┌─┘█┌─┐█└─┐.┌───┘█┌─┐█████└───────┐.
....│███│.│███│.│█████│.│█████████████│.
....└───┘.└─┐█│.│█┌─┐█│.└─┐█┌───┐█┌─┐█│.
............│█│.│█│.│█│...│█│...│█│.│█│.
..........┌─┘█│.│█│.│█│.┌─┘█└─┐.│█│.└─┘.
..........│███│.│█│.│█│.│█████│.│█│.....
..........└───┘.└─┘.└─┘.└─────┘.└─┘.....
........................................

....┌─┐...
....│█│...
..┌─┘█│...
..│███│...
┌─┘███└─┐.
│███████│.
│█┌─────┘.
│█│.......
└─┘.......
..........

On « recompresse » ensuite en prenant les cases dont les coordonnées sont paires : (0, 0), (0, 2), (2, 2) etc.

.┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌───┐
.│└┘││││││││││││┌──┘
.└─┐└┘└┘││││││└┘└─┐.
┌──┘┌──┐││└┘└┘█┌┐┌┘.
└───┘┌─┘└┘████┌┘└┘..
...┌─┘┌───┐███└┐....
..┌┘┌┐└┐┌─┘┌┐██└───┐
..└─┘└┐││┌┐│└┐┌─┐┌┐│
.....┌┘│││││┌┘└┐││└┘
.....└─┘└┘└┘└──┘└┘..

..┌┐.
.┌┘│.
┌┘█└┐
│┌──┘
└┘...

Le reste c'est un décompte et hop, fini.
Le code est plutôt moche, je le posterai plus tard quand je l'aurai rendu plus lisible.

• Yth.

Mon algo final est un peu bâtard, parce qu'il part sur un truc plus générique selon les données de l'énoncé et s'arrête un peu sèchement grâce à ce qu'on « découvre » dans les données :

Au passage j'ai découvert itertools.cycle, très pratique, au début j'avais réimplémenté la me^me chose avec un générateur.

import sys
import re
import math
from dataclasses import dataclass
from itertools import cycle

program, _, *data = sys.stdin.read()).strip().splitlines()
program = [int(x == "R") for x in program]

@dataclass
class Node:
  name: str
  left: str = None
  right: str = None
  start: bool = False
  end: bool = False
  def __bool__(self):
    return self.end
  def __getitem__(self, key):
    return self.right if key else self.left

places = {x[0]: Node(*x) for line in data for x in [re.findall("[A-Z]{3}", line)] if x}
for place in places.values():
  place.left = places[place.left]
  place.right = places[place.right]
  place.start = place.name[2] == "A"
  place.end = place.name[2] == "Z"

def run(position, prog):
  _endpos = None
  _endtime = 0
  _nb = 0
  for direction in cycle(prog):
    position = position[direction]
    _nb += 1
    if position:
      if _endpos:
        break
      _endpos = position.name
      _endtime = _nb
  return _endpos, _endtime, _nb

# Exercice 1
endpos, ex1, loop = run(places["AAA"], program)

# Exercice 2
loops = []
for place in places.values():
  if place.start:
    endpos, loopstart, loopend = run(place, program)
    loop = loopend - loopstart
    loops.append(loop)
    print(f"From {place.name} to {endpos}, loop={loopstart}+{loop}={loopend}")

ex2 = math.lcm(*loops)

Les affichages de la boucle de l'exercice 2 donnent chez moi :

From VNA to KTZ, loop=15871+15871=31742
From AAA to ZZZ, loop=21251+21251=42502
From DPA to GGZ, loop=16409+16409=32818
From JPA to MCZ, loop=11567+11567=23134
From DBA to TPZ, loop=18023+18023=36046
From QJA to FTZ, loop=14257+14257=28514

On voit très clairement les deux cycles de même longueur, dès le début.
C'est à partir de cet affichage là qu'on saute la résolution générique pour se contenter de calculer le PPCM et finir le problème.

• Yth.

Franchement, heureusement que c'était assez trivial aujourd'hui, parce que certaines des journées précédentes, je n'aurais pas pu faire ça…

data = """...
...
..."""
ex1, ex2 = 0, 0
for serie in (
  [int(x) for x in line.split()]
  for line in data.splitlines()
):
  sign = 1
  s = serie
  while any(s):
    ex2 += sign * s[0]
    ex1 += s[-1]
    sign = -sign
    s = [s[i + 1] - s[i] for i in range(len(s) - 1)]
print(ex1)
print(ex2)

Sur l'éditeur en ligne sur le téléphone, j'ai commencé par copier-coller les données de l'exercice dans la variable data, et zou pour l'exercice 1, puis modifier le programme pour juste l'exercice 2, j'avais besoin des résultats à entrer, pas d'un code propre et complet.

• Yth.

Tu as any aussi, à la place de if all(a == 0 for a in L): j'ai fait if not any(L):

• Yth.

Aujourd'hui je n'ai pas d'ordinateur disponible, alors c'est résolution sur téléphone.
Déjà, trouver un interpréteur python qui soit utilisable, c'est un premier exercice.
Ensuite, bah résolu en marchant entre les étals du marché.
Aucune difficulté à signaler, aucun algo à fournir non plus : je ne peux pas copier-coller mon travail !

Bref, on fait comme on peut 😃

• Yth, 3615 mavie…

Je pense, en effet, que ce théorème aurait permit de résoudre le cas où les cycles ne commencent pas tous à 0.
Là on a une situation où les restes sont tous nuls, donc tout de suite, ça simplifie…

• Yth.

En fait, les données tournent forcément en rond.
Avec mes données :
On a 269 actions, et 750 positions.
Il est obligatoire qu'en 269*750 = 201750 déplacements on ait bouclé, pour chaque fantôme.
Il y a 6 fantômes.

On va donc chercher la longueur du cycle, et toutes les sorties (zone en ..Z) possibles à partir d'une entrée (..A).
Dès qu'on retombe sur la première sortie trouvée, ET qu'on en est au même point dans le programme : on a fait une boucle.

Il se trouve que :
* toutes les longueurs de boucles (entre deux passages sur une même sortie) sont divisibles par 269, on a donc un vrai cycle dès qu'on retombe sur la première sortie visitée ;
* on tombe, pour chaque entrée, sur une et une seule sortie, donc chaque cycle est indépendant ;
* la durée pour tomber sur la sortie une première fois est la même que la longueur du cycle, donc tous les cycles commencent au même point dans le temps : 0.

Ex: A -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z -> [n-1 étapes] -> Z
Le cycle fait n de long, n est un nombre entier de fois le programme exécuté (n divisible par 269), et démarrer en A est équivalent à démarrer en Z.

Ça simplifie à mort, puisqu'en pratique il ne reste plus qu'à calculer le PPCM des longueurs de cycles.

Si ça n'avait pas été le cas, les cycles auraient été beaucoup plus longs, mais toujours inférieurs à 169*750 = 201750, ce qui se calcule vite.
Par contre on aurait pu avoir des périodes de démarrage où on parcours quelques zones, avant de « tomber » sur un cycle, et de rester dedans, ils auraient pu ne pas commencer au même moment.
Et là le PPCM des cycles ne permet que d'avoir la longueur du super-cycle de l'ensemble des 6 fantômes, mais pas le moment où ils se trouvent tous sur une sortie en même temps.
Ce qui pourrait ne jamais arriver, et c'est probablement pour ça que le problème est « aussi simple », ça aurait peut-être été trop difficile de s'assurer qu'il y ait une solution, et que cette solution soit effectivement calculable rapidement ?

J'ai pas d'idée géniale, là tout de suite, sur comment résoudre ce problème là, mais la force brute n'est pas une solution, mon propre super-cycle faisant presque 12000 milliards, la solution on va pas tomber dessus par hasard.

J'ai failli tenter de résoudre le gros problème, mais heureusement j'ai d'abord regardé mes cycles, et la simplicité m'a fait prendre le raccourci d'un PPCM multiple vite fait.

• Yth.

PS: ça me rappelle une histoire de Tetris l'année dernière, avec des cycles de dingue et beaucoup de méninges triturées :)

Ah non, ma faute, en fait il ne faut pas redéfinir __eq__(), si on le fait alors ça fait sauter le hash (enfin, disons que ça casse quelque chose quelque part) et on ne peut plus l'utiliser dans les set(), mais on n'a pas besoin de surcharger cette méthode : elle fonctionne très bien nativement.

Donc on définit uniquement __lt__() avec le @total_ordering, et on est bon :)

• Yth.

Et en rajoutant deux lignes tu peux les utiliser dans des Set, ou en clé de dictionnaires etc :

  def __hash__(self):
    return self.weight

Avec ça je n'ai quasiment rien à changer dans mon algorithme pour utiliser cette classe à la place des caractères "23456789abcdef" comme je l'ai fait dans ma solution.

J'aime bien l'élégance de la chose, et le côté vraiment lisible, zéro hack dans le reste du code.
Bon, par contre je n'ai besoin que de Card.JOKER de façon explicite.
Il faut juste faire un line.replace(Card.JACK.value, Card.JOKER.value pour la seconde partie de l'exercice, à la place des a.translate(str.maketrans("TJQKA", "a0cde")), c'est plus joli.

Je perd un poil en perfs par contre : 85ms au lieu de 70ms.
Je suppose que c'est au niveau de la comparaison d'un tuple de Card par rapport à celle de deux str dans mon code initial.
Pas très sûr, mais c'est dommage…

• Yth.