-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day12.hs
executable file
·65 lines (56 loc) · 1.71 KB
/
Day12.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/env stack
{-
stack script
--resolver lts-20.2
--package vector
--package search-algorithms
-}
import Data.Char
import Data.Maybe
import Data.Vector (Vector, (!))
import qualified Data.Vector as V
import Algorithm.Search
data Matrix a = Matrix {
entries :: Vector a,
nRows :: Int,
nColumns :: Int
}
parse :: String -> Matrix Char
parse s = Matrix { entries = out , nRows = length rows, nColumns = length . head $ rows }
where
rows = lines s
out = V.fromList . concat $ rows
readAt :: Matrix a -> (Int, Int) -> Maybe a
readAt m (x, y)
| x < 0 || y < 0 || x > nColumns m - 1 || y > nRows m - 1= Nothing
| otherwise = Just (entries m ! (x + nColumns m * y))
find :: Eq a => Matrix a -> a -> Maybe (Int, Int)
find m v =
let pos i = (i `mod` nColumns m, i `div` nColumns m)
in fmap pos . V.elemIndex v . entries $ m
minSteps :: Matrix Char -> (Char -> Char -> Bool) -> Char -> Char -> Maybe Int
minSteps m validNeighbor from to = do
start <- find m from
fst <$> dijkstra neighbors cost target start
where
neighbors p@(x, y) =
let isValid other = or $ fmap (validNeighbor (fromJust . readAt m $ p)) . readAt m $ other
in filter isValid [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
cost _ _ = 1
target = (== to) . fromJust . readAt m
validUp :: Char -> Char -> Bool
validUp f t
| f == 'S' = t == 'a'
| t == 'E' = f == 'z'
| otherwise = ord t - ord f <= 1
validDown :: Char -> Char -> Bool
validDown f t
| f == 'E' = t == 'z'
| t == 'S' = f == 'a'
| otherwise = ord f - ord t <= 1
main :: IO ()
main = do
input <- readFile "data/12.txt"
let m = parse input
print . fromMaybe (-1) $ minSteps m validUp 'S' 'E'
print . fromMaybe (-1) $ minSteps m validDown 'E' 'a'