Project Euler 43

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

ライブラリで順列を出して判定すると非常に遅い。

import Data.List

primes = [2,3,5,7,11,13,17]
numerize a = foldl (\x y -> x * 10 + y) 0 a
is_valid a [] = True
is_valid a (p:ps) = if mod n p /= 0 then False else is_valid (tail a) ps
                    where n = numerize (take 3 a)
a = filter (\a -> is_valid (tail a) primes) (permutations [0..9])
main = print(sum (map numerize a))

後ろ3桁から順に素数で割り切れる数だけ残して前に数字を加える、という作業をしていけば範囲が絞れて速い。

primes = [2,3,5,7,11,13,17]
numerize a = foldl (\x y -> x * 10 + y) 0 a

increment a = map (\e -> [e] ++ a) (filter (\e -> notElem e a) [0..9])
mul a p = filter (\e -> mod (numerize (take 3 e)) p == 0)
                                (concat (map increment a))
b = [1,1] ++ (reverse primes) ++ [1]
main = print(sum(map numerize (foldl mul [[]] b)))