66 lines
2.1 KiB
Haskell
66 lines
2.1 KiB
Haskell
import AStar
|
|
import Data.List (findIndex, elemIndex)
|
|
import Data.Maybe (fromJust)
|
|
import GHC.Utils.Misc (uncurry3)
|
|
|
|
data Elevation = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
|
|
deriving (Show, Eq, Enum, Bounded)
|
|
|
|
type Pos = (Int, Int)
|
|
type Grid a = [[a]]
|
|
|
|
(!!!) :: Grid a -> Pos -> a
|
|
(!!!) grid (x, y) = grid !! y !! x
|
|
|
|
findPos :: (Eq a) => a -> Grid a -> Maybe Pos
|
|
findPos target grid = do
|
|
y <- findIndex (target `elem`) grid
|
|
x <- elemIndex target (grid !! y)
|
|
Just (x, y)
|
|
|
|
gridMap :: (a -> b) -> Grid a -> Grid b
|
|
gridMap f = map (map f)
|
|
|
|
gridWidth :: Grid a -> Int
|
|
gridWidth = length . head
|
|
gridHeight :: Grid a -> Int
|
|
gridHeight = length
|
|
|
|
parseElevation :: Char -> Elevation
|
|
parseElevation 'S' = A
|
|
parseElevation 'E' = Z
|
|
parseElevation x = toEnum (fromEnum x - 97)
|
|
|
|
parseGrid :: String -> (Grid Elevation, Pos, Pos)
|
|
parseGrid g = (gridMap parseElevation gridChars, fromJust start, fromJust end)
|
|
where
|
|
start = findPos 'S' gridChars
|
|
end = findPos 'E' gridChars
|
|
gridChars = lines g
|
|
|
|
isValidTravel :: Grid Elevation -> Pos -> Pos -> Bool
|
|
isValidTravel grid (x1, y1) (x2, y2)
|
|
| x2 < 0 || x2 >= gridWidth grid || y2 < 0 || y2 >= gridHeight grid = False
|
|
| otherwise = diff <= 1
|
|
where
|
|
diff = height2 - height1
|
|
height1 = fromEnum $ grid !!! (x1, y1)
|
|
height2 = fromEnum $ grid !!! (x2, y2)
|
|
|
|
getAdjacentPositions :: Grid Elevation -> Pos -> [(Pos, Int)]
|
|
getAdjacentPositions grid (x, y) = zip validPositions [1000000000..] -- spent about an hour debugging for this to be the fix
|
|
where
|
|
validPositions = filter (isValidTravel grid (x, y)) allPositions
|
|
allPositions = [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]
|
|
thisHeight = fromEnum $ grid !!! (x, y)
|
|
|
|
distance :: Pos -> Pos -> Int
|
|
distance (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)
|
|
|
|
pathfind :: Grid Elevation -> Pos -> Pos -> Maybe (Int, [Pos])
|
|
pathfind grid start end = astarSearch start (== end) (getAdjacentPositions grid) (distance end)
|
|
|
|
main = interact $
|
|
show
|
|
. flip (-) 1 . length . snd . fromJust . uncurry3 pathfind
|
|
. parseGrid |