Yth a écrit 2604 commentaires

C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…

J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension : x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.
J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.

from sys import stdin
from functools import total_ordering
from collections import deque
from itertools import chain
data = deque(stdin.read().strip().splitlines())

@total_ordering
class Bloc:
  def __init__(self, blocdef=None, blocname=None, cubes=None):
    self.name = blocname
    if cubes:
      self.cubes = cubes
      self.alt = min(cubes) // 100
      return
    x, y, z = zip(*((int(__) for __ in _.split(",")) for _ in blocdef.split("~")))
    self.cubes = {
      a + b * 10 + c * 100
      for a in range(min(x), max(x) + 1)
      for b in range(min(y), max(y) + 1)
      for c in range(min(z), max(z) + 1)
    }
    self.alt = min(z)
  def __iter__(self):
    for p in self.cubes:
      yield p
  def __eq__(self, o):
    return self.alt == o.alt
  def __lt__(self, o):
    return self.alt < o.alt
  def __contains__(self, _):
    return _ in self.cubes
  def __repr__(self):
    return f"Bloc#{self.name}({self.cubes})"
  def __neg__(self):
    alt = min(_ // 100 for _ in self.cubes) * 100 - 100
    return Bloc(blocname=self.name, cubes={alt + _ % 100 for _ in self.cubes})
  def __pos__(self):
    alt = max(_ // 100 for _ in self.cubes) * 100 + 100
    return Bloc(blocname=self.name, cubes={alt + _ % 100 for _ in self.cubes})
  def __sub__(self, x):
    self.cubes = {_ - 100 * x for _ in self.cubes}

class Universe:
  def __init__(self):
    self.zone = set(range(100))
    self.blocs = {}
  def __contains__(self, _):  # True if bloc can be placed in universe
    return not self.zone.intersection(_.cubes)
  def add(self, _):
    self.zone.update(_)
    for p in _:
      self.blocs[p] = _.name

data.extendleft(["0,0,0~9,9,0"])
blocs = sorted(Bloc(line, i) for i, line in enumerate(data))
ground = blocs.pop(0)
universe = Universe()
universe.add(ground)
for bloc in blocs:
  while -bloc in universe:
    bloc - 1
  universe.add(bloc)

# Blocs under each bloc
down = {
  bloc.name: {universe.blocs[p] for p in -bloc if p in universe.blocs}
  for bloc in blocs
}
cannot = {bloc for _ in down.values() if len(_) == 1 for bloc in _}.difference({0})
ex1 = len(blocs) - len(cannot)

Et l'exercice 2, prenez peur !

topof = {}
partial = {}
for bloc in sorted(blocs, reverse=True):
  name = bloc.name
  if name not in topof:
    topof[name] = set()
  # Handling partially supported blocks
  mypartial = partial.pop(name, set())
  if mypartial:
    replay = True
    while replay:
      replay = False
      newpart = set()
      # All blocs partially supported elsewhere
      otherpart = set(chain.from_iterable(
        v
        for k, v in partial.items()
        if k not in topof[name]
      ))
      for _ in mypartial:
        if _ not in otherpart:
          # That bloc isn't supported by someone else elsewhere, it is mine!
          topof[name].add(_)
          topof[name].update(topof.get(_, []))
          replay = True  # We'll have to restart the search here, because the world changed.
        else:
          newpart.add(_)
      mypartial = newpart
    if mypartial:
      partial[name] = mypartial
  # Sending down my informations
  up = topof.get(name, set()).union({name})
  downward = list(down.get(name, []))
  if len(downward) == 1:  # Supported by only one other bloc, sending what I'm actively supporting
    topof[downward[0]] = topof.get(downward[0], set()).union(up)
  # Sending known partial information down
  for bloc in downward:
    partial[bloc] = partial.get(bloc, set()).union({name}).union(partial.get(name, {}))
  partial.pop(name, None)

ex2 = sum(len(topof[bloc]) for bloc in cannot)

J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.

• Yth.

Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
Parfois on peut représenter ce qu'il se passe, parfois pas trop.
Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.

• Yth.

C'est pas hyper simple à représenter, mais je vais essayer.

button
↓
broadcaster
│ 
├→hd → lt → rh → gx → xf → tg → ks → tc → qz → rl → pf → pr
│ │↑   ↑    ↓    ↑    ↑    ↓    ↑    ↑    ↓    ↓    ↓    ↓
│ │╰───┌─────────────────────────────────────────────────┐ ┌──┐
│ ╰───→│                    nl                           │→│cq│──╮
│      └─────────────────────────────────────────────────┘ └──┘  │
│                                                                │
├→zj → kn → xn → gf → gv → vr → qb → hq → nx → bs → rd → vs      │
│ │↑   ↓    ↓    ↑    ↑    ↑    ↑    ↑    ↓    ↓    ↓    ↓       ↓
│ │╰───┌─────────────────────────────────────────────────┐ ┌──┐ ┌──┐
│ ╰───→│                    pb                           │→│vp│→│  │
│      └─────────────────────────────────────────────────┘ └──┘ │  │
│                                                               │  │
├→sq → vh → qc → gp → cp → jt → kb → hj → cf → jg → pd → mt     │ns│→rx
│ │↑   ↓    ↑    ↑    ↓    ↑    ↓    ↓    ↓    ↓    ↓    ↓      │  │
│ │╰───┌─────────────────────────────────────────────────┐ ┌──┐ │  │
│ ╰───→│                    rr                           │→│rv│→│  │
│      └─────────────────────────────────────────────────┘ └──┘ └──┘
│                                                                ↑
└→jz → ht → jv → zs → dq → jc → xv → dx → fq → xz → zp → mm      │
  │↑   ↑    ↓    ↑    ↓    ↑    ↓    ↓    ↑    ↓    ↓    ↓       │
  │╰───┌─────────────────────────────────────────────────┐ ┌──┐  │
  ╰───→│                    dj                           │→│dc│──╯
       └─────────────────────────────────────────────────┘ └──┘

On va dire qu'un « low pulse » est un 1, et un « high pulse » un 0.
C'est plus simple pour comprendre.

Le button envoie un 1 quand on appuie dessus.
Le broadcaster transmet ce qu'il a reçu à toutes ses destinations.

Les noms simples, en deux lettres, sans cadre, sont des alternateurs, s'ils reçoivent un 1, ils envoient une fois un 1, et une fois un 0. Mais s'ils reçoivent 0 ils bougent pas.
À l'état initial ils enverront un 0 au premier 1 reçu.
Donc notre broadcaster étant relié à des alternateurs, au repos il ne se passe rien, mais quand on appuie sur le gros bouton rouge, il active les quatre alternateurs devant lui.

Les noms dans les cadres sont des boîtes de remise à zéro, en gros.
Au début elles sont configurées sur 1 à toutes leurs entrées, mais c'est mis à jour dès qu'elles reçoivent un truc.
Si toutes leurs entrées sont à 0, alors elles envoient un 1 à toutes leurs sorties ! Sinon, c'est un 0, qui sera ignoré par tous les alternateurs connectés. D'où le nom de boîte de remise à zéro, ça ne va envoyer 1 aux alternateurs que quand ça reçoit du 0 de partout à la fois !

Quand ça arrive, les boîtes à droites reçoivent un 1 et donc envoient un 0, sinon elles reçoivent un 0 et envoie un 1.
Avec une seule entrée, ce sont des inverseurs.

Donc quand nos grosses boîtes s'activent et réussissent à envoyer un 1, le signal est inversé en 0 vers la boîte finale.
Si toutes les quatre grosses boîtes envoient un 1 en même temps, alors la boîte finale reçoit quatre 0.
À ce moment là elle va envoyer un 1 vers rx, qui est notre module de sortie et qui n'attends que ça !

Franchement, une fois représenté comme ça, le problème il est hyper clair hein ?
Faut trouver le moment où chacune des grosses boîte s'active.

Là, on a grosso-modo tous fait une simulation : on part de l'état initial, chaque alternateur va envoyer un 0, et les grosses boîtes sont sur 1 dans toutes leurs entrées, et on appuie sur le gros bouton rouge, jusqu'à ce que les boîtes s'activent.

Là on note quand c'est arrivé.
Typiquement on va continuer pour voir quand ça va se produire à nouveau, pour chaque boîte, et essayer de déduire un schéma.
Ici c'est facile, en fait, dès la première fois que ça s'active, on a fait un cycle et c'est retour à l'état initial, en fait pas tout à fait, mais au moins ça boucle sur la même durée.
On a donc 4 cycles, il ne reste plus qu'à les coordonner, savoir quand est-ce qu'ils vont s'activer tous ensemble.
Et le plus petit multiple commun aux quatre valeurs mesurées est notre réponse.

Maintenant en poussant l'analyse.
Notre série par exemple de la première boîte, consiste en 12 alternateurs, tous éteints donc prêts à envoyer 0.
On va noter ça 000000000000.
La boîte n'enverra absolument rien tant qu'on ne l'aura pas activée (enfin, elle envoie des 0 qui sont ignorés par les alternateurs).
Si on appuie, le premier va s'allumer, et envoyer 0, qui va être ignoré, on est donc dans cette situation :
100000000000.
Au second coup, notre premier alternateur va s'éteindre, repasser à 0, mais aura envoyé un 1 à droite, sur le second, qui va s'allumer et envoyer 0 qui sera ignoré.
01000000000
Au 3ème coup, on rallume le premier, rien d'autre ne bouge : 110000000000.
4 : 0010000000
5 : 1010000000
6 : 0110000000
7 : 1110000000
Ok peut continuer la simulation, mais il apparaît comme évident qu'on est en train de compter. On a exactement la représentation binaire, mais de gauche à droite, des numéros des étapes.

Là on va regarder notre boîte nl, et constater qu'elle va s'activer dès qu'elle reçoit 0 en même temps de la part de hd, rh, tg, qz, rl, pf et pr, ce qui va arriver quand il vont tous s'être allumés (passer de 0 à 1) comme dernière action.
Ça arrive dès qu'on a 1 sur chacun d'entre eux, et 0 sur les autres, c'est la première fois où ça va se produire et c'est cette configuration : 101001001111 qu'on retourne en 111100100101 pour avoir le chiffre binaire 3877, qu'on retrouve bien dans mes résultats plus haut.
Pour les autres, on va simplement lire 111000001111 soit 3847, 110010111111 soit 4051, et enfin 101010110111 soit 3797.

Diantre c'est juste.
Là nos nombres sont premiers entre eux, donc le PPCM vaut la multiplication des 4 soit… beaucoup.

Mais bref, voilà le problème entièrement décortiqué, et finalement une lecture directe des chiffre à trouver, sans aucun calcul, sans besoin d'ordinateur, sauf pour le PPCM (c'est un peu misérable à la main avec des chiffres aussi gros quand même).

Merci de ta question Ysabeau, je n'aurais pas poussé autant sinon :)

Pour continuer un petit peu, sur notre exemple 1.
On active sur 101001001111 mais à ce moment là notre boîte ne se contente pas d'envoyer un 1 vers la sortie, elle envoie aussi un 1 vers tous nos 0 !
En effet, tous les alternateurs qui n'envoient pas vers la boîte, reçoivent de la boîte.
Ils sont éteints, ils vont donc s'allumer, envoyer des 0 qui seront ignorés et passer tous à 1 : 111111111111 = 4095.
Sauf que le tout premier reçoit lui aussi un 1, exactement comme si on avait appuyé sur le bouton une fois tout passé à 1 !
C'est hd, et il est bien en dernier de la liste des alternateurs activés par nl. On lui envoie un 1 qui va faire s'éteindre tous les alternateurs en chaîne, puisqu'ils envoient un 1 en s'éteignant. Ils vont donc tous avoir envoyé un 1 vers la boîte (ceux qui sont connectés) qui verra bien son état retourner à celui d'origine.
D'où la boucle et le cycle qui recommence exactement à zéro, on est effectivement retourné précisément à l'état initial.
On a compté de 0 à 3877, et au moment d'arriver à 3877, on a une remise à 0 avec un signal envoyé vers la sortie.

• Yth.

Ça y est, j'ai, compris ton explication, bien vu !

Yth.

Alors j'ai rien compris à ton explication, mais je crois que je suis en train de tomber malade.
J'ai hyper galéré à débugger mon code, bourré de mauvaises bornes, jusqu'au bout du bout…

Bon, d'une façon ou d'une autre je n'ai pas fait comme toi.
Cf plus bas :)

