# Project Euler Problem 31 Solution

## Question

In England the currency is made up of pounds, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p)

It is possible to make £2 in the following way:

1 × £1 + 1 × 50p + 2 × 20p + 1 × 5p + 1 × 2p + 3 × 1p

How many different ways can £2 be made using any number of coins?

main = print $length [1 | a <- [200,0], b <- [a,a-100..0], c <- [b,b-50..0], d <- [c,c-20..0], e <- [d,d-10..0], f <- [e,e-5..0], g <- [f,f-2..0]] $ ghc -O2 -o currency currency.hs
$time ./currency real 0m0.004s user 0m0.000s sys 0m0.004s ## Python #!/usr/bin/env python def ways_to_change(target, coins): if target == 0 or len(coins) == 1: return 1 else: coins = sorted(coins) largest = coins[-1] uses = target // largest total = 0 for i in range(uses + 1): total += ways_to_change(target - largest * i, coins[:-1]) return total def main(): print(ways_to_change(200, [1, 2, 5, 10, 20, 50, 100, 200])) if __name__ == "__main__": main() $ time python3 currency.py
real   0m0.049s
user   0m0.049s
sys    0m0.000s

## Ruby

#!/usr/bin/env ruby
count = 0
200.step(0, -200) do |a|
a.step(0, -100) do |b|
b.step(0, -50) do |c|
c.step(0, -20) do |d|
d.step(0, -10) do |e|
e.step(0, -5) do |f|
f.step(0, -2) do
count += 1
end
end
end
end
end
end
end
puts count
\$ time ruby currency.rb
real   0m0.043s
user   0m0.043s
sys    0m0.000s