# Minimum coins algorithm in Ruby

I am working on a puzzle to find the minimum number of coins needed to buy a product.

I am given three coins:

• 1
• 3
• 5

and also a number representing the price of a product:

• 11

The answer here would be three, since it takes at least three coins to reach this number.

5, 5, 1


I decided it was best to use Ruby's repeated_permutation method. I tested my method in irb and it seems to work for smaller inputs, but when I submitted it to the online grader, I got a Memory Allocation Error.

File.open(ARGV[0]).each_line do |line|
number = line.to_i
coins = [1,3,5]
coin_combos = []
i = 1
until coin_combos.flatten(1).any? { |c| c.inject(:+) >= number }
coin_combos << coins.repeated_permutation(i).to_a
i += 1
end
puts i - 1
end


Here was my thought process:

1. Store the different types of coins in a coins array
2. Initialize an empty array for storing sequences of coins
3. Use a loop. It will be finished once the sum of one of the sequences is equal to or surpasses the product's price.
4. Push to my array the number of repeated permutations of length equal to my counter
5. Increment my counter and test for the condition again

This seems to be a problem with my algorithm and I'm using up too much space here.

Is there a different algorithm I should use?

• Since you only seem to need the number of coins used, and not the values of the coins used, I suppose you can just overpay? Because then you can just use the largest coin and nothing else. In which case the answer will always be number.fdiv(coins.max).ceil, as far as I can tell. Apr 15 '15 at 1:09
• @Fiambino, have you ever wondered why you have so little money in your pockets at the end of the day? Apr 15 '15 at 3:15
• @CarySwoveland Trickle-down economics. Coins are just pouring out of my pockets, and trickling down from my mansion on the hill. Apr 15 '15 at 10:07
• – knut
Apr 16 '15 at 19:53

I don't see why you need to calculate permutations. Simply calculate the quotient and remainder of the division starting from the highest coins. In imperative style:

def get_num_coins(coins, value)
ncoins = 0
coins.sort.reverse.each do |coin|
ncoins +=  value / coin
value = value % coin
end
ncoins
end


In functional style:

def get_num_coins(coins, value)
coins.sort.reverse.reduce(value: value, ncoins: 0) do |state, coin|
q, r = state[:value].divmod(coin)
{value: r, ncoins: state[:ncoins] + q}
end.fetch(:ncoins)
end

• This might be a good use-case for #divmod. By the way, there's an assumption about value and coin being integers when you do the division. A pretty safe assumption no doubt, but maybe worth mentioning. Apr 15 '15 at 9:58
• Well, the code was/is perfectly nice either way, really. By the way, I know the coins are a given, but just to play Devil's advocate: What if the price is 11 but the coins are 2, 3, and 5? You'd end up paying 2x 5 but leave an unpaid remainder of 1. (This situation, by the way, how I came upon my cheating solution of just overpaying.) Again, the coin values are given, so it's a moot point, but still. Apr 15 '15 at 20:17
• In that case you'd call the method run :p. No problem: add a final expression where you check whether state[:value] is 0 or not. Apr 15 '15 at 20:22
• Heh, now who's cheating? :) And yes, you check for a remainder, and if any, add a coin to the count. It was just to say that that's where I sort of realized that the coin values don't necessarily mean much, since you just add "a coin" - any coin - to pay the remainder (presuming of course that there isn't a requirement like "return zero if the price can't be paid exactly" or something). Apr 15 '15 at 20:30

I wrote this as a comment, but I'd just like to expand on it a bit:

Since you only seem to need the number of coins used, and not the values of the coins used, I suppose you can just overpay? Because then you can just use the largest coin and nothing else. In which case the answer will always be number.fdiv(coins.max).ceil, as far as I can tell.

File.open(ARGV[0]).each_line do |line|
puts line.to_i.fdiv(5).ceil
end


Basically, you're often paying too much, but the only thing that's being checked seems to be the number of coins. So who cares?

If the price is $11 (just using the dollar sign for clarity), then yes, the smart way to pay that would with$5 + $5 +$1 (or maybe $5 +$3 + $3). But that's 3 coins, and so is$5 + $5 +$5.

What if the price is just $1? Well, you could pay$1, and use 1 coin. Or you could overpay with a \$5 coin... and it'd still be 1 coin.

So... is this a trick question?

• I don't think it's a trick question, it seems obvious to me that you should get the exact value. Apr 15 '15 at 8:31
• @tokland Oh, I know I'm cheating. But still... using only the highest denomination coin should fit the spec as given. I was actually writing the same as your answer to begin with, but where's the fun in going by the book? ;) Apr 15 '15 at 9:55

Note that with problems like this, you can always prove that there is a small value that is dependent on the smaller coins only. For example, in your case, with the coins 1,3,5, you can get the following combinations:

1 -> 1
2 -> 1,1
3 -> 3
4 -> 1,3
5 -> 5
6 -> 5,1
7 -> 5,1,1
8 -> 5,3
9 -> 3,3,3
10 -> 5,5
11 -> 5,5,1
12 -> 5,5,1,1
13 -> 5,5,3
14 -> 5,3,3,3
15 -> 5,5,5


Note how, from point 10 onwards, all we did was add a 5?

So, the proof, for your situation, is that you can divide the total by 5 until your value is less than 10.... and then choose one of your canned solutions.... using some... as a consequence, you only need to solve the puzzle for the value less than 10, adter you have removed the 5-coins needed after that. In psuedocode:

solvefor = X
fivecount = 0;
if (solvefor > 10) {
fivecount = (solvefor - 10) / 5;
solvefor = solvefor - fivecount * 5;
}

solve for solvefor (which will be less than 10).


Putting this to some code:

coins = [5,3,1]
maxcoin = coins.first
# initialize the memoization array with 0 coins for 0 dollars
base = [0]
diff = 0

# Use the test that the last maxcoin tests have 1
# more coin than the previous maxcoin tests.
until diff == maxcoin
number = base.length
min = 1000000
found = false
for c in coins
num = number - c
if num < 0
next
end
dist = 1 + base[num]
if !found || dist < min
found = true
min = dist
end
end
base << min

if number >= 2 * maxcoin
sumhi = base[-maxcoin, maxcoin].reduce(:+)
sumlo = base[-maxcoin - maxcoin, maxcoin].reduce(:+)
diff = sumhi - sumlo
end
end

#File.open(ARGV[0]).each_line do |line|
for number in 10000 .. 10009
#number = line.to_i
init = 0;
if number >= base.length
init = 1 + (number - base.length) / maxcoin
end
coins = init + base[number - init * maxcoin]
puts "#{number} -> #{coins}"
end


(also in ideone)