Project Euler 75

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

ピタゴラスの数の生成式を使って周囲の長さをリストにする。例えば60までなら、

[12,24,36,48,60,30,60,40,56]

これをMapに入れようとしたが、メモリが足りない。

import qualified Data.Map as M
import Data.List

l = 15 * 10^5
perimeters = [ 2 * k * m * n | m <- [2..div l 6],
                               n <- [m+1..min (m*2-1) (div l (2*m))],
                               k <- [1..(div l (2*m*n))],
                               gcd m n == 1, odd n ]

update [] m = m
update (x:xs) m = update xs (M.insert x n m) where
        n = case M.lookup x m of
                Just p  -> p + 1
                Nothing -> 1

m = update perimeters M.empty
main = print (length (filter (\(p,n) -> n == 1) (M.toList m)))

リストを並べ替える。

[12,24,30,36,40,48,56,60,60]

そして続いていないものを数える。

import Data.List

l = 15 * 10^5
perimeters = [ 2 * k * m * n | m <- [2..div l 6],
                               n <- [m+1..min (m*2-1) (div l (2*m))],
                               k <- [1..(div l (2*m*n))],
                               gcd m n == 1, odd n ]

count [p] b = if b then 1 else 0
count (p:q:ps) b = if b && p /= q then (count (q:ps) True) + 1
                                  else count (q:ps) (p /= q)

main = print (count (sort perimeters) True)