Yth a écrit 2671 commentaires

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.

Une idée :

from enum import Enum
from functools import total_ordering

@total_ordering
class Card(Enum):
    JOKER = '*'
    ONE   = '1'
    TWO   = '2'
    THREE = '3'
    FOUR  = '4'
    FIVE  = '5'
    SIX   = '6'
    SEVEN = '7'
    EIGHT = '8'
    NINE  = '9'
    TEN   = 'T'
    JACK  = 'J'
    QUEEN = 'Q'
    KING  = 'K'
    ACE   = 'A'
    def __lt__(self, other):
        return self.weight < other.weight
    def __eq__(self, other):
        return self.weight == other.weight

for i, card in enumerate(Card):
    card.weight = i

>>> Card('A') > Card('7')
True
>>> Card('J') > Card('K')
False
>>> a = [Card(x) for x in "A2222"]
>>> b = [Card(x) for x in "99997"]
>>> a > b
True

Un peu du hack puisque la définition même de la classe est bancale, et qu'il faut modifier après initialisation et avant utilisation, mais ça fonctionne.

• Yth.

Et A pour As aussi, au bout.

• Y.

Surtout que quand j'ai voulu faire mon malin, j'avais une erreur que je n'ai jamais trouvée, mais qui s'est corrigée d'elle-même en remplaçant des chiffres par des trucs lisibles.
Comme quoi coder propre, contrairement à la rumeur, ben c'est utile même pour soi-même aujourd'hui.

Voilà, avec ça on corrige des bugs, et on supprime plein de commentaires devenus inutiles aussi :

from enum import IntEnum
class HandType(IntEnum):
    HighCard = 1
    OnePair = 2
    TwoPairs = 3
    ThreeOfAKind = 4
    FullHouse = 5
    FourOfAKind = 6
    FiveOfAKind = 7

Comme ça on peut comparer le HandType entre deux mains, et le plus grand est plus fort.
L'autre étape c'est de renommer les cartes pour pouvoir comparer deux mains du même type :

data = sys.stdin.read().strip().splitlines()
hands1 = (
    Hand(a.translate(str.maketrans("TJQKA", "abcde")), int(b))
    for line in data
    for a, b in [line.split()]
)

Et pour l'exercice 2, on initialise les données (hands2) tout pareil sauf qu'on fait : str.maketrans("TJQKA", "a0cde") comme ça le Joker a une valeur plus petite que les autres cartes lors de la comparaison. Et en plus on va pouvoir bosser avec la même classe Hand, et compter les Jokers, donc les "0", et comme il n'y en a pas dans les données transformées pour l'exercice 1, ça va fonctionner pour les deux !

