Solution en Haskell

100 ms pour la partie 1, 4s pour la partie 2.

J'ai trouvé le problème assez simple aujourd'hui. En tout cas plus simple que les jours précédents. Dommage que je me sois levé tard.

Tout d'abord, remarquons que le problème qu'on essaie de résoudre (Longest Path) est NP-difficile. Ce qui ne veut pas dire qu'on ne va réussir car il n'y a pas tellement de choix et donc de backtrack à faire.

La première partie est du backtracking classique. Dans la deuxième partie, l'espace d'exploration augmente considérablement. Mais on se rend qu'il y a de longs couloirs, c'est à dire une suite de sommets de degré 2.

On va dans compresser la grille de cette manière:
on dit qu'une tuile est intéressante si c'est la tuile de départ, d'arrivée ou si c'est une jonction, c'est à dire un sommet de degré au moins 3.
Et pour chaque tuile intéressante, on va chercher dans chaque direction la prochaine tuile intéssante ainsi que la distance qui les sépare.
On va appliquer notre algo de backtracking sur cette instance.

Voici le code:
comme d'habitude, on va essayer d'être le plus générique possible et on va définir une fonction longestPath qui prend en entrée un sommet de départ, un sommet d'arrivée et une fonction de voisinages. Elle s'applique donc à n'importe quelle strucutre et pas seulement aux grilles. On va la mettre dans ma librairie de fonctions de recherche dans un graphe.

longestPath :: Hashable a => (a -> [(a, Int)]) -> a -> a -> Int
longestPath neighbors start dest = go Set.empty 0 start where
 go visited len pos 
 | pos == dest = len
 | otherwise = maximumDef 0 [ go (Set.insert pos visited) (len+len') next
 | (next, len') <- neighbors pos
 , not $ next `Set.member` visited
 ]

Ensuite, vient le code du problème à proprement parler.
Tout d'abord les types utilisés et le parsing. Rien de bien compliqué.

data Tile = Path | Forest | North | South | West | East deriving (Eq)
type Grid = Matrix B Tile
parser :: Parser Grid
parser = fromLists' Seq <$> some tile `sepEndBy1` eol where
 tile = choice [Path <$ ".", Forest <$ "#", North <$ "^", South <$ "v", West <$ "<", East <$ ">"]

Ensuite, on définit une fonction de voisnage pour la partie 1.

neighbors1 :: Grid -> V2 Int -> [(V2 Int, Int)]
neighbors1 grid p = case grid ! toIx2 p of
 Path -> [ (p', 1)
 | p' <- adjacent p
 , let tile = grid !? toIx2 p'
 , tile /= Nothing && tile /= Just Forest
 ]
 North -> [(p - V2 1 0, 1)]
 South -> [(p + V2 1 0, 1)]
 West -> [(p - V2 0 1, 1)]
 East -> [(p + V2 0 1, 1)]
 _ -> error "neighbors: cannot happen"
part1 :: Grid -> Int
part1 grid = longestPath neighbors start dest where
 neighbors = neighbors1 grid
 Sz2 h w = size grid
 start = V2 0 1
 dest = V2 (h-1) (w-2)

Pour la partie 2, on définit une fonction de voisinage qui ne prend pas en compte les pentes.

neighbors2 :: Grid -> V2 Int -> [V2 Int]
neighbors2 grid p = [ p' 
 | p' <- adjacent p
 , let tile = grid !? toIx2 p'
 , tile /= Nothing && tile /= Just Forest
 ]

et on définit la fonction de compression de grille.

compressGrid :: Grid -> V2 Int -> V2 Int -> Matrix B [(V2 Int, Int)]
compressGrid grid start end = makeArray Seq (Sz2 h w) \(Ix2 r c) ->
 let pos = V2 r c
 neighbors = neighbors2 grid pos
 in
 if pos == start || pos == dest || length neighbors > 2 then
 [followPath next pos 1 | next <- neighbors]
 else
 []
 where
 followPath pos pred len =
 case neighbors2 grid pos of
 [next1, next2] | next1 == pred -> followPath next2 pos (len+1)
 | otherwise -> followPath next1 pos (len+1)
 _ -> (pos, len)
 Sz2 h w = size grid
part2 :: Grid -> Int
part2 grid = longestPath neighbors start dest where
 compressed = compressGrid grid start end
 neighbors p = compressed ! toIx2 p
 Sz2 h w = size grid
 start = V2 0 1
 dest = V2 (h-1) (w-2)