{-# 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