Shortest Path

gistfile1.hs

pathRecurse :: Board -> [Pos] -> Pos -> Pos -> Maybe [Pos]
pathRecurse b visited pa pb
    | pa == pb                = Just (visited++[pb])
    | null neighbors          = Nothing
    | null subpaths           = Nothing
    | otherwise               = Just ( minimumBy (comparePath) subpaths )
        where subpaths        = catMaybes ( map (\n -> pathRecurse b (visited++[pa]) n pb) neighbors)
              neighbors       = filter (\x -> (walkable b x) && not (x `elem` visited)) (getNeighbors b pa)
              comparePath x y = compare (length x) (length y)


path :: Board -> Pos -> Pos -> Maybe [Pos]
path b pa pb = pathRecurse b [] pa pb