# Coin Kata

## Introduction

Many people have talked about the Coin Change Kata. The local PDX Clojerks had a swarm where you rewrote this same program repeatedly to make it better.

Martin Ordesky had the following Scala example of change counting in his online class, Functional Programming in Scala:

def countChange(money: Int, coins: List[Int]): Int = { if (money == 0) // Is this a special case? 0 else changeAcc(money, coins.reverse) } def changeAcc(money: Int, coins: List[Int]): Int = { val availableCoins = coins.filter(_ <= money) if (money == 0) 1 // Good path else if (money < 0) 0 else if (availableCoins.length == 0) 0 // Bad path else changeAcc(money - coins.head, coins) + changeAcc(money, coins.tail) }

Where you could call it with some of these test cases:

// example from instructions assert(countChange(4,List(1,2)) === 3) // sorted CHF assert(countChange(300,List(5,10,20,50,100,200,500)) === 1022) // no pennies assert(countChange(301,List(5,10,20,50,100,200,500)) === 0) // unsorted CHF assert(countChange(300,List(500,5,50,100,20,200,10)) === 1022) // no coins assert(countChange(300,List()) === 0) // no money assert(countChange(0,List(500,5,50,100,20,200,10)) === 0)

### Coin Kata Tests

While not always listed first, the tests were written first, and
are stored in a test source code file next to `coin-kata.clj`

.

Currently, they do not take advantage of any testing framework, and just make a bunch of assertions.

## Port of Scala Version

The main functional interface for this is the `count-change`

function which just calls an internal function, `change-acc`

, which
*follows two coin change algorithms*.

For instance, if we want change from 4¢, and we had only 1¢ and 2¢ coins, we could follow both paths shown in the following state diagram:

In Path 1, we lower the amount of money by the largest coin and try to find change from the remainder (with all available coins).

In Path 2, we try to find change from the same amount, but without the largest coin in the list.

### Count Change Function

The `count-change`

function has two parts, the first (at the end)
sorts the coins from largest to smallest, and calls the *inner
function*, `change-acc`

.

After covering the end cases, tHe inner function simply counts the possibilities based on each of the two paths, and returns the sum.

(defn count-change "Returns the number of ways to make change for an amount with a list of coins." [money coins] (letfn [(change-acc [money coins] (let [available-coins (filter (fn [c] (<= c money)) coins)] (cond (= money 0) 1 ;; Happy Ending! (< money 0) 0 (= (count available-coins) 0) 0 :else (+ (change-acc (- money (first coins)) coins) (change-acc money (rest coins))))))] (if (= money 0) 0 (change-acc money (reverse (sort coins))))))

Sanity case, taken from Ordesky’s lecture, if you have coins for a 1¢ and a 2¢ value, you could make change for 4¢ in 3 different ways:

- 1, 1, 1, 1
- 1, 1, 2
- 2, 2

(assert 3 (count-change 4 '(1 2)))

The base case, where we want change for nothing must be 0:

(assert 0 (count-change 0 '(1 5)))

The other base case is having an empty list of coins, which also much return 0:

(assert 0 (count-change 5 '()))

Here are the rest of the tests ported from the Scala work:

;; sorted CHF (assert 1022 (count-change 300 '(5,10,20,50,100,200,500))) ;; no pennies (assert 0 (count-change 301 '(5,10,20,50,100,200,500))) ;; unsorted CHF (assert 1022 (count-change 300 '(500,5,50,100,20,200,10)))

While this does count the *number of ways* to make change, it
doesn’t tell you what coins to use, and that is the focus of the
Kata.

## Initial Approach

Given a list of 1¢ and 2¢ coins, we expect to need both coins to make change for 3¢:

(assert '(2 1) (get-change 3 (list 1 2)))

Given the standard US coins, we expect 68¢ to need just about every coin as well:

(assert '(25 25 10 5 1 1 1) (get-change 68 '(1 5 10 25)))

This *naive approach* begins by sorting coins from highest to
lowest, and then we use the top coin, and make change with
the money left.

(defn get-change "Return a list of coins needed to make change for an amount with a list of coins." [money coins] (letfn [(get-change-acc [money coins] (let [available-coins (filter (fn [c] (<= c money)) coins)] (cond (= money 0) '() ;; Happy Ending! (= (count available-coins) 0) '() :else (let [biggest-coin (first available-coins)] (cons biggest-coin (get-change-acc (- money biggest-coin) available-coins))))))] (if (= money 0) '(0) (get-change-acc money (reverse (sort coins))))))

Why is this naive? Because it doesn’t produce the *least* amount of
coins. Granted, this works out for US coins, but what if we wanted
change for 80¢, but with had the following: 25¢, 20¢, and 1¢:

(get-change 80 '(1 20 25))

It thinks we need 8 coins, when we could have made change with 4 20¢ coins.

## Better Approach

The next idea is to simply run the `get-change`

function with
subset collections of the coin list to see which is the smallest
approach.

(defn get-better-change "Returns a smaller number of coins to make change" [money coins] (letfn [(get-all-change [money coins] (if (> (count coins) 0) (cons (get-change money coins) (get-all-change money (rest coins))))) (smallest-list [list-a list-b] (if (< (count list-a) (count list-b)) list-a list-b))] (reduce smallest-list (get-all-change money (reverse (sort coins))))))

This function now deals correctly with 80¢ change when our coins are 1¢, 20¢ and 25¢.

(assert '(20 20 20 20) (get-better-change 80 '(1 20 25)))

We should create a series of base-cases and sanity tests for our new function.

;; No money (assert '() (get-better-change 0 '(1 5 10 25))) ;; No coins (assert '() (get-better-change 100 '())) ;; No pennies (assert '() (get-better-change 4 '(10 5)))

## Technical Artifacts

This code (and the documentation) was created using org-mode and
its Babel project and can both *tangle* the source code out to
Clojure files as well as *weave* (generate) documents easier for
human eyes.

This section is only if you’ve loaded the `org`

file in your Emacs
session. To build the source on a new system, first place the cursor
over any of these properties, and hit: `C-c C-c`

Generate the *human documentation* by typing: `C-c C-e b`