Re: sans PPCM, t'est cuit

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.