Project Euler 74

p74.hs

{- Runs in 14 seconds -}

import Data.List
import Data.Array
import Data.Digits

{- Is this the fastest factorial? Nope. Is it a fun, recursive and dynamic? Yup. -}

fac :: Integer -> Integer
fac n = facs !! (fromIntegral n) where
        facs = 1 : (zipWith (*) [1..] facs)

facplus :: Integer -> Integer
facplus a = sum $ map fac ds where
            ds = digits 10 a

{- The real beauty of the program. Possibly the only elegant thing I've ever written.
My first experiment with dynamic programming was a success! Haskell's lazy data structures
make it all possible. Quite nicely too.
This has to go up to 2177280 because facplus 999999 == 2177280. -}

chains = listArray (1,2177280) [ x:(takeWhile (\a -> a /= x) (chains ! (facplus x)) ) |x <- [1..2177280]]

main = do
  let ans = length $ filter (== 60) $ map (length.(chains !)) [1..1000000]
  print ans