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