Project Euler 31,32

Haskell

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))))