Re: Solution en Haskell

Après quelques optimisations
200ms pour la partie 1 et 800ms pour la partie 2.

L'idée est qu'au lieu de dire qu'un noeud du graphe est un couple (position, direction) avec 4 directions possibles, je dis qu'un noeud est un couple (position, booléen)
ou le booléen m'indique si je me déplace horizontalement ou verticalement.
Ca fait 2 fois moins de noeuds dans le graphe. Du coup, logiquement, ça divise le temps d'exécution par deux (et même plus avec quelques autres optimisations).

Le code qui change:

type Grid = Matrix U Int
type Position = V2 Int
type Direction = Bool -- True -> horizontal | False -> vertical
neighbors :: [Int] -> Grid -> (Position, Direction) -> [((Position, Direction), Int)]
neighbors nbSteps grid (pos, dir) =
 [ ((nextPos, not dir), weight)
 | i <- nbSteps
 , let vDir = if dir then V2 0 1 else V2 1 0
 , let nextPos = pos + fmap (*i) vDir
 , isJust (grid !? toIx2 nextPos)
 , let range = if i > 0 then [1..i] else [i..(-1)]
 , let weight = sum [grid ! toIx2 (pos + fmap (*j) vDir) | j <- range]
 ]
solveFor :: [Int] -> Grid -> Maybe Int
solveFor nbSteps grid = dijkstra' (neighbors nbSteps' grid) (`elem` ends) starts where
 nbSteps' = nbSteps ++ map negate nbSteps
 Sz2 h w = A.size grid
 starts = (V2 0 0,) <$> [True, False]
 ends = (V2 (h-1) (w-1),) <$> [True, False]