53 lines
1.4 KiB
Haskell
53 lines
1.4 KiB
Haskell
import Data.List
|
|
import Data.Maybe
|
|
|
|
type Path = ([String], [(Int, Int)])
|
|
|
|
main :: IO ()
|
|
main = do
|
|
input <- lines <$> readFile "input"
|
|
let s = findLetter 'S' input
|
|
let e = findLetter 'E' input
|
|
print $ step 'E' (input, []) [s]
|
|
print $ step 'a' (input, []) [e]
|
|
|
|
findLetter :: Char -> [String] -> (Int, Int)
|
|
findLetter c = f <*> fromJust . findIndex (/= Nothing) <$> map (elemIndex c)
|
|
where
|
|
f x y = (head $ catMaybes x, y)
|
|
|
|
step :: Char -> Path -> [(Int, Int)] -> Int
|
|
step c (field, visited) active
|
|
| c `elem` (map f active) = 0
|
|
| otherwise = 1 + step c (field, active ++ visited) next
|
|
where
|
|
next = nub $ sort $ concatMap (nextSteps (c == 'E') (field, visited)) active
|
|
f x = field !! snd x !! fst x
|
|
|
|
nextSteps :: Bool -> Path -> (Int, Int) -> [(Int, Int)]
|
|
nextSteps up (field, visited) (x, y) =
|
|
[ (x + x', y + y')
|
|
| x' <- [-1 .. 1]
|
|
, x' + x >= 0
|
|
, x' + x < lenX
|
|
, y' <- [-1 .. 1]
|
|
, y' + y >= 0
|
|
, y + y' < lenY
|
|
, abs x' /= abs y'
|
|
, let a = field !! (y + y') !! (x + x')
|
|
in (a `elem` reachables || (a == 'E' && current == 'z'))
|
|
, (x + x', y + y') `notElem` visited
|
|
]
|
|
where
|
|
lenX = length $ head field
|
|
lenY = length field
|
|
char = field !! y !! x
|
|
current
|
|
| char == 'S' = 'a'
|
|
| char == 'E' = 'z'
|
|
| otherwise = char
|
|
reachables =
|
|
if up
|
|
then ['a' .. succ current]
|
|
else [pred current .. 'z']
|