Struggling with recursive base case

Question

I've spent a while on the following algorithm:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Example 2: coins = [2], amount = 3 return -1.

Note: You may assume that you have an infinite number of each kind of coin.

This is likely not the most efficient way to solve the problem, but I figured I can solve it by trying every coin and launching a new function per attempt, where the new function call has the updated amount. This would launch N function calls per coin... but I'll deal with that later.

Right now I'm dealing with the following issue: often when making recursive calls, I'm unable to properly code in a base case. 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. However, I also need to count up the fewest number of coins. So I figured I'd take a min variable and call 1 + new_func_call.

However, when this new_func_call ends up not working out, it passes up a -1 to the recursive call stack, which ends up making min zero instead. I'm not sure how to adjust this-- I've tried varying my code in different ways but perhaps I'm having a conceptual issue. I know why it's happening-- just don't know how to deal with it.

Sample input:
Coins: [2]
Amount: 3

My output: 0
Correct output: -1 

Code:

def coin_change(coins, amount)
    coin_count(coins, amount, coins.min)
end

def coin_count(coins, amount, min_coin)
    with_coin = min = 1.0/0
    return 0 if amount == 0
    return -1 if amount < min_coin
    i = 0

    while i < coins.length
        with_coin = 1 + coin_count(coins, amount - coins[i], min) if amount - coins[i] >= 0
        min = [min, with_coin].min
        i += 1
    end

    min
end

Answer 1

Right now I'm dealing with the following issue: often when making recursive calls, I'm unable to properly code in a base case. 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. However, I also need to count up the fewest number of coins.

Well you sort of have two base cases here

1. If the amount state variable is zero, we are done counting, so return the count
2. If we run out of coins (xs) to count with and still didn't reach a zero-amount, then return -1

Otherwise we have the two recursion cases

1. oops: amount is less than 0 meaning the last coin (x) subtracted was too big – rewind and recurse without using this coin
2. default case: add 1 to count, subtract the coin (x) from amount, and recurse using the same set of coins (xs)

The only requirement for this to work is that the coins are first sorted in descending order

OK, so all of this is easily encoded in Ruby using an auxiliary helper (aux) to hold our state variables. Remember to initialize with a count of 0 and ensure that xs is sorted in descending order. - Note the sorting only happens once – not once per recursion

def fewest_coins amount, xs
  def aux count, amount, (x,*xs)
    if amount.zero?
      count
    elsif x.nil?
      -1
    elsif amount < 0
      aux (count - 1), (amount + x), xs
    else
      aux (count + 1), (amount - x), [x, *xs]
    end
  end
  aux 0, amount, xs.sort { |a,b| b <=> a }
end

fewest_coins 11, [1, 5, 2]         # => 3
fewest_coins 2, [3]                # => -1
fewest_coins 100, [1, 25, 10, 5]   # => 4

---

Check your understanding

As an exercise, modify fewest_coins to output an array of coins that makes up the answer

# for example
fewest_coins 199, [1, 5, 10, 25, 50]
# => [50, 50, 50, 25, 10, 10, 1, 1, 1, 1]

Answer 2

You could do that as follows.

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 

def fewest(cents, coins)
  count_ways(cents, coins)&.map(&:sum)&.min
end

fewest(11, [5,2,1])
  #=> 3
fewest(199, [25,10,5,1])
  #=> 13 (Let me guess: 7 quarters, 2 dimes, 4 pennies) 
fewest(2, [3]) 
  #=> nil

require 'time'

t = Time.now
fewest(2835, [25,10,5,1])
  #=> 114 
Time.now - t
  #=> 7.6961 (seconds)

I took count_ways from my answer here.

The two &'s followed by . are Ruby's safe navigation operator, which was introduced in Ruby v2.3.0. Array#sum (and Enumerable#sum) first appeared in Ruby v2.4.0.

Answer 3

This question already has a really good answer that shows you exactly how to solve your problem, but I wanted to point out what was actually happening with your algorithm, so you know why it wasn't working for you.

Your first problem is that

coin_count(coins, amount - coins[i], min)

should be

coin_count(coins, amount - coins[i], coins.min)

Instead of passing along the smallest coin, you were passing along your min value, which you had set to Infinity, which made this statement checking if the amount was smaller than the smallest coin:

return -1 if amount < min_coin

actually check if the amount was smaller than infinity, which meant your coin_count is always returning -1. Which leads to the second problem:

1 + coin_count(coins, amount - coins[i], min)
#1 + -1 = 0

The frustrating thing about using -1 as an error in recursive programming is that -1 is an otherwise valid number and frequently causes logic problems. I would avoid using it entirely, but if your prompt or spec forces you to return it, i'd use it only at the last second. try:

def coin_change(coins, amount)
    result = coin_count(coins, amount, coins.min)
    return -1 if result == 1/0.0
    return result
end

def coin_count(coins, amount, min_coin)
    with_coin = min = 1.0/0
    return 0 if amount == 0
    return 1/0.0 if amount < min_coin
    i = 0

    while i < coins.length
        with_coin = 1 + coin_count(coins, amount - coins[i], coins.min) if amount - coins[i] >= 0
        min = [min, with_coin].min
        i += 1
    end

    min
end

I changed your error number from -1 to infinity, which essentially makes your algorithm ignore invalid permutations since they're always sorted out by your .min(). the only way your function would return infinity in this case is if it were the smallest number returned, which only happens when there are no valid permutations. Then in fewest_coins I set it to check for infinity and return -1 instead.

Oh and by the way, there's a much easier way to loop through things in ruby:

coins.each do |coin|
  with_coin = 1 + coin_count(coins, amount - coin, coins.min) if amount - coin >= 0
  min = [min, with_coin].min
end

Answer 4

This definitely won’t be a smartest approach, it’s not the best performant one, and it might be time consuming for huge amounts, but it’s how I would do it in ruby:

def get coins, amount
  coins = coins.sort
  max = amount / coins.first + 1
  (1..max).detect do |i|
    result = coins.repeated_permutation(i).detect do |e|
      e.reduce(:+) == amount
    end
    break result if result
  end || -1
end

get [1, 2, 5], 11
#⇒ [1, 5, 5]

get [2], 3
#⇒ -1