• Yth.

Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution…

On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.

Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
Pour les zones en diagonale, on va rentrer par la case au coin.
Ya pas plus rapide.

Le terrain fait 131x131, et le départ au centre en 65x65.
Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre.
65 + 1 + 131 * (distance - 1) quand on va en ligne droite nord, sud, est ou ouest.
Et 65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2) pour les cases qui sont au moins un peu en diagonale.
Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.

On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être plein tout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.
Ben oui, si on entre dans une zone mettons via (0, 0), la case (0, 0) d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.
On a en fait un damier de damiers, yay !

Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
On additionne.

En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.

...●...
..●○●..
.●○●○●.
●○●○●○●
.●○●○●.
..●○●..
...●...

En distance 0 on a la zone de départ.
En distance 1 on a 4 zones directement liées.
En distance 2 on a 4 zones directes, et 4 zones diagonales.
En distance 3 c'est 4 et 8.
En distance n, c'est 4 et (n-1)*4.
Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.

Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.

Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
Je dénombre, j'additionne.

Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
On passe à la distance suivante.
On s'arrête avec une petite marge où on va additionner des zéros.
J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes…

Et puis, voilà, résultat :)

Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.

from sys import stdin
from dataclasses import dataclass
from functools import cached_property
data = stdin.read().strip().splitlines()
LARGEUR = len(data[0])  # 131
HAUTEUR = len(data)  # 131
XMAX = LARGEUR - 1
YMAX = HAUTEUR - 1
MIDDLE = XMAX // 2  # 65
ROCKS = frozenset((x, y) for y, _ in enumerate(data) for x, t in enumerate(_) if t == '#')
START = "".join(data).index("S")
START = (START % LARGEUR, START // LARGEUR)  # 65x65
STEPS1, STEPS2 = (64, 26501365)
@dataclass
class exploration:
  sx: int = 0
  sy: int = 0
  def run(self):
    def dest(x, y):
      yield (x - 1), y
      yield (x + 1), y
      yield x, (y - 1)
      yield x, (y + 1)
    explored = {(self.sx, self.sy)}
    exploring = {(self.sx, self.sy)}
    steps = [{(self.sx, self.sy)}]
    overexplored = set()
    s = 0
    while exploring:
      s = s + 1
      exploring = {
        d
        for x, y in exploring
        for d in dest(x, y)
        if d not in ROCKS
      }.difference(explored).difference(overexplored)
      for x, y in exploring:
        if (x < 0 or x >= LARGEUR or y < 0 or y >= LARGEUR) and (x, y) not in overexplored:
          overexplored.add((x, y))
      exploring.difference_update(overexplored)
      steps.append(exploring)  # adds an empty set() at the end
      explored.update(exploring)
    self._exploration = steps
    self.even = self.explored(0, len(steps))
    self.odd = self.explored(1, len(steps))
  @cached_property
  def exploration(self):
    if not hasattr(self, '_exploration'):
      self.run()
    return self._exploration
  def explored(self, start=0, steps=None):
    steps = min(steps + 1, len(self.exploration))
    return sum(
      len(self.exploration[i])
      for i in range(start, steps, 2)
    )

exp1 = exploration(*START)
ex1 = exp1.explored(STEPS1 % 2, STEPS1)

Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
Pour le premier problème, on démarre en START = (65, 65) et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.

Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.

N = exploration(MIDDLE, 0)
S = exploration(MIDDLE, YMAX)
E = exploration(XMAX, MIDDLE)
W = exploration(0, MIDDLE)
NE = exploration(XMAX, 0)
NW = exploration(0, 0)
SE = exploration(XMAX, YMAX)
SW = exploration(0, YMAX)
# nombre minimum de pas pour explorer entièrement n'importe quelle zone.
MAXEXPLORATION = max(len(x.exploration) - 1 for x in [N, S, E, W, NE, NW, SE, SW])
def bigexploration(x, y):
  bx = MIDDLE + 1 + LARGEUR * (abs(x) - 1)
  by = MIDDLE + 1 + HAUTEUR * (abs(y) - 1)
  bd = bx + by
  if y == 0:
    if x > 0:
      return E, bx
    if x < 0:
      return W, bx
    return exp1, 0
  elif x == 0:
    if y > 0:
      return S, by
    return N, by
  if x > 0 and y > 0:
    return SE, bd
  if x > 0 and y < 0:
    return SW, bd
  if x < 0 and y > 0:
    return NE, bd
  return NW, bd

FINESTEPS = STEPS2 - MAXEXPLORATION * 2
odd = STEPS2 % 2
score = exp1.odd if odd else exp1.even

La fonction bigexploration retourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en (x, y) par rapport à celle de départ.
FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis * 2 pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplement STEPS2 - MAXEXPLORATION fonctionne.

Après ça le code est moche et répétitif, dans l'esprit de bigexploration.

for distance in range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2):
  for ex, steps in [
    bigexploration(0, -distance),
    bigexploration(0, distance),
    bigexploration(distance, 0),
    bigexploration(-distance, 0),
  ]:
    remaining = STEPS2 - steps
    odd = remaining % 2
    if steps > STEPS2:
      continue
    s = ex.odd if odd else ex.even
    if steps > FINESTEPS:
      s2 = ex.explored(odd, remaining)
      print(f"Finescore({remaining}) {s2} / {s} {s!=s2}")
      s = s2
    score += s
  if distance <= 1:
    continue
  for ex, steps in [
    bigexploration(1, 1 - distance),
    bigexploration(-1, 1 - distance),
    bigexploration(1, distance - 1),
    bigexploration(-1, distance - 1),
  ]:
    remaining = STEPS2 - steps
    odd = remaining % 2
    if steps > STEPS2:
      continue
    s = ex.odd if odd else ex.even
    if steps > FINESTEPS:
      s2 = ex.explored(odd, remaining)
      print(f"FineDiago({remaining}) {s2} / {s} {s!=s2}")
      s = s2
    score += s * (distance - 1)

