Project Euler 31,32

Problem 31

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


使う最大のコインが決まっているときの総額の作り方の場合の数の配列をリストにする。
ちょっとややこしくなるとなかなか書けない。



import Data.Array

n = 200
coins = [ 1, 2, 5, 10, 20, 50, 100, 200 ]
f ary coin amount = sum([ ary!(amount - coin * k) |
k <- (takeWhile (\k -> amount >= k * coin) [1..]) ])
g ary coin = [ f ary coin m | m <- [0..n] ]
add a b = [ x + y | (x, y) <- zip a b ]
update [] coin = [ 0 | k <- [0..n] ]
update (ary:a) coin = add (g ary coin) (update a coin)
calc a [] = a
calc a (c:cs) = calc (a ++ [array (0, n) (zip [0..n] (update a c))]) cs
a = calc [array (0, n) [ (k, 1) | k <- [0..n] ]] (tail coins)
main = print(sum (map (!n) a))

Problem 32

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

(1桁)×(4桁)または(2桁)×(3桁)



import qualified Data.Set as S

digits 0 = []
digits n = (digits (div n 10)) ++ [mod n 10]
is_pandigital [] n = n == 2^10 - 2
is_pandigital (p:ps) n = if (mod (div n (2^p)) 2) == 1 then False
else is_pandigital ps (n + (2^p))

g :: Int -> Int -> [Int]
g n m = map (\(k,l) -> l) (filter
(\(k,l) -> is_pandigital (digits n ++ digits k ++ digits l) 0)
(takeWhile (\(_,l) -> l < 10^4)
(map (\k -> (k, n * k)) [10^(m-1)..10^m-1])))

f m = concat (map (\n -> g n (5 - m)) [(div (10^m-1) 9)..10^m-1])
main = print(sum (S.elems (S.fromList (f 1 ++ f 2))))