Project Euler 解答

Project Euler Problem 092

Project Euler Problem 092

import Data.Char
import Data.Array
import Data.List
import qualified Data.Foldable as F
square n = n*n -- (^2)でも代用できる
chain :: Show a => a -> Int
chain n = sum $ map (square . digitToInt) $ show n
test n = case n of
  1 -> False
  89 -> True
  _ -> test (chain n)
-- ナイーブな実装。160.68sec 8581146
ans1 = length $ filter id $ map test [1..10000000]

-- キャッシュ版
test2 :: Array Int Bool
test2 = ar
  where
    n = 10000000
    ar = listArray (1,n) [imp x | x<-[1..n]]
    imp :: Int -> Bool
    imp x = if x' < x then ar!x'
            else test x'
      where x' = chain x
ans2 = length $ filter id $ F.toList test2 -- 40.22sec       
ans3 = F.foldl (\a x -> if x then a+1 else a) 0 test2 -- 51.89secs

-- 8581146
main = print ans2

since 2013