Maintenant notre classe Hand peut être initialisée avec les données : hand et bid, et on la décore pour pouvoir ordonner directement une liste de mains. Le cached_property permet de s'assurer qu'on ne recalculera jamais deux fois le score d'une main lors de l'exécution (an pratique ça divise le temps d'exécution par 2 environ, ça aurait pu être bien pire…). On utilise une frozen dataclass parce qu'on ne modifie pas une main, là aussi c'est de l'optimisation qui peut s'avérer déterminante en cas de problème vraiment gros.

from functools import total_ordering, cached_property
from dataclasses import dataclass
@dataclass(frozen=True)
@total_ordering
class Hand:
    hand: str = ""
    bid: int = 0
    @cached_property
    def score(self):
        return some magic
    def __lt__(self, other):
        return (self.hand < other.hand) if self.score == other.score else (self.score < other.score)
    def __eq__(self, other):
        return False

Ouaip, on simplifie en disant que deux mains sont toujours différentes, à toutes fins utiles, ça va plus vite, hein ?
Parce qu'on suppose, vu l'exercice, que toutes les mains fournies sont différentes, sinon le calcul final donnera un résultat différent (sauf si elles ont le même « bid », auquel cas osef).
De plus cut -d\ -f1 < 07.input | sort -u | wc -l; wc -l 07.input nous retourne 1000 lignes pour chaque, on a donc bien des mains uniques dans les données en entrée.
En pratique on ne gagne rien, avec la cached_property sur le score, de toute façon on va calculer le score une seule fois par main, et ça coûte pas lourd comme comparaisons. Mais là aussi c'est lié finalement à la toute petite quantité de données.

Bref, il ne nous reste plus qu'à résoudre, avec la fonction sorted() qui va faire tout le boulot à notre place, magique !

ex1 = sum((i + 1) * hand.bid for i, hand in enumerate(sorted(hands1)))
ex2 = sum((i + 1) * hand.bid for i, hand in enumerate(sorted(hands2)))

Et enfin, voilà le code de la méthode Hand.score, là où on se rend compte que tous les magiciens ont leur « trucs ». Je ne sais pas si j'aurais pu faire plus « intelligent », mais c'est assez clair je pense.

    @cached_property
    def score(self):
        cards = set(self.hand)  # all kind of cards in hand
        nb = len(cards)  # number of different cards, including jokers
        jokers = self.hand.count("0")  # number of jokers in hand
        if nb == 5:  # abcde, abcd*
            return HandType.OnePair if jokers else HandType.HighCard
        if nb == 4:  # aabcd, aabc*, **abc
            return HandType.ThreeOfAKind if jokers else HandType.OnePair
        if nb == 3:  # aaabc, aabbc, aaab*, aabb*, aa**c, ***bc
            cards.discard("0")  # Jokers are already counted
            card = cards.pop()  # draw a non-joker card
            c = self.hand.count(card)
            if c == 2:  # aabbc, aabb*, aa**c
                return [HandType.TwoPairs, HandType.FullHouse, HandType.FourOfAKind][jokers]
            if c == 3:  # aaabc, aaab*
                return HandType.FourOfAKind if jokers else HandType.ThreeOfAKind
            # non-joker card U is unique: aaabU, aabbU, aaaU*, aa**U, ***bU
            card = cards.pop()
            if self.hand.count(card) == 2:  # aabbU, aa**U
                return HandType.FourOfAKind if jokers else HandType.TwoPairs
            # aaabU, aaaU*, ***bU
            return HandType.FourOfAKind if jokers else HandType.ThreeOfAKind
        if nb == 2:  # aaa**, ***aa, aaaa*, ****a
            if jokers:  # whatever, jokers makes it Five of a kind
                return HandType.FiveOfAKind
            card = cards.pop()
            if self.hand.count(card) in (2, 3):  # aaabb
                return HandType.FullHouse
            # aaaab
            return HandType.FourOfAKind
        return HandType.FiveOfAKind

Et voilà :)
Et une fois n'est pas coutume : PyPy est largement moins efficace que Python là-dessus, on passe de 70 à 370 millisecondes, même avec les 150ms de démarrage de PyPy, c'est amplement trois fois moins bon pour l'exécution en elle-même.
Dans tous les cas : pas de quoi faire chauffer la pièce à coups de CPU.

• Yth.

Ah, je parlais juste en brute force, comme ça tu traites les graines par paquets de 1 million seulement, et ça prend moins de RAM. Que 850 millions par exemple, qui peuvent mettre une machine à genoux, et invoquer l'OOM.

• Yth.

Ça fait en effet pas mal de possibilités, puisque ma réponse est de plus de 34 millions de façon de gagner.

En fait, la meilleure course c'est simplement d'appuyer sur le bouton la moitié du temps et de laisser filer l'autre moitié.
Mais c'est pas ça qu'on demande, on demande juste de calculer les racines d'un polynome du second degré, et de mesurer l'intervalle entre les deux.

Ok, pour l'exercice 1, on modélise quand même, parce que ça a l'air plus simple que de réfléchir :

races = list(zip(*[
  [
    int(y.strip())
    for y in x.split(":")[-1].strip().split()
  ] for x in sys.stdin.read().strip().splitlines()
][:2]))

