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?

Haskell

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