import Data.Array
import Data.Array.ST
import Control.Monad
import Control.Monad.ST

main :: IO ()
main = do
--  input <- readFile "input-test"
--  let bounds = ((0,0), (6,6))
--  let n = 12
  input <- readFile "input"
  let bounds = ((0,0), (70,70))
  let n = 1024
  let coords = map readPair . lines $ input
--  print $ part1 bounds (take n coords)
  print $ part2 bounds coords


part1 bounds@((minx,miny), (maxx,maxy)) coords =
  let grid = array bounds [((i,j), if (i,j) `elem` coords then '#' else '.') |
                           i <- [minx..maxx], j <- [miny..maxy]]
      dist = findDistances grid (0,0)
  in dist!(maxx,maxy)

-- inefficient but what the hell
part2 bounds coords = try 0
  where try n =
          let ok = (part1 bounds (take n coords)) /= maxInt
          in if ok then try (n+1)
             else coords!!(n-1)

maxInt = maxBound :: Int

-- dijkstra algorithm
findDistances :: Array (Int,Int) Char -> (Int,Int) -> Array (Int,Int) Int
findDistances grid start = runST $ do
    let ((miny,minx), (maxy,maxx)) = bounds grid
    dist <- newArray ((miny,minx), (maxy,maxx)) maxInt :: ST s (STArray s (Int,Int) Int)
    writeArray dist start 0
    search dist [start]
    frozen <- freeze dist
    return frozen
  where search dist [] = return ()
        search dist current = do
          let neighbours = concatMap (getFromTo grid) current
          next <- forM neighbours $ \(from, to) -> do
            hereDist <- readArray dist from
            oldDist <- readArray dist to
            if (hereDist+1) < oldDist then do
              writeArray dist to (hereDist+1)
              return [to]
            else return []
          search dist (concat next)

getFromTo grid pos =
  let n = getNeighbours grid pos
      free = filter (\p -> grid!p == '.') n
  in zip (repeat pos) free

getNeighbours arr (i,j) = filter (inRange (bounds arr)) [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]

readPair :: String -> (Int,Int)
readPair s = toPair $ read ("[" ++ s ++ "]")

toPair [a,b] = (a,b)