 # gstro's solution

## to Change in the Scala Track

Published at Oct 06 2019 · 0 comments
Instructions
Test suite
Solution

Correctly determine the fewest number of coins to be given to a customer such that the sum of the coins' value would equal the correct amount of change.

## For example

• An input of 15 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) or [5, 10]
• An input of 40 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) and one quarter (25) or [5, 10, 25]

## Edge cases

• Does your algorithm work for any given set of coins?
• Can you ask for negative change?
• Can you ask for a change value smaller than the smallest coin value?

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command `sbt test` in the exercise directory.

Please see the learning and installation pages if you need any help.

## Source

Software Craftsmanship - Coin Change Kata https://web.archive.org/web/20130115115225/http://craftsmanship.sv.cmu.edu:80/exercises/coin-change-kata

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### ChangeTest.scala

``````import org.scalatest.{Matchers, FunSuite}

/** @version 1.2.0 */
class ChangeTest extends FunSuite with Matchers {

test("single coin change") {
Change.findFewestCoins(25, List(1, 5, 10, 25, 100)) should be (Some(List(25)))
}

test("multiple coin change") {
pending
Change.findFewestCoins(15, List(1, 5, 10, 25, 100)) should be (Some(List(5, 10)))
}

test("change with Lilliputian Coins") {
pending
Change.findFewestCoins(23, List(1, 4, 15, 20, 50)) should be (Some(List(4, 4, 15)))
}

test("change with Lower Elbonia Coins") {
pending
Change.findFewestCoins(63, List(1, 5, 10, 21, 25)) should be (Some(List(21, 21, 21)))
}

test("large target values") {
pending
Change.findFewestCoins(999, List(1, 2, 5, 10, 20, 50, 100)) should be (Some(List(2, 2, 5, 20, 20, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100)))
}

test("possible change without unit coins available") {
pending
Change.findFewestCoins(21, List(2, 5, 10, 20, 50)) should be (Some(List(2, 2, 2, 5, 10)))
}

test("another possible change without unit coins available") {
pending
Change.findFewestCoins(27, List(4, 5)) should be (Some(List(4, 4, 4, 5, 5, 5)))
}

test("no coins make 0 change") {
pending
Change.findFewestCoins(0, List(1, 5, 10, 21, 25)) should be (Some(List()))
}

test("error testing for change smaller than the smallest of coins") {
pending
Change.findFewestCoins(3, List(5, 10)) should be (None)
}

test("error if no combination can add up to target") {
pending
Change.findFewestCoins(94, List(5, 10)) should be (None)
}

test("cannot find negative change values") {
pending
Change.findFewestCoins(-5, List(1, 2, 5)) should be (None)
}
}``````
``````import scala.annotation.tailrec

object Change {
import Tree._

private sealed trait CoinTree {
def path: List[Int] = Nil
def depth: Int = path.length
}
private object Tree {
case object Leaf extends CoinTree
case class Node(value: Int, siblings: List[Int], branch: CoinTree) extends CoinTree {
override def path: List[Int] = value :: branch.path
}
}

def findFewestCoins(change: Int, coins: List[Int]): Option[List[Int]] =
if (change == 0) Some(Nil)
else checkCoins(change, coins.reverse, Leaf) match {
case Leaf => None
case tree => Some(tree.path)
}

@tailrec
private def checkCoins(target: Int, coinsList: List[Int], minValid: CoinTree): CoinTree = coinsList match {
case _ :: tail => checkCoins(target, tail, iterate(target, coinsList, Leaf, minValid))
case Nil       => minValid
}

@tailrec
private def iterate(remaining: Int, currentCoins: List[Int], acc: CoinTree, minValid: CoinTree): CoinTree = currentCoins match {
case _ if remaining == 0       => List(acc, minValid).sortBy(_.depth).find(_.path.nonEmpty).getOrElse(Leaf)
case c :: cs if c <= remaining => iterate(remaining - c, currentCoins, Node(c, cs, acc), minValid)
case _ :: cs                   => iterate(remaining, cs, acc, minValid)
case _                         => prune(remaining, acc, minValid)
}

private def prune(remaining: Int, acc: CoinTree, minValid: CoinTree): CoinTree = acc match {
case a if a.depth < minValid.depth => minValid
case Leaf                          => minValid
case Node(v, sibs, branch)         => iterate(remaining + v, sibs, branch, minValid)
}
}``````