-1

I'm working on the following algorithm and wanted to know if my implementation is correct:

Given an infinite number of quarters, dimes, nickels and pennies, write code to calculate the number of ways of representing n cents

This is without memoizing:

def count_ways(n)
  return 0 if n < 0 
  return 1 if n == 0 

  count_ways(n-25) + count_ways(n-5) + count_ways(n-10) + count_ways(n-1)
end
the Tin Man
  • 158,662
  • 42
  • 215
  • 303
segue_segway
  • 1,490
  • 1
  • 22
  • 40
  • 1
    Do you have test cases? For example, can you compute by hand the correct return value for count_ways(n) for small n (say n=1..10), and then see if your code returns what you expect? – Paul Hankin Mar 07 '17 at 19:36
  • Why the rush to select the first answer, particularly one which only provides pseudo-code, when you asked for a solution written in Ruby? Moreover, as I noted in a comment on the answer, it is incorrect. – Cary Swoveland Mar 07 '17 at 20:30
  • This really sounds like a homework question. http://meta.softwareengineering.stackexchange.com/questions/6166/open-letter-to-students-with-homework-problems is really good to read. Also read "[mcve]". Your question doesn't meet the criteria for a question about a problem with your code as we have to write a test harness for it to do anything. – the Tin Man Mar 07 '17 at 23:01

3 Answers3

6

No, you will be double-counting solutions, because you could first pick a quarter and then a dime or the other way around, but those solutions are essentially the same.

The easiest way to prevent double-counting is to make sure you never pick a coin that is bigger than the ones you already picked.

In code:

def count_ways(n, max_coin)
  return 0 if n < 0 
  return 1 if n == 0 

  result = count_ways(n-1, 1)
  result = result + count_ways(n- 5,  5) if max_coin >=  5
  result = result + count_ways(n-10, 10) if max_coin >= 10
  result = result + count_ways(n-25, 25) if max_coin >= 25
  result
end

And call it with 25 as initial max coin

Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
  • You have offered valid Ruby code, but `count_ways(10,2) #=> 9`, but should return `3` (1 dime, 1 nickel and 5 pennies, and 10 pennies). Even without running the Ruby code one can trace through to see that it returns `9`. Did you test this in any language? – Cary Swoveland Mar 07 '17 at 20:29
  • @CarySwoveland no, unfortunately I have no pseudo-code interpreter at hand. But you're right, I made a typo and wrote `<=` instead of `>=`, that's fixed now. I'm not sure why you think `count_ways(10, 2)` should return `3`, as it clearly should return `1` (and it does): the penny is the only coin with value `<= 2`, so 10 pennies is the only solution. – Vincent van der Weele Mar 08 '17 at 05:43
  • 1
    It looks good now, with one small change needed: you must add the line `result` before the last line (`end`). That's because in Ruby, `def doit; result = 1; result = result + 1 if false; end; doit #=> nil`. Disregard my earlier reference to `count_ways(10, 2)`. I was mixed up on the second argument. Note `count_ways(100,25).size #=> 242`, coinciding with my result. – Cary Swoveland Mar 08 '17 at 06:09
3

We can see if your code is correct quite easily. let's try making change for a dime. There are four ways: 1 dime, 2 nickels, 1 nickel and 5 pennies, and 10 pennies, yet count_ways(10) #=> 9.

You can do it as follows, using recursion.

Code

def count_ways(cents, coins)
  if coins.size == 1
    return (cents % coins.first) == 0 ? [cents/coins.first] : nil
  end 
  coin, *remaining_coins = coins
  (0..cents/coin).each_with_object([]) { |n, arr|
    count_ways(cents-n*coin, remaining_coins).each { |a| arr << [n, *a] } }
end

Examples

coins = [25, 10, 5, 1]