ex2 = score

Et bigre, même le range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2) m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !

On vérifie l'intérêt de nos FINESTEPS avec les sorties :

Finescore(130) 5635 / 7509 True
Finescore(130) 5661 / 7509 True
Finescore(130) 5624 / 7509 True
Finescore(130) 5672 / 7509 True
FineDiago(195) 6610 / 7509 True
FineDiago(195) 6571 / 7509 True
FineDiago(195) 6560 / 7509 True
FineDiago(195) 6573 / 7509 True
FineDiago(64) 957 / 7566 True
FineDiago(64) 958 / 7566 True
FineDiago(64) 946 / 7566 True
FineDiago(64) 957 / 7566 True

On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.

C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(

• Yth, vivement les vacances.

Ah oui, le deque() permet de faire une FIFO de messages, on les empile à droite, on les dépile à gauche, on a fini quand c'est vide, d'où un code d'itération assez simple dans la fonction push().

C'était la minute structure de données pas encore vue cette année. Le deque() c'est une list() optimisée pour faire des ajouts/suppressions aux bouts, donc idéal pour des FIFO, LIFO et trucs du genre.

• Yth.

Ah, oui, c'est vrai ça, le résultat c'est le PPCM des 4 cycles, sauf qu'en l'occurrence ils sont premiers entre eux (enfin, chez moi en tout cas…), encore une propriété cachée dans les données, d'où la multiplication annoncée dans mon message !
J'ai testé vite fait la multiplication sur le site avant de lancer le PPCM, et ça a fonctionné, donc j'ai complètement oublié qu'il fallait faire ça pour être corrects.

• Yth.

Je profite des feux pour écrire, et ça calcule pendant que je roule, si ça plante en général j'arrive à penser la modif à faire de tête et j'ai juste à l'écrire à l'arrêt suivant.
Je suis peut-être inconscient, mais pas suicidaire.

• Yth -> []

Ici aussi, l'énoncé ne suffit pas à résoudre le problème, les données imposent la méthode.

Il faut constater qu'à l'instar de l'exemple 2 avec output, le rx de sortie n'existe pas dans les données en entrée, et qu'il est uniquement relié à une boîte à conjonction, l'équivalent du inv du second exemple.
rx recevra un low pulse ssi inv reçoit des high pulses de partout à la fois.

Et là on lance des simulations (ou on analyse les données en entrée ?), pour voir quand notre inv reçoit des high pulses, on va constater en environ 13000 itérations qu'on a vu passer 3 high pulses de chacun des 4 sources, et que chacun de ces évènement cycle.

Chez moi :

• 3797 HP depuis la 1ère entrée ;
• 3847 HP depuis la 3è entrée ;
• 3877 HP depuis la 4è entrée ;
• 4051 HP depuis la 2è entrée.

Et ça cycle, donc 1ère entrée en 3797, 7594, 11391, 2è entrée en 4051, 8102, 12153, 3è entrée en 3847, 7694, 11541, 4è entrée en 3877, 7754, 11631.
4 cycles, et qui commencent tous à 0 en plus, heureux hasard, n'est-ce pas ?

En analysant les données on doit réaliser qu'on a 4 parcours indépendants, depuis chacune des 4 entrées de notre broadcaster, qui mènent chacun à une entrée de notre boîte inv, donc les cycles sont bien indépendants.
Par contre, deviner qu'ils commencent à zéro ne me semble pas si évident, même si tout les FlipFlop commencent à off, et les Conjoncteurs à low partout, pourquoi une fois un low reçu à l'arrivée est-ce qu'on retomberait sur l'état initial ?

Bon, bah le résultat c'est de multiplier les longueurs de cycles entre eux.
- Parce qu'on a des cycles indépendants.
- Et qu'ils commencent tous à zéro.

Le résultat est dans les 256 billions (proche de 4000⁴ ), donc on lance pas la force brute, quelle que soit la qualité de notre modélisation.

Côté code j'ai pas lourd à montrer, peut-être ma modélisation pour le 1, mignonne, que j'ai un peu pensée en amont pour pouvoir détecter des cycles, donc avec des frozen dataclass. Ça tourne pas trop mal avec 1 millions de cycles en 15 secondes et une RAM constante à 80Mo (c'est PyPy, ya un overhead de RAM de 70Mo, c'est comme ça).
Le problème réel (4051 cycles) prend moins d'une seconde en CPython, avec 10Mo de RAM.
L'état des Conjunctions est un binaire avec les bits à 0 ou 1 selon le dernier pulse reçu de chaque entrée, donc les entrées sont ordonnées. Et bien sûr, partout, low c'est 1 ou True, et high c'est 0 ou False, ça simplifie de le prendre comme ça !
L'état est dans boxes qui ne contient que des frozen dataclasses, donc en pratique quand une boîte change d'état, elle retourne une nouvelle boîte dans le nouvel état, je ne modifie jamais une boîte, ce n'est pas possible, j'en crée des nouvelles selon la situation.
Cette façon de faire permettrait de comparer deux états global du système.
On n'a pas à faire ça, donc probablement qu'il vaudrait mieux coder des boîtes dynamiques à états.
de toute façon le code final est un mélange de trucs fixes et de trucs qui bougent magiquement avec des variables globales, on a vu plus propre (je pense aux statistiques pour le premier problème)…

data = stdin.read().strip().splitlines()
FINAL = "ns"  # manuellement extrait de mes données
from dataclasses import dataclass
from collections import deque
from functools import cached_property
messages = deque()
stats = [0, 0]
# Modules
class Module:
  def send(self, src, low):  # low if True, high if False
    for dst in self.destination:
      stats[not low] += 1
      messages.append((src, dst, low))
@dataclass(frozen=True)
class Broadcaster(Module):
  destination: tuple = tuple()
  def __call__(self, src, name, low):
    self.send(name, low)
    return self
@dataclass(frozen=True)
class FlipFlop(Module):
  on: bool = False
  destination: tuple = tuple()
  def __call__(self, src, name, low):
    if not low:
      return self
    self.send(name, self.on)  # High if off, low if on
    return FlipFlop(not self.on, self.destination)
@dataclass(frozen=True)
class Conjunction(Module):
  src: tuple = tuple()
  destination: tuple = tuple()
  state: int = 0
  def addsrc(self, *src):
    return Conjunction(self.src + src, self.destination, self.state + 2**len(self.src))
  @cached_property
  def full(self):
    return 2 ** len(self.src) - 1  # low pulse for each
  def __call__(self, src, name, low):
    state = self.full if self.state == -1 else self.state
    bit = 2 ** self.src.index(src)
    if low:
      state |= bit
    else:
      state &= self.full - bit
    self.send(name, state == 0)
    return Conjunction(self.src, self.destination, state)
# data modelisation
boxes = {}
conjunctions = set()
for line in data:
  name, _, *dst = line.replace(",", "").split()
  if name[0] == "b":
    boxes[name] = Broadcaster(tuple(dst))
  elif name[0] == "%":
    boxes[name[1:]] = FlipFlop(False, tuple(dst))
  else:
    boxes[name[1:]] = Conjunction(destination=tuple(dst))
    conjunctions.add(name[1:])  # storing all conjunction names
# Updating src for conjunctions
for name, box in boxes.items():
  i = set(box.destination).intersection(conjunctions)
  if i:
    for c in i:
      boxes[c] = boxes[c].addsrc(name)

# Red Button, DO NOT PUSH !
button = Broadcaster(("broadcaster",))
def push():
  button.send("button", True)
  cstate = 0
  while messages:
    src, dst, low = messages.popleft()
    if dst in boxes:
      boxes[dst] = boxes[dst](src, dst, low)
    if dst == FINAL and not low:
      cstate = boxes[FINAL].state
  return cstate

# Cycling...
cycles = {}
for _ in range(5000**4):
  if _ == 1000:
    stats1000 = tuple(stats)
  state = push()
  if state and state not in cycles:
    cycles[state] = _ + 1
  if len(cycles) == len(boxes[FINAL].src):
    break

# Results
def mul(i):
  return reduce(lambda x, y: x * y, i)
ex1 = mul(stats1000)
ex2 = mul(cycles.values())

Le coût fixe de PyPy le rend inutile sur le problème réel, je monte de 0,55s à 0,65s, par contre si je cycle 1 million de fois, ça passe de 2min10 à 15s.
Ça doit être pour ça que je n'ai pas trouvé PyPy si pertinent cette année : l'an dernier je devais être un gros bourrin, cette année je suis tout en finesse (……).

Bon, c'était mignon, mais toujours un poil agaçant quand l'énoncé ne suffit pas à avoir la résolution, et qu'il faut compter sur des particularités des données.
Mais bon, si on nous expliquait dès le début qu'il y avait 4 cycles et qu'il fallait les coordonner, l'exercice serait assez trivial…

• Yth.

T'as découpé l'espace à 4 dimensions selon toutes les bornes possibles trouvées dans les règles, et traité chaque pavé à travers les règles pour savoir s'il était valide ou non ?

Ça doit faire plus de traitements oui, mais c'est assez propre comme approche.

Je n'y ai même pas pensé, je suis parti directement sur des découpage de pavés en deux, et bifurcation sur une règle ou une autre.

D'ailleurs, à bien y réfléchir, plutôt que d'avoir des workflows à étapes on pourrait exploser en règles uniques nom#condition?vrai:faux} :

px{a<2006:qkq,m>2090:A,rfg}
 -> px#a<2006?qkq:px1
 -> px1#m>2090?A:rfg
in{s<1351:px,qqz}
 -> in#s<1351?px:qqz
qqz{s>2770:qs,m<1801:hdj,R}
 -> qqz#s>2770?qs:qqz1}
 -> qqz1#m<1801?hdj:R}
qs{s>3448:A,lnx}
 -> qs#s>3448?A:lnx}
hdj{m>838:A,pv}
 -> hdj#m>838?A:pv}
etc.

Ça simplifierai les traitements derrière.
J'ai aussi vu des règles simplifiables comme gd{a>3333:R,R} où en fait tu rejettes tout, mais je n'ai pas jugé utile d'essayer de simplifier par ce genre de cas, ça avait l'air d'être plus d'efforts qu'autre chose.

• Yth.

Mon algo est itératif, mais sur des ensembles de pavés.
Mais bon, ça ou du récursif, ça revient au même, c'est parcours en profondeur ou en largeur, au final on explore la même chose.

Je n'ai que 546 pavés au bout du compte, et j'en ai considéré 2700 au total : pavés en cours de route, ou pavés rejetés.

• Yth.

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.