Solution en Haskell

Je trouve que ce problème ressemble à celui d'hier.
Il s'agit encore d'un parcours dans un graphe.
Ici, le graphe est pondéré. On va donc utiliser l'algorithme de Dijkstra au lieu d'un simple parcours en profondeur/largeur.
Comme hier, la direction est importante. Les sommets du graphe seront donc les paires (Position, Direction).
Les voisins d'un sommet ne seront pas les positions adjacentes dans la grille mais celle à distance entre 1 et 3 pour la partie 1 et entre 4 et 10 pour la partie 2.
La direction devra également changer à chaque fois.
Le poids des arêtes sera la somme des chiffres indiqués sur chacune des tuiles que l'on a parcouru durant ce déplacement.

Dans mon code, j'utilise la fonction dijkstra' que j'ai également écrite pour des problèmes des années précédentes.
Voici sa signature

dijkstra' :: (Hashable v, Real w) => (v -> [(v, w)]) -> (v -> Bool) -> [v] -> Maybe w

Le type v est celui des sommets et le type w est celui des poids des arêtes.
La fonction prend en entrée
- une fonction de voisinage qui à chaque sommet associe une liste des sommets voisins ainsi que le poids de l'arête entre les deux sommets,
- une fonction de prédicat pour le sommet de fin,
- un ensemble de sommets de départ.
et renvoit la distance entre un des sommets de départs et un des sommets de fin si un chemin existe.

Voici le code (sans les imports)

import AOC.Prelude
import Data.Char (digitToInt)
import Data.Massiv.Array (Matrix, (!), (!?), U, Comp(Seq), Sz(Sz2))
import qualified Data.Massiv.Array as A
import AOC (aoc)
import AOC.V2 (V2(..), adjacent, toIx2)
import AOC.Parser (Parser, sepEndBy1, eol, digitChar, some)
import AOC.Search (dijkstra')
type Grid = Matrix U Int
type Position = V2 Int
type Direction = V2 Int
directions :: [V2 Int]
directions = adjacent (V2 0 0)
parser :: Parser Grid
parser = A.fromLists' Seq <$> some (digitToInt <$> digitChar) `sepEndBy1` eol
neighbors :: [Int] -> Grid -> (Position, Direction) -> [((Position, Direction), Int)]
neighbors nbSteps grid (pos, dir) =
 [ ((nextPos, nextDir), weight)
 | i <- nbSteps
 , nextDir <- directions
 , nextDir /= dir && nextDir /= -dir
 , let nextPos = pos + fmap (*i) nextDir
 , isJust (grid !? toIx2 nextPos)
 , let weight = sum [grid ! toIx2 (pos + fmap (*j) nextDir) | j <- [1..i]]
 ]
solveFor :: [Int] -> Grid -> Maybe Int
solveFor nbSteps grid = dijkstra' (neighbors nbSteps grid) (`elem` ends) starts where
 Sz2 h w = A.size grid
 starts = [(V2 0 0, V2 1 0), (V2 0 0, V2 0 1)]
 ends = [(V2 (h-1) (w-1), V2 0 1), (V2 (h-1) (w-1), V2 1 0)]
solve :: Text -> IO ()
solve = aoc parser (solveFor [1..3]) (solveFor [4..10])