The basic idea of the Coin Change Kata is that you are given a list of coin denominations and an amount of money, and you need to find the way to achieve that amount of money in the smallest amount of coins. For example, if you want to make 18 cents out of standard U.S. coin denominations, the best way would be one dime, one nickel, and three pennies. The official description of the kata gives some latitude about how to express the output of your function. I think a dictionary (aka hash table) is a perfectly sensible way to do it.
So, in Racket terminology, we're looking for a function that behaves like this:
(make-change '(1 5 10 25) 18) produces #hash((1 . 3) (5 . 1) (10 . 1))
Most beginners, when faced with this problem, immediately reason about the problem using the most obvious example they are familiar with: U.S. coin denominations. In our experience counting out money, we know that the best strategy is to first use as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and finally, finish off with pennies.
So the strategy seems straightforward. Sort the denominations in descending order, then work your way down the list, using as many as possible of the big coin denominations first. Many of the solutions that others have provided for this kata employ this strategy, known as the "greedy strategy". Those solutions are wrong.
To see this, consider (make-change '(1 20 25) 80). If you start by counting out quarters, you'll get to 75 cents, and then you make up the difference with pennies, for a total of 8 coins. Clearly, you're better off just using four 20 cent coins. So a more thorough search algorithm is required.
There's one other confounding factor that is often overlooked by beginners -- what if the problem is impossible? For example, what should (make-change '(2 10) 13) return? With that in mind, let's refine our contract for make-change and say that it either returns a dictionary of how to make change, or it returns false if the problem is impossible.
Before we get into the meat of the problem, there are a couple helper functions that we're going to want to have. First, it seems clear that a big part of what we'll be doing is comparing solutions to see which one uses the fewest coins. So we need a way to count the coins in a "change dictionary".
;; count-coins: dict -> nat
;; counts how many coins are in the change dictionary
(define (count-coins change)
(apply + (dict-values change)))
It would also be helpful to have a way to increment the coin count of a single denomination in a change dictionary. For example,
(change-increment #hash((10 . 1) (25 . 2)) 25) gives #hash((10 . 1) (25 . 3))
This is also straightforward:
;; change-increment: dict nat -> dict
;; Takes a change dictionary and a coin, returns the
;; change dictionary with that coin's count incremented
(define (change-increment change coin)
(dict-update change coin add1 0))Now we're ready to dive in. I am aware of two basic recursive strategies for tackling this problem.
Strategy 1: Include the first coin denomination, or not
To illustrate this idea, let's go back to U.S. denominations. If I want to find the best way to make 15 cents with the denominations '(1 5 10 25), I have two scenarios to consider.The first scenario is to include the first denomination, i.e., find the best way to make 14 cents with '(1 5 10 25) and then increment the penny count of that solution by 1. The best way to make 14 cents with '(1 5 10 25) is #hash((1 . 4) (10 . 1)). Increment the penny count, and you get #hash((1 . 5) (10 . 1)). So this is one of our candidate solutions.
The second scenario is that I ignore the penny completely and find the best way to make 15 cents out of '(5 10 25). The best way to do this is #hash((5 . 1) (10 . 1)).
In this example, the second scenario yields the superior solution, so that's the answer.
An outline of this algorithm would look like this:
(define (make-change denominations amount)
(cond
;; Insert base cases here
[else
;; Case 1: Use the first denomination
(define option1 (change-increment
(make-change denominations
(- amount (first denominations)))
(first denominations)))
;; Case 2: Or not
(define option2 (make-change (rest denominations) amount))
;; Which is best?
(argmin count-coins (list option1 option2))]))It's not entirely obvious what the base cases are, but if you have experience with recursive algorithms, you can see that this algorithm either reduces the length of the denomination list, or reduces the target amount of money with each step. So there are really two separate base cases to consider: either the denomination list gets to empty or the amount reaches zero (or maybe even becomes negative!).
Filling in the base cases looks like this:
(define (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)))
(define option2 (make-change (rest denominations) amount))
(argmin count-coins (list option1 option2))]))
Uh oh. There's a problem here. make-change can potentially return false, and the helper functions we created (i.e., change-increment and count-coins) don't handle false values. There are several possible ways to tackle this, but I think the simplest way is to just modify the helper functions to handle the false value gracefully.
change-increment is easy to modify -- false in should mean false out.
;; change-increment: dict-or-false nat -> dict-or-false
(define (change-increment change coin)
(if change
(dict-update change coin add1 0)
false))
It's a little less obvious how to modify count-coins. However, we're using count-coins within an argmin in order to find the solution with the fewest coins. To make this work, we just need to ensure that when count-coins is passed a false value, the output is something that can never be a "minimum". A standard trick to accomplish this is to set the output to "infinity".
;; count-coins: dict-or-false -> nat-or-infinity
(define (count-coins change)
(if change
(apply + (dict-values change))
+inf.0))
Now, we have a working make-change function that passes all test cases. Unfortunately, as you test the make-change function with larger and larger amounts, it gets really, really sloooooow. Functional programmers know that there's a simple trick to get around this -- memoization. A quick and easy way to add memoization is to add the line:
(require (planet dherman/memoize:3:1))
to the top of your file and change define to define/memo in the definition of make-change.
[The first time you include the memoization library, Racket will churn for several minutes and print out hundreds of error messages as it downloads and compiles the library locally on your machine. After that, the library will be available on your system, and future inclusions will be speedy.]
The final Racket version of Strategy 1:
#lang racket
(require rackunit)
(require (planet dherman/memoize:3:1))
;; count-coins: dict-or-false -> nat-or-infinity
;; counts how many coins are in the change dictionary
;; or returns infinity if input is false
(define (count-coins change)
(if change
(apply + (dict-values change))
+inf.0))
;; change-increment: dict-or-false nat -> dict-or-false
;; Takes a change dictionary and a coin, returns the
;; change dictionary with that coin's count incremented
;; or false if change input is false
(define (change-increment change coin)
(if change
(dict-update change coin add1 0)
false))
;; make-change: list-of-nats nat -> dict-or-false
;; Takes a list of coin denominations and an amount that
;; needs to be broken up into change. Returns a
;; "change dictionary", i.e., a hash table that maps
;; coin denominations to counts, corresponding to the
;; most efficient way that sums to the desired amount.
;; Returns false if impossible.
(define/memo (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)))
(define option2 (make-change (rest denominations) amount))
(argmin count-coins (list option1 option2))]))
(check-equal? (make-change '(1 5 10 25) 18)
#hash((1 . 3) (5 . 1) (10 . 1)))
(check-equal? (make-change '(1 20 25) 80)
#hash((20 . 4)))
(check-equal? (make-change '(1 24 25) 98)
#hash((24 . 2) (25 . 2)))
(check-equal? (make-change '(2 10) 13) false)
Strategy 2: Which coin to use next?
Going back to our example of finding the best way to make 15 cents out of '(1 5 10 25), there's a completely different strategy we could take. The first coin I use could either be a penny, nickel, dime, or quarter. So if I knew the best way to make 14 cents, 10 cents, 5 cents, and -10 cents out of '(1 5 10 25) [note that these values are 15-1, 15-5, 15-10, and 15-25, respectively], then I take the best of those ways, and increment the count of the corresponding coin to get the best way to make 15 cents.Using the same helper functions as Strategy 1, here is the final Racket implementation of make-change, Strategy 2:
(define/memo (make-change denominations amount)
(cond
[(negative? amount) false]
[(zero? amount) #hash()]
[(empty? denominations) false]
[else
(define options (for/list ([coin (in-list denominations)])
(change-increment
(make-change denominations (- amount coin))
coin)))
(argmin count-coins options)]))
In my benchmarking, the Racket version of Strategy 1 performed 10x better than the Racket version of Strategy 2 for large target amounts.
Clojure versions
Now, let's take a look at the Clojure versions of the same code. We'll begin with Strategy 1. In Clojure, hash maps are written using curly braces and we can insert commas anywhere we like to increase readability, so the change dictionaries look like {1 3, 5 1, 10 1}. Keeping with Clojure's conventions, the input list of denominations is now a vector rather than a list. Also, in Clojure we use nil as the output when there is no solution, rather than false. Overall, the code is almost the same (although this is not quite the final version):(use 'clojure.test)
(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
(defn make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)),
option2 (make-change (rest denominations) amount)]
(min-key count-coins option1 option2))))
(def make-change (memoize make-change))
(deftest make-change-tests
(are [x y] (= x y)
(make-change [1 5 10 25] 18) {1 3, 5 1, 10 1}
(make-change [1 20 25] 80) {20 4}
(make-change [1 24 25] 98) {24 2, 25 2}
(make-change [2 10] 13) nil))
Let's enumerate some of the differences:
- count-coins is essentially the same -- infinity has a longer name.
- Clojure does not have a built-in update function for hash-maps, so we have to roll our own. Frankly, I find this to be one of the most glaring omissions in Clojure's core library. Given the richness of Clojure's core, I find it baffling that Clojure is up to version 1.5, and this function still has not been added.
- In change-increment, we can leverage the fact that Clojure's when returns nil when the condition is false/nil, thus saving a line relative to Racket. This is a common idiom in Clojure for writing "nil in means nil out" functions.
- No internal define in Clojure, so instead in the else clause, we use let (which is similar to Racket's let*).
- In Racket, argmin takes a function and a list. In Clojure, the corresponding function is min-key which takes a function and a variable number of arguments.
- memoize is built-in to Clojure. The above technique of defining the function normally and then rebinding the function name to the memoized version is a common idiom, somewhat different than Racket's define/memo.
Racket uses a very clever technique to simulate an unlimited stack (or more to the point, limited only to the overall memory you've allocated to Racket, rather than some arbitrary stack limit). My understanding is that Racket achieves this trick by catching the error thrown when the stack overflows, moving the stack to the heap, and continuing. Even if those details aren't quite right, the main point here is that in Racket, you just don't spend any time worrying about stack overflows. In Clojure, it's a very salient issue that you absolutely must contend with.
So how to deal with it? One option is to switch the code over to memoization's bottom-up cousin, dynamic programming. The idea is that you allocate an array large enough to store the computations of make-change for all possible values up to amount, and fill up this array in sequence using the values that have been computed before. This will solve our stack overflow problem, but requires writing the code in a very different style. It would be nice if we could solve the problem without changing much of our existing code.
Any other options? How about we do a CPS transform on the entire program so that it doesn't consume any stack space, only heap? Blech.
Fortunately, there is a quick trick that I like to call "priming the pump". We just call the memoized function on all numbers up to the target amount, achieving a similar bottom-up effect as the dynamic programming approach in a way that allows us to build off our existing code. For clarity, I've left the original function alone, and created a new prime-the-pump version called make-change-fast. This new function, make-change-fast, is the one we would expose publicly; the original make-change function would become private.
Final Clojure version of Strategy 1:
;;Basic helper functions remain unchanged
(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
;; This is now the private helper function, don't use this directly
(defn ^:dynamic make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [option1 (change-increment
(make-change denominations (- amount (first denominations)))
(first denominations)),
option2 (make-change (rest denominations) amount)]
(min-key count-coins option1 option2))))
;; This is the new public function we use to make change.
(defn make-change-fast [denominations amount]
(binding [make-change (memoize make-change)]
(last
(for [i (range (inc amount))]
(make-change denominations i)))))
Strategy 2:
No real surprises here, and only a few lines differ from Strategy 1, but for completeness, here is the final Clojure version of Strategy 2:(defn count-coins [change]
(if change
(apply + (vals change))
Double/POSITIVE_INFINITY))
(defn update [m k f default]
(assoc m k (f (get m k default))))
(defn change-increment [change coin]
(when change
(update change coin inc 0)))
(defn ^:dynamic make-change [denominations amount]
(cond
(neg? amount) nil
(zero? amount) {}
(empty? denominations) nil
:else
(let [options (for [coin denominations]
(change-increment
(make-change denominations (- amount coin))
coin))]
(apply min-key count-coins options))))
(defn make-change-fast [denominations amount]
(binding [make-change (memoize make-change)]
(last
(for [i (range (inc amount))]
(make-change denominations i)))))
Interestingly, in Clojure, Strategy 2 is twice as fast Strategy 1 for large target amounts (whereas in Racket, Strategy 1 was substantially faster).
Final Thoughts
On my computer, both Clojure versions were faster than all the Racket versions I came up with (both the ones I displayed above, and other ones I tried, for example, employing the priming-the-pump strategy on Racket even though it is not needed). Specifically, my slowest Clojure version was twice as fast as the fastest Racket version.I find Racket's #hash notation to be awkward to work with relative to Clojure's simple {} syntax for hash tables.
I wrote the Racket versions first, and they were error-free the first time. I wrote the Clojure versions second, and they took me longer to write, even though I spend more time programming Clojure than Racket, in part because there were two errors I needed to debug. First, I made a mistake when writing the update helper function (I initially tried to use Clojure's related update-in function, not realizing that it doesn't allow for a default value when the key is not found). Second, I always forget that min-key is a variable argument function, rather than a list function like in Racket -- to me it seems far more intuitive to have that kind of function behave on a list, since that is the most common use case. In both cases, Clojure's error messages were spectacularly unhelpful, which sadly, is par for the course in Clojure.
The other reason the Clojure code took longer to write is that I needed to figure out how I wanted to deal with the stack overflow, and that ate up some time. I can't stress enough how freeing it is to not have to worry about those sorts of issues on Racket.
Clojure gives you better control over memoization strategies and even more options are available in clojure.core.memoize. Racket doesn't even have a built-in memoization library, and the one on planet is weak relative to Clojure.
Usually, when comparing Clojure to Racket, I find that Clojure has the richer set of built-ins: more versatile data structures and functions that operate over them. For this particular example, however, most of the built-in functions I relied on had counterparts in both languages, so the code looks nearly identical between the two languages. Oddly enough, this time it was Clojure that was missing something I wanted, namely the hash-map update function.
Looking at this as a Clojure vs Racket battle, there's not a clear winner on this example since both allowed me to compactly express the approaches I had in mind and there were some advantages and disadvantages on both sides. I'd probably give Clojure the nod because Clojure gave me better speed and more control over the memoization caching behavior. (Yes, I realize that if I drop down to C, I'd get even better speed and control over caching strategies, but that's not my point. My point is that if you can get better speed and control for a similar level of effort, why not?) Nevertheless, with no stack overflows and better error messages, writing the code in Racket was a noticeably more pleasant experience.
For those who have not tried Code Katas, I encourage you to do so. Code Katas usually are simple enough that they exercise fundamental skills that every programmer should possess, but are just tricky enough that there are several viable solutions and it is therefore interesting to compare those solutions with one another and across languages.
For those who enjoyed this particular Kata, I would recommend reading Doctor Ecco's Cyberpuzzles by Dennis E. Sasha. The first chapter deals with a fascinating, related problem of trying to find the optimal denomination list of a given list that minimizes the average number of coins needed across a range of possible target amounts.
