In my attempt to learn Ruby out in the open, here’s my solution for Project Euler Problem 31.
I like this question as it puts an interesting twist on the “how many ways can you make change for a dollar” question of which I was already familiar and I solved years ago. I haven’t turned to recursion in many (if any) of the Ruby solutions thus far. After spending a good amount of time with F# and Scala this year, this is welcome change because I regret to say that I still have troubles working with recursive functions at times. But enough about my shortcomings…
Below I have offered two solutions to the problem. The first isn’t scalable though it nicely demonstrates the overall approach and it does include multiple recursive methods. The latter solution is a refactoring of the former and though it might not be as easy to interpret I believe it is a more appropriate implementation.
As always, any feedback is welcome.
# Euler 31
# http://projecteuler.net/index.php?section=problems&id=31
# In England the currency is made up of pound, £, 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:
# 1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p
#
# How many different ways can £2 be made using any number of coins?
timer_start = Time.now
def pence(i)
1
end
def two_pence(i)
i >= 0 ? two_pence(i-2) + pence(i) : 0
end
def five_pence(i)
i >= 0 ? five_pence(i-5) + two_pence(i) : 0
end
def ten_pence(i)
i >= 0 ? ten_pence(i-10) + five_pence(i) : 0
end
def twenty_pence(i)
i >= 0 ? twenty_pence(i-20) + ten_pence(i) : 0
end
def fifty_pence(i)
i >= 0 ? fifty_pence(i-50) + twenty_pence(i) : 0
end
def pound(i)
i >= 0 ? pound(i-100) + fifty_pence(i) : 0
end
def two_pound(i)
i >= 0 ? two_pound(i-200) + pound(i) : 0
end
puts two_pound(200)
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
# Refactored solution
timer_start = Time.now
$coin_values = [1, 2, 5, 10, 20, 50, 100, 200]
def change_count(change, coin_values_index)
return 1 if coin_values_index == 0
return 0 if change < 0
change_count(change - $coin_values[coin_values_index], \
coin_values_index) + change_count(change, coin_values_index - 1)
end
puts change_count(200, 7)
puts "Elapsed Time: #{(Time.now - timer_start)*1000} milliseconds"
For the record, the latter implementation takes roughly 50% longer to execute. It’s a difference of 10 and 15 milliseconds.
I also went recursive with this one. My stop condition is a bit different from yours, because I was trying to allow for cases where correct change was impossible. (E.g., you only have nickels and dimes and you want to make 24 cents in change.)
#!/usr/bin/ruby class CoinCounter def initialize(coins) @coins = coins.sort end private def count_combos(amount, pos) return (amount % @coins[pos] == 0 ? 1 : 0) if (pos == 0) (0..amount/@coins[pos].floor).inject(0) { |sum, count| sum + count_combos(amount - count * @coins[pos], pos-1) } end public def coin_combinations(amount) count_combos(amount, @coins.length-1) end end cc = CoinCounter.new([1,2,5,10,20,50,100,200]) puts cc.coin_combinations(200)