current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|improve this question
    
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. –  Flambino Apr 15 at 1:09
1  
@Fiambino, have you ever wondered why you have so little money in your pockets at the end of the day? –  Cary Swoveland Apr 15 at 3:15
1  
@CarySwoveland Trickle-down economics. Coins are just pouring out of my pockets, and trickling down from my mansion on the hill. –  Flambino Apr 15 at 10:07
    
See also codereview.stackexchange.com/questions/69012/… –  knut Apr 16 at 19:53

3 Answers 3

up vote 5 down vote accepted

I don't see why you need to calculate permutations. Simply calculate the quotient and remainder of the division starting from the highest coins. Im 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 (I'll use a hash as state variable, use a 2-item array if you wish):

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
share|improve this answer
1  
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. –  Flambino Apr 15 at 9:58
    
Flambino, I had divmod but I wanted to save one line. But yes, it should be used. –  tokland Apr 15 at 18:05
    
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. –  Flambino Apr 15 at 20:17
1  
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. –  tokland Apr 15 at 20:22
1  
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). –  Flambino Apr 15 at 20:30
up vote 2 down vote

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)

share|improve this answer
up vote 2 down vote

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.

Or, in your context:

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?

share|improve this answer
    
I don't think it's a trick question, it seems obvious to me that you should get the exact value. –  tokland Apr 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? ;) –  Flambino Apr 15 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.