CODEWITHSUNDEEP
scalascala-2.9
Muavia
Muavia

Reputation: 408

coin change algorithm in scala using recursion

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?

Upvotes: 21

Views: 40508

Answers (9)

nidal
nidal

Reputation: 470

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])
    }

}

Upvotes: 0

pg20
pg20

Reputation: 339

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)
  })

Upvotes: 1

mysteriousscent
mysteriousscent

Reputation: 209

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))
}

Upvotes: 20

Suat Karakuşoğlu
Suat Karakuşoğlu

Reputation: 642

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)
}

Upvotes: 3

Carlos Caldas
Carlos Caldas

Reputation: 816

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
}

Upvotes: 12

Prasad
Prasad

Reputation: 636

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)
  }

Upvotes: 0

Leonmax
Leonmax

Reputation: 131

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

Upvotes: 0

rkenmi
rkenmi

Reputation: 1173

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
}

Upvotes: 106

Rex Kerr
Rex Kerr

Reputation: 167871

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 { ... }

Upvotes: 8

Related Questions