module Problem104 where

import Data.Array
import Data.List

lim :: Int
lim = 500000

main :: IO ()
main =
    print
        . head
        . filter
            (\x -> isPandigital (take 9 . show . fst $ fib1 ! x)
                && isPandigital (show $ fib2 ! x)
            )
        $ [1 ..]
  where
    fib1 :: Array Int (Integer, Int)
    fib1 = array (1, lim) (zip [1 ..] $ map fib1' [1 .. lim])
    fib1' x
        | x == 1                = (1, 0)
        | x == 2                = (1, 0)
        | extra == 0 && n == n' = (v'', n)
        | otherwise             = (read (take 20 $ show v''), n + extra)
      where
        extra    = max 0 (length (show v'') - 20)
        v''      = v + read (take (length (show v') - (n - n')) $ show v')
        (v , n ) = fib1 ! (x - 1)
        (v', n') = fib1 ! (x - 2)
    fib2 = array (1, lim) (zip [1 ..] $ map fib2' [1 .. lim])
    fib2' x
        | x == 1    = 1
        | x == 2    = 1
        | otherwise = (x' + x'') `mod` 1000000000
      where
        x'  = fib2 ! (x - 1)
        x'' = fib2 ! (x - 2)
    isPandigital xs = length xs == 9 && and (zipWith (==) ['1' .. '9'] (sort xs))
