Project Euler 解答

Project Euler Problem 034

Project Euler Problem 034

import Control.Monad
import Data.Char
import Data.List

--9!*9が326万なので、330万は簡単にわかる上限
facl :: [Integer]
facl = scanl1 (*) [1..]
fac :: (Enum a, Num a) => a -> a
fac n = product [1..n]

tes :: Show a => a -> Bool
tes n = test (map (fromIntegral . digitToInt) $ show n)
test :: [Integer] -> Bool
test lists = imp lists 0  == val lists where
  imp :: [Integer] -> Integer -> Integer
  imp [] sum_ = sum_
  imp (x:xs) sum_ = imp xs (fac x+sum_)
val :: [Integer] -> Integer
val lists = foldl1' (\acc x -> acc*10+x) lists
st :: [Char] -> [Int]
st str = map digitToInt str
r :: [Integer]
r=[1..9]

list :: [Integer]
list = [ x | x<-[3..3270000],tes x] --[145,40585]
ans :: Integer
ans = sum list


-- 重複組み合わせ
hck :: (Eq a1, Num a1) => [a] -> a1 -> [[a]]
hck _  0 = [[]]
hck xs n = loop (func ([], xs)) n where
          loop xss 1 = [xs | (xs, _) <- xss]
          loop xss n = loop (concatMap func xss) (n - 1)
          func (xs, ys) = [(xs ++ [z], zs) | zs@(z : _) <- tails ys]

--重複組み合わせが既知として
faclist :: [Integer]          
faclist = map fac [1..9]
faccoms :: Integer -> [Integer]
faccoms n = [sum x |x<-hck faclist n,test (map (fromIntegral.digitToInt) $ show $  sum x)]
ans2 :: Integer
ans2 = (sum $ nub $ sort $ concatMap faccoms [1..7]) - fac 1 - fac 2

-- 40730
main :: IO ()
main = print ans2

since 2013