Re: Solution en Haskell

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.