Project Euler 60

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

Setが自由に使うのが難しい。しかたがないので、上限を倍々していく。とても遅い。

import qualified Data.Set as S

min_sum n = min_s where
    is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes)
    primes = 2:(filter is_prime [3,5..])

    num_digits n = head (filter (\m -> 10^m > n) [1..])
    cat n m = n * 10^(num_digits m) + m

    memo = f [ (p, q) | p <- takeWhile (<n) primes,
            q <- (takeWhile (\q -> q < p && p + q < n) primes),
                                            is_conn (p,q) ] S.empty
        where
            f [] s = s
            f (x:xs) s = f xs (S.insert x s)
            is_conn (m,n) = is_prime (cat m n) && is_prime (cat n m)

    is_connected p q = S.member (p,q) memo

    add_prime :: [[Int]] -> [[Int]]
    add_prime a = [ p:b | p <- takeWhile (<n) primes,
                b <- takeWhile (\e -> (head e) < p) a,
                sum(b) + p < n && is_valid p b ] where
                    is_valid p e = all (is_connected p) (reverse e)

    a = foldr (\x y -> add_prime y) (map (\p -> [p]) primes) [1..4]
    limit_sum = if length a == 0 then 0 else sum (head a)
    min_s = foldr min limit_sum
            (map sum (takeWhile (\e -> (head e) < limit_sum) a))

main = print (head (filter (>0) (map min_sum a))) where
    a = 1000:[ n * 2 | n <- a ]