eggDrop/egg.hs

import Data.Map (Map, (!))
import qualified Data.Map as Map

loeb :: Functor f => f (f a -> a) -> f a
loeb x = go where go = fmap ($ go) x

loebify :: Integer -> Integer -> (Map (Integer, Integer) Integer -> Integer)
loebify n k
  | k == 1 || k == 0 || n == 1 = const k
  | otherwise = (\m -> 1 + (minimum $ map (\i -> f m i) [1..k]))
  where
    f m i = max (m ! ((n-1),(i-1))) (m ! (n,(k-i)))

solve :: Integer -> Integer -> Integer
solve n k = (loeb m) ! (n,k)
  where
    f (n,k) = ((n,k), loebify n k)
    m = Map.fromList $ map f [ (x,y) | x <- [1..n], y <- [0..k]]

-----------------
-- gross io bs --
-----------------

main :: IO ()
main = do
  l <- getLine
  let (n:k:_) = map read $ words l :: [Integer]
  putStrLn $ show $ solve n k