ex1 = reduce(lambda x, y: x * y, (
  sum(
    1
    for i in range(1, time)
    if i * (time - i) > distance
  )
  for time, distance in races
))
print(f"Number of ways to win, score : {ex1}")

Après, on prend peur, et on se dit que ça va être énorme, les chiffres sont gros, blabla, donc résolution de polynôme, cas limites, soustraction, résultat :

data = sys.stdin.read().strip().splitlines()
time, distance = (
  int(x.split(":")[-1].strip().replace(" ", ""))
  for x in data[:2]
)
print(f"Big race time {time}, high score : {distance}")
Δ = math.sqrt(time**2 - 4 * distance)  # Ok, this is √Δ and not Δ
r1 = math.floor((time - Δ) / 2 + 1)  # if r is an integer, it's not a winning race, it's a tie
r2 = math.ceil((time + Δ) / 2 - 1)   # so we make sure to handle that edge case.
# All winning solutions are between r1 and r2, included, hence:
print(f"Result = {r2 - r1 + 1}")

Bon, et puis au final on se dit que 35 millions c'est pas si lourd, alors on tente la force brute :

ex2 = 0
for i in range(1, time):
    if i * (time - i) > distance:
        ex2 += 1
print(f"Brute Score : {ex2}")

Et… des petites comparaisons :
PyPy3, polynôme : 0,171s
PyPy3, force brute : 0,268s
Python3, polynôme : 0,031s
Python3, force brute : 12,634s

D'accord, PyPy a un surcoût au démarrage, environ 0.15 secondes, donc la solution efficace en python3 est plus rapide.
Mais la force brute, bigre, quelle différence, dans les 50 fois plus rapide !

Et bref, dans tous les cas, on peut y aller comme un bourrin, ou intelligemment, ya rien de difficile dans ces exercices.

• Yth.

Ici on peut faire du brute-force tout découpé, donc éviter de blinder la RAM.
Par exemple si tu redécoupes tous tes intervalles en intervalles de 1 million, et un dernier pour les éléments qui restent.
Tu vas avoir quelque chose comme 2500/2600 intervalles, que tu traites séquentiellement, et la RAM utilisée n'est « que » pour une liste de 1 million d'éléments.

La RAM est basse donc tu ne fais presque que du pompage de CPU, sans mettre la machine à genoux, et ça tourne a peu près vite.

Chez moi, sur la petite machine (i3@2,3Ghz), ça fait environ 1h, en mono-thread, bien sûr (et avec PyPy, surtout pas CPython pour ça !).
Sur l'autre qui a 4 coeurs, en découpant le travail en quatre pour profiter de tous les coeurs, ça se termine en moins d'un quart d'heure.

Donc ça reste « facile » en force brute :)

• Yth.

Mon premier algo a fait fondre deux CPU en même temps, sur deux machines différentes, avec partage du travail à faire, pour pondre le résultat en pas loin de 40 minutes, avec PyPy.
Voici le second, celui qui fonctionne, qui prends moins d'un dixième de seconde pour résoudre tout le problème, et de façon assez élégante en plus, juste en exploitant le range() de Python.
C'est pour ça que dans l'algo présenté, j'utilise la même méthode pour les deux exercices, avec des range de un élément pour l'exercice 1, je n'ai pas codé ça dès le début.
Et non, je ne posterai pas mon premier algo, très bien pour l'exo 1, mais très crado pour le 2 ^{^}

Les données d'abord, je distingue les graines et le reste :

def seedranges(seeds):
  def __iter():
    while seeds:
      src = seeds.pop(0)
      dst = seeds.pop(0)
      yield range(src, src + dst)
  return __iter()

datas = [x.strip().split(" ") for x in sys.stdin]
seeds = [int(x) for x in datas.pop(0)[1:]]
# Exercice 1
values = [range(seed, seed + 1) for seed in seeds]
# Exercice 2
values = list(seedranges(seeds))

Les graines sont donc une liste de range().

Ensuite les transformations pour trouver les correspondances, on va avoir une classe avec deux listes : les range() source, et les opérations à appliquer sur chaque range, qui sont simplement un entier relatif à ajouter. Et puis les noms des éléments depuis et vers lesquels on transforme :

class Map():
  ranges = None
  operations = None
  def __init__(self, *ranges):
    self.ranges = []
    self.operations = []
    for dst, src, size in ranges:
      self.ranges.append(range(src, src + size))
      self.operations.append(dst - src)

def readmap(lines):
  ranges = None
  mapname = None
  for line in lines:
    if not line[0]:
      if mapname:
        yield mapname[0], mapname[2], Map(*ranges)
      ranges = None
    elif ranges is None:
      mapname = line[0].split("-")  # ['seed', 'to', 'soil']
      ranges = []
    else:
      ranges.append(int(x) for x in line)
  yield mapname[0], mapname[2], Map(*ranges)

converters = {
  src: (dst, mapping)
  for src, dst, mapping in readmap(datas)
}

Pour les calculs en eux-même, la méthode qui fait le travail est ajoutée à Map(), et la résolution est assez simple au bout du compte.
On calcule tout simplement les superpositions de deux range() : on va avoir un range d'éléments non traité avant un range de transformation, un range d'éléments non traités après un range de transformation, et enfin un range transformé. On boucle sur toutes les opérations disponibles, en remettant dans le pot les range non traités (avant et après) et en retournant (yield est ton ami) les range traités.
On n'oublie pas à la fin de retourner tous les range ayant échappés aux transformations, car ils restent identiques selon l'énoncé.
Le code est vraiment simple grâce aux itérateurs, avec yield, on ne se fatigue pas à construire une liste, à tester des trucs : on a une donnée finale ? yield, et on continue, elle est envoyée, et on ne s'en occupe plus.
Et on utilise les propriétés des range(), au début je voulais faire des if élément in range_operation qui est immédiat, mais en fait on n'en a pas besoin. La seule subtilité c'est qu'un range est Vrai s'il contient en pratique des éléments, et Faux sinon, donc range(20, 10) c'est faux.
if before signifie donc simplement : si on a des éléments non traités avant.

class Map():
  [...]
  def __call__(self, sources):
    for i, r in enumerate(self.ranges):
      op = self.operations[i]
      new_sources = []
      while sources:
        src = sources.pop()
        before = range(src.start, min(src.stop, r.start))
        after = range(max(src.start, r.stop), src.stop)
        transformed = range(max(src.start, r.start) + op, min(src.stop, r.stop) + op)
        if before:
          new_sources.append(before)
        if after:
          new_sources.append(after)
        if transformed:
          yield transformed
      sources = new_sources
    for src in sources:
      yield src

Enfin le résolution se fait à l'identique pour les deux parties, avec la bonne valeur initiale pour values :

while src in converters:
  dst, converter = converters[src]
  # print(f"Converting from {src} to {dst}")
  values = list(converter(values))
  src = dst
print("Closest location is {}".format(
  min(v.start for v in values)
))

Pour info, faire les 7 moulinettes sur une liste de 850 millions d'éléments, même avec PyPy, ça prend dans les dix/quinze minutes, et je parle pas de la RAM.
Comme quoi ça peut valoir le coup de regarder les données à traiter pour savoir où on va se planter, avant de coder…
Cela dit, un algo non optimisé, même à 45 minutes de calcul réparti sur deux machines (j'aurais pu aller plus vite en parallélélisant sur les multiples proc des machines, un range initial par exécution, en moins de 15 minutes c'était plié), c'est plus rapide que de réinventer un algorithme, le coder, le valider.

• Yth.

"zero" n'est pas dans les données, mais l'ajouter chez moi permet d'avoir la correspondance entre les textes et les index de la liste Python qui commence à 0.

C'est une optimisation facile de lisibilité on va dire.

Par ailleurs, j'ai codé sans regarder les données justement, donc en fait je ne savais pas que le zéro était inutilisé.
Dans l'idée, il aurait pu l'être.

• Yth.