Re: Solution en Haskell

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.