81 lines
2.8 KiB
Haskell
81 lines
2.8 KiB
Haskell
{-# LANGUAGE TupleSections #-}
|
|
|
|
import AStar
|
|
import Data.List (findIndex, elemIndex)
|
|
import Data.Maybe (fromJust, mapMaybe)
|
|
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)
|
|
|
|
allGridPositions :: Grid a -> [Pos]
|
|
allGridPositions grid = concatMap (\y -> map (, y) [0 .. gridWidth grid - 1]) [0 .. gridHeight grid - 1]
|
|
|
|
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)
|
|
|
|
findShortestSteps :: Grid Elevation -> Pos -> Pos -> Maybe Int
|
|
findShortestSteps grid start end = flip (-) 1 . length . snd <$> pathfind grid start end
|
|
|
|
-- hacky way of doing this; you'd preferably pathfind from the end to any `a` but i didn't want to write a heuristic for that so oh well
|
|
findShortestStart :: Grid Elevation -> Pos -> Int
|
|
findShortestStart grid end = minimum $ mapMaybe (flip (findShortestSteps grid) end) possibleStartPositions
|
|
where
|
|
possibleStartPositions = filter ((== A) . (grid !!!)) allPositions
|
|
allPositions = allGridPositions grid
|
|
|
|
main = interact $
|
|
show
|
|
. (\(grid, _, end) -> findShortestStart grid end)
|
|
. parseGrid |