count_ways(32, coins)
  #=> [[0, 0, 0, 32], [0, 0, 1, 27], [0, 0, 2, 22], [0, 0, 3, 17], [0, 0, 4, 12],
  #    [0, 0, 5,  7], [0, 0, 6,  2], [0, 1, 0, 22], [0, 1, 1, 17], [0, 1, 2, 12],
  #    [0, 1, 3,  7], [0, 1, 4,  2], [0, 2, 0, 12], [0, 2, 1,  7], [0, 2, 2,  2],
  #    [0, 3, 0,  2], [1, 0, 0,  7], [1, 0, 1,  2]] 

count_ways(100, coins)
  #=> [[0, 0, 0, 100], [0, 0, 1, 95], [0, 0, 2, 90], [0, 0, 3, 85], [0, 0, 4, 80],
  #    [0, 0, 5,  75], [0, 0, 6, 70], [0, 0, 7, 65], [0, 0, 8, 60], [0, 0, 9, 55],
  #    ...
  #    [3, 1, 2,   5], [3, 1, 3,  0], [3, 2, 0,  5], [3, 2, 1,  0], [4, 0, 0,  0]] 
count_ways(100, coins).size
  #=> 242

Explanation

The best way to show how the recursion works is to salt the code with puts statements and then run it against a simple example.

INDENT = 8
@indentation = 0

def indent
 @indentation += INDENT
end

def undent
 @indentation = [@indentation-INDENT, 0].max
end

def ind
  ' '*@indentation
end


def count_ways(cents, coins)
  puts "#{ind}** entering count_ways with cents=#{cents}, coins=#{coins}"
  if coins.size == 1
    puts "#{ind}<< returning [cents]=#{[cents]} as coins.size == 1" 
    undent
  end  
  return [cents] if coins.size == 1
  coin, *remaining_coins = coins
  puts "#{ind}coin=#{coin}. remaining_coins=#{remaining_coins}"
  puts "#{ind}0..cents/coin=#{0..cents/coin}"
  arr = (0..cents/coin).each_with_object([]) do |n, arr|
    puts "#{ind}  n=#{n}, arr=#{arr}"
    puts "#{ind}  >> calling count_ways(#{cents}-#{n}*#{coin}, remaining_coins)"
    indent
    aa = count_ways(cents-n*coin, remaining_coins)
    puts "#{ind}  aa=#{aa}"
    aa.each do |a|
      arr << [n, *a]
      puts "#{ind}    arr << [#{n}, *#{a}], arr=#{arr}"
    end
    puts "#{ind}  after all coins, arr=#{arr}"
  end
  puts "#{ind}<< returning arr=#{arr}"
  undent
  arr
end

Now let's run count_ways(12, coins) which should return the four ways of making change for 12 cents: [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]].

count_ways(12, coins)
** entering count_ways with cents=12, coins=[25, 10, 5, 1]
coin=25. remaining_coins=[10, 5, 1]
0..cents/coin=0..0
  n=0, arr=[]
  >> calling count_ways(12-0*25, remaining_coins)
        ** entering count_ways with cents=12, coins=[10, 5, 1]
        coin=10. remaining_coins=[5, 1]
        0..cents/coin=0..1
          n=0, arr=[]
          >> calling count_ways(12-0*10, remaining_coins)
                ** entering count_ways with cents=12, coins=[5, 1]
                coin=5. remaining_coins=[1]
                0..cents/coin=0..2
                  n=0, arr=[]
                  >> calling count_ways(12-0*5, remaining_coins)
                        ** entering count_ways with cents=12, coins=[1]
                        << returning [cents]=[12] as coins.size == 1


                  aa=[12]
                    arr << [0, *12], arr=[[0, 12]]
                  after all coins, arr=[[0, 12]]
                  n=1, arr=[[0, 12]]
                  >> calling count_ways(12-1*5, remaining_coins)
                        ** entering count_ways with cents=7, coins=[1]
                        << returning [cents]=[7] as coins.size == 1
                  aa=[7]
                    arr << [1, *7], arr=[[0, 12], [1, 7]]
                  after all coins, arr=[[0, 12], [1, 7]]
                  n=2, arr=[[0, 12], [1, 7]]
                  >> calling count_ways(12-2*5, remaining_coins)
                        ** entering count_ways with cents=2, coins=[1]
                        << returning [cents]=[2] as coins.size == 1


                  aa=[2]
                    arr << [2, *2], arr=[[0, 12], [1, 7], [2, 2]]
                  after all coins, arr=[[0, 12], [1, 7], [2, 2]]
                << returning arr=[[0, 12], [1, 7], [2, 2]]
          aa=[[0, 12], [1, 7], [2, 2]]
            arr << [0, *[0, 12]], arr=[[0, 0, 12]]
            arr << [0, *[1, 7]], arr=[[0, 0, 12], [0, 1, 7]]
            arr << [0, *[2, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
          after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
          n=1, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]]
          >> calling count_ways(12-1*10, remaining_coins)
                ** entering count_ways with cents=2, coins=[5, 1]
                coin=5. remaining_coins=[1]
                0..cents/coin=0..0
                  n=0, arr=[]
                  >> calling count_ways(2-0*5, remaining_coins)
                        ** entering count_ways with cents=2, coins=[1]
                        << returning [cents]=[2] as coins.size == 1


                  aa=[2]
                    arr << [0, *2], arr=[[0, 2]]
                  after all coins, arr=[[0, 2]]
                << returning arr=[[0, 2]]
          aa=[[0, 2]]
            arr << [1, *[0, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
          after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
        << returning arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
  aa=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]]
    arr << [0, *[0, 0, 12]], arr=[[0, 0, 0, 12]]
    arr << [0, *[0, 1, 7]], arr=[[0, 0, 0, 12], [0, 0, 1, 7]]
    arr << [0, *[0, 2, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2]]
    arr << [0, *[1, 0, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
  after all coins, arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
<< returning arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
 => [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]]
Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
  • Although this code is correct, it seems quite far above the skill level of the OP. You could maybe add some explanation why this works. Besides, `return [cents] if coins.size == 1` implicitly assumes that the smallest coin has value 1, which reduces the usefulness of passing the coins array (I would expect `count_ways(2, [5])` to return 0, not 1). – Vincent van der Weele Mar 08 '17 at 06:04
  • Good points. I'll add an explanation tomorrow. `count_ways(x, [5])` would never be called, only `count_ways(x, [25,10,5,1])`, `count_ways(x, [10,5,1])`, `count_ways(x, [5,1])` and `count_ways(x, [1])`. – Cary Swoveland Mar 08 '17 at 06:19
  • 1
    @VincentvanderWeele & Sunny, I provided an explanation of the recursion. – Cary Swoveland Mar 09 '17 at 05:59
1

The order of the coins doesn't matter, so coins.min isn't going to help you in this case – it's over-complicating things.

First we must develop an intuition about the relationship between the kinds of coins and the amount of change to count

The number of ways to change amount a using n kinds of coins equals

  • the number of ways to change amount a using all but the first kind of coin, plus
  • the number of ways to change amount a − d using all n kinds of coins, where d is the denomination of the first kind of coin.

source: SICP Chapter 1.2

### change_coins :: (Int, [Int]) -> Int
def change_coins amount, (x,*xs)
  if amount == 0
    1
  elsif amount < 0 or x.nil?
    0
  else
    change_coins(amount, xs) + change_coins(amount - x, [x,*xs])
  end
end

change_coins 11, [1, 2, 5]           # => 11
change_coins 2, [3]                  # => 0
change_coins 100, [1, 5, 10, 25, 50] # => 292

Sensible return values

For example, in this problem we have to return -1 if the amount of money cannot be made up by any combination of the coins.

The -1 case is dumb. There are zero ways to change 2 cents using only a 3-cent coin; therefore we return 0.

If you really must return -1, just use a stupid wrapper

def cc amount, xs
  count = change_coins amount, xs
  if count == 0 then -1 else count end
end

Order doesn't matter

change_coins 11, [5, 1, 2]           # => 11
change_coins 2, [3]                  # => 0
change_coins 100, [50, 1, 25, 10, 5] # => 292
Community
  • 1
  • 1
Mulan
  • 129,518
  • 31
  • 228
  • 259