21

I am trying to program the coin change problem in Scala using recursion. The code that i have written is as follows.

def countChange(money: Int, coins: List[Int]): Int = {
  def ways(change: List[Int], size: Int, capacity: Int): Int = {
    if(capacity == 0) 1
    if((capacity < 0) || (size <= 0)) 0

    //println and readLine to check and control each recursive call.

    println("calling ways(",change, change.length-1, capacity,") + ways(",change,   change.length, capacity - change(change.length - 1),")")
    readLine()
    //

    ways(change, change.length-1, capacity) + ways(change, change.length, capacity - change(change.length - 1))
  }
  ways(coins, coins.length, money)
}

On running the code, it does not terminate and keeps on calling the first recursive call. Where am I going wrong?

Improve this question
1

9 Answers 9

Reset to default
106

Nice and simple

def countChange(money: Int, coins: List[Int]): Int = {
  if(money == 0)
    1
  else if(money > 0 && !coins.isEmpty)
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  else
    0
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Could you provide some intuition behind this solution?
The idea here is to use up our coins and subtract it from the current amount of money. Eventually, the amount of money will be either 0, some negative number (meaning this combination of coins failed), or some positive number (meaning that we can still subtract more with the coins we currently have). countChange(money - coins.head, coins) will exhaust all combinations subtracting the first coin from the money, while countChange(money, coins.tail) exhausts all combinations using all other coins only. They are added together, since + is synonymous with the logical OR operator.
The solution is nice. One question about the base case: what if the initial money is 0. Isn't there 0 way to make changes for 0 money?
Imagine that you are given some coins in front of you and you are asked to match that using a huge bag of coins. If you had a penny in front of you, there is only 1 way to match that; by using a penny from your bag. Next, what if you had no coins in front of you? Again there is only 1 way to represent that; by not taking out any coins in your bag. Now finally, what if you had negative money? Well, you can't really represent that physically. So there are 0 ways to produce this output; the bag of coins is completely irrelevant in this scenario.
@rileyss you can represent 0 money by showing 0 coins. Remember, the question is "how many ways can we represent money given a certain denomination of coins". So using zero of the coins is still considered one distinct way.
20

Here is my implementation: I have tested it and it works fine

def countChange(money: Int, coins: List[Int]): Int = {

  def count(capacity: Int, changes: List[Int]): Int = {
    if (capacity == 0)
      1
    else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else
      count(capacity, changes.tail) 
        + count(capacity - changes.head, changes)
  }

  count(money, coins.sortWith(_.compareTo(_) < 0))
}
Improve this answer

4 Comments

Nice! Although, I think changing names (money -> capacity, coins -> changes) makes it harder to understand.
is the sorting really needed?
I have a question am new to scala : how does the compiler reads this line : count(capacity, changes.tail) + count(capacity - changes.head, changes) ? I know how the recursion works but am having problem understanding how the compiler executes the last line
@moe you may choose to watch week 1 lecture of this course by Martin Odersky class.coursera.org/progfun-004/lecture/4
12

Just another solution

def countChange(amount: Int, coins: List[Int]): Int = coins match {
  case _ if amount == 0 => 1
  case h :: t if amount > 0 => countChange(amount - h, h :: t) + countChange(amount, t)
  case _ => 0
}
Improve this answer

Comments

8

Simply stating a value does not make Scala return it; you either need an explicit return, or it has to be the last item stated. Thus:

if (capacity == 0) return 1

or

if (capacity == 0) 1
else if (...)
else { ... }
Improve this answer

2 Comments

are you sure it works? i'm still having the same problem as stated earlier
@user1050258 - Well, that wasn't the only problem--you also use change.length-1 instead of size-1 in various places. You don't update change itself in your solution! (Hint: if you did update change, then you would have avoided this bug and wouldn't need the size argument....)
3

Hey I just thought it would be better to see not only the amount but also the list of them, so put on top of the above example like :

def moneyChanges(money: Int, coins: List[Int]) : Option[List[Seq[Int]]]= {
  var listOfChange=List[Seq[Int]]()
  def changeMoney(capacity: Int, changes: List[Int], listOfCoins: Option[Seq[Int]]): Int = {
    if (capacity == 0) {
      listOfChange = listOfCoins.get :: listOfChange
      1
    } else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else {
      changeMoney(capacity, changes.tail, listOfCoins) +
      changeMoney(capacity - changes.head, changes, 
      Some(changes.head +: listOfCoins.getOrElse(Seq())))
    }
  }

  changeMoney(money, coins.sortWith(_.compareTo(_) < 0), None)
  Some(listOfChange)
}
Improve this answer

Comments

1

Here is my code: It's not optimized but works on all test cases.

The idea is to subtract first coin of list from from money until it becomes 0. Once it becomes 0, it will return 1 which means one solution is possible. To add all solutions coming from different recursion I used foldLeft.

(iterating list using foldLeft, so first goes in 1, then again goes in recursion and iterate for (1, 2) list)

                    [4, (1, 2)].  
             /(1 as cn)       \ (2 as cn)
            [3, (1, 2)].                 [2, (2)]
         /(-1)       \(-2)                \
      [2, (1, 2)].     [1, (2)].          [0, (2)]   
       /.(-1)    \(-2) 
     [1, (1, 2)].   [0, (2)]
      /. (-1)  \(-2)
    [0, (1, 2)].  [-1, (2)]

def countChange(money: Int, coins: List[Int]): Int = coins.foldLeft(0)((accum, cn) =>
  (money, cn) match {
    case (money, _) if money < 0 => 0
    case (0, _) => 1
    case (curr_money, curr_coin) =>
      val (before_curr_coin, after_curr_coin) = coins.span(_ != curr_coin)
      accum + countChange(curr_money - curr_coin, after_curr_coin)
  })
Improve this answer

Comments

0

here is a DP approach to reduce a lot of re-calculation in recursive approach

object DP {
  implicit val possibleCoins = List(1, 5, 10, 25, 100)
  import collection.mutable.Map

  def countChange(amount: Int)(implicit possibleCoins: List[Int]) = {
    val min = Map((1 to amount).map (_->Int.MaxValue): _*)
    min(0) = 0
    for {
      i <- 1 to amount
      coin <- possibleCoins
      if coin <= i && min(i - coin) + 1 < min(i)
    } min(i) = min(i-coin) + 1
    min(amount)
  }

  def main(args: Array[String]) = println(countChange(97))
}

see DP from novice to advanced for algorithm

Improve this answer

Comments

0

Below code is similar to one of the above example except I am using match case instead of if else 

def countChange(money: Int, coins: List[Int]): Int = {
    def change(m: Int, coinList: List[Int], count: Int): Int =
      m match {
        case _ if m < 0 => count
        case _ if coinList.isEmpty => {
          m match {
            case 0 => count + 1
            case _ => count
          }
        }
        case _ => change(m, coinList.tail, count) + change(m - coinList.head, coinList, count)
      }
    change(money, coins, 0)
  }
Improve this answer

Comments

0

This will handle the case where money is zero but not negative coins...

def countChange(money: Int, coins: List[Int]): Int = {

    def loop(money: Int, coins: List[Int]): Int = {
      if(money == 0) {
        1
      } else if(money > 0 && !coins.isEmpty) {
        loop(money - coins.head, coins) + loop(money, coins.tail)
      } else {
        0
      }
    }

    if(money == 0) {
      0
    } else {
      loop(money: Int, coins: List[Int])
    }

}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.