CODEWITHSUNDEEP
algorithmscala
Bula
Bula

Reputation: 2792

Algorithm fails for coin change

I am trying to build my last piece of homework from the scala course from coursera however my algorithm seems to fail. I cannot understand however why it fails and why it returns 0.

NOTE I am not asking for a solution to this problem. I want an explanation regarding what is happening with the code and why it fails. 

def countChange(money: Int, coins: List[Int]): Int = {
    def cc(amount: Int, list: List[Int]): Int = {
      println(amount, list);
      if (amount == 0) 1
      if (amount < 0 || list.isEmpty) 0
      else cc(amount - list.head, list) + cc(amount, list.tail)
    }

    cc(money, coins)
}

The logic was that the number of ways that you can give change to a given amount is equal to the number of ways you can give change using the first type of coin + the number of ways that you can give change to the next type of coin. This resulted in a recursive function which counted all the ways. This was my logic and this was what I tried to build however this is what it returns:

   (10,List(2, 3, 5))
(8,List(2, 3, 5))
(6,List(2, 3, 5))
(4,List(2, 3, 5))
(2,List(2, 3, 5))
(0,List(2, 3, 5))
(-2,List(2, 3, 5))
(0,List(3, 5))
(-3,List(3, 5))
(0,List(5))
(-5,List(5))
(0,List())
(2,List(3, 5))
(-1,List(3, 5))
(2,List(5))
(-3,List(5))
(2,List())
(4,List(3, 5))
(1,List(3, 5))
(-2,List(3, 5))
(1,List(5))
(-4,List(5))
(1,List())
(4,List(5))
(-1,List(5))
(4,List())
(6,List(3, 5))
(3,List(3, 5))
(0,List(3, 5))
(-3,List(3, 5))
(0,List(5))
(-5,List(5))
(0,List())
(3,List(5))
(-2,List(5))
(3,List())
(6,List(5))
(1,List(5))
(-4,List(5))
(1,List())
(6,List())
(8,List(3, 5))
(5,List(3, 5))
(2,List(3, 5))
(-1,List(3, 5))
(2,List(5))
(-3,List(5))
(2,List())
(5,List(5))
(0,List(5))
(-5,List(5))
(0,List())
(5,List())
(8,List(5))
(3,List(5))
(-2,List(5))
(3,List())
(8,List())
(10,List(3, 5))
(7,List(3, 5))
(4,List(3, 5))
(1,List(3, 5))
(-2,List(3, 5))
(1,List(5))
(-4,List(5))
(1,List())
(4,List(5))
(-1,List(5))
(4,List())
(7,List(5))
(2,List(5))
(-3,List(5))
(2,List())
(7,List())
(10,List(5))
(5,List(5))
(0,List(5))
(-5,List(5))
(0,List())
(5,List())
(10,List())
0

As you can see it returns 0 even though the steps that it takes as it can be seen from the printed calls seem to be exactly what my logic tried to achieve.

This is the call of the function in the main function:

 println ("" + countChange(10,List(2,3,5)))

Please Do not give me baked code which I can copy and paste. I want to know what is wrong with my logic.

Upvotes: 3

Views: 220

Answers (2)

Rex Kerr
Rex Kerr

Reputation: 167871

You are missing an else:

  if (amount == 0) 1   // This value is thrown away
  if (amount < 0 || list.isEmpty) 0
  else cc(amount - list.head, list) + cc(amount, list.tail)

Just add it before the second if and you'll be okay.

(In case it isn't clear, only the result from the last if/else is returned, so in

if (a) 1
if (b) 2
if (c) 3
else 4

only the last two lines will matter. If you want to choose one of those options,

if (a) 1
else if (b) 2
else if (c) 3
else 4

is what you need.)

Upvotes: 3

wheaties
wheaties

Reputation: 35962

Your bug is in the recursive portion of the code:

 cc(amount -list.head, list) + cc(amount, list.tail)

If you look at the first part, you're passing the entire list again without removing the head. What that means is that the only way you'll ever get an answer is if the amount is exactly divisible by the coin at the head position of the current list.

Upvotes: 2

Related Questions