Problem 92

http://projecteuler.net/index.php?section=problems&id=92

ナイーブな解法でも解けたが、少し遅かったので、ちょっと改良。

import Data.Char (digitToInt)
import Data.List (group)

next :: Int -> Int
next = sum.map (^2).map digitToInt.show

choose :: [a] -> Int -> [[a]]
choose _ 0 = [[]]
choose [] _ = []
choose (x:xs) (n+1) = (map (x:) . choose (x:xs)) n ++ choose xs (n+1)

count :: Eq a => [a] -> Integer
count xs = div (fact.length$xs) .product.map (fact.length).group$xs
    where fact n = product [1..toInteger n]

end :: Int -> Int
end = head.snd.break isEnd.iterate next
    where isEnd n = n==1||n==89
--main = print.length.filter((==89).end)$[1..10^7]
main =print.sum$[count x|x<-tail.choose [0..9] $ 7,end' x == 89]
    where end' = end.sum.map (^2)