Clojure programming exercise for calculating change

Question

I'm learning Clojure and have written a small function to calculate change. I don't like few things about the code and would primarily like to replace recursive call with something more idiomatic. Could you please comment on the code and suggest a better (more Clojure-like) way of implementing it?

(def in-bank #{1 2 5 10})
(defn smaller-than? [compare-input metric]
 (>= compare-input metric))
(defn get-max-smaller-than [input]
 (apply max (filter (partial smaller-than? input) in-bank)))
(defn change-calc [change-requested change-given]
 (let [calculated
 (get-max-smaller-than change-requested)]
 (let [upd-change-given
 (conj change-given calculated)]
 (let [sub-request (- change-requested calculated)]
 (if (= sub-request 0)
 upd-change-given (recur sub-request upd-change-given))))))

Answer 1

First, there is nothing wrong with your recursive call: recur is about as idiomatic as Clojure gets.

Now, let's try to improve your code.

• If you look at it, smaller-than? is a synonym for >=. It just passes it the same arguments in the same order.

You could define it as ...

(def smaller-than? >=)

... or, better, just use >=. If you want your own name, you'd have been better to call it not-smaller-than?.

• There is no need to nest lets in change-calc. One let will do. Successive bindings in a let are evaluated in order.
• Try to choose suggestive names. I'd replace the meaningless calculated with something like candidate.

Thus we get

(defn max-smaller-than [input]
 (apply max (filter (partial >= input) in-bank)))
(defn change-calc [change-requested change-given]
 (let [candidate (max-smaller-than change-requested)
 upd-change-given (conj change-given candidate)
 sub-request (- change-requested candidate)]
 (if (= sub-request 0)
 upd-change-given (recur sub-request upd-change-given))))

There are a couple of worries here:

• We'd better deal with a zero change-requested directly than work out it's going to be zero next time round.
• The test for sub-request is for exactly zero. What happens if we can't give exact change? (With 1 in in-bank, this will not arise. But if it ever does, max throws an arity exception).

These revisions get us to

(defn change-calc [change-requested change-given]
 (if (pos? change-requested)
 (let [candidate (max-smaller-than change-requested)
 upd-change-given (conj change-given candidate)
 sub-request (- change-requested candidate)]
 (recur sub-request upd-change-given))
 change-given))

But this doesn't deal with the exception throwing problem. What is perhaps a better solution to this follows.

---

Let's look at the problem afresh.

Your code returns

• its second (sequence) argument with ...
• the change from the in-bank denominations conj-ed onto it, so at the front/back if the sequence is a list/vector.

In any programming language, the second function should be distinct: especially in Clojure, where it is easy to append to a vector.

How do we do it?

• For the change, we can return a count of how many coins there are of each denomination, using a map from denomination to number. If Clojure had a standard multiset/bag, we'd use it instead.
• And let's make the denomination set an explicit argument.

If we want to make up a sum from a number of denominations, we can do the following:

(defn change [sum denoms]
 (reduce
 (fn [[ans ch :as both] d]
 (let [c (quot ch d)]
 (if (zero? c) both [(assoc ans d c) (mod ch d)])))
 [{} sum]
 (sort > denoms)))

This is more or less the algorithm you wrote, with a few wrinkles:

• We sort the denominations in decreasing order.
• We deal with each once and for all through a reduce.
• We use quot and mod to short-circuit a loop using subtraction.

The result is a pair:

• a map representing a multiset of how many (non-zero) there are of each denomination, and
• a number for how much change is left over unreconciled.

Examples:

(change 8 in-bank)
;[{1 1, 2 1, 5 1} 0]
(change 8 #{2 5 10})
;[{2 1, 5 1} 1]
(change 13 #{1 5 10})
;[{1 3, 10 1} 0]

• The idea of returning the residue too arose from the algorithm, where it is part of the working.
• If 1 is a denomination, the residue is always 0.
• A development might be to know how many of each coin were present to start with.

Answer 2

One thing to note is that you dont have to use 3 different let statements, you could just use one instead (each new 2-tuple in the let binding group is aware to all its previous bindings).

Another thing, you might not want to expose 'change-given' to the user, since it generally has to be an empty list, so you could "confine" your recursion using the loop macro, like this:

(defn change-calc [change-requested]
 (loop [change-requested change-requested change-given []]
 (let [calculated (get-max-smaller-than change-requested)
 upd-change-given (conj change-given calculated)
 sub-request (- change-requested calculated)]
 (if (zero? sub-request)
 upd-change-given
 (recur sub-request upd-change-given)))))

If you really wanted to get rid of explicit recursion, you could always use implicit one, using methods such as reduce and iterate. here is an example:

(defn change-calc [change-requested]
 (second
 (last
 (take-while (complement nil?)
 (iterate (fn[[n coins]]
 (when (pos? n)
 (let [coin (get-max-smaller-than n)]
 [(- n coin) (cons coin coins)]))) [change-requested []])))))

reduce is a catamorphism, which informally shrinks a list into a number. You are looking for the reverse operation, blowing a number into a list, this is called anamorphism. You could read this interesting blog post about anamorphisms in clojure

• Thumbnail: This applies a set of numbers (the implicit denominations argument) to a number and produces a multiset/bag of numbers, albeit not recognised as such in the code.

Answer 3

Slightly modified version using loop-recur. Use vector for in-bank to find biggest denom faster. You are using set and filter+max which do a lot more work than filter+first.

(def in-bank [10 5 2 1])
(defn change-calc [n]
 (loop [rem n change []]
 (if-let [sm (first (filter (partial >= rem) in-bank))]
 (recur (- rem sm) (conj change sm))
 change)))

---

To answer how is this better, using criterium bench original code clocks in 15ms, my code - 7.5ms for (change-calc 99999) Using vector for in-bank fit better here.

• Malachi: why is it better than the original post?
• edbond: @Malachi it's shorter and easier to read.
• edbond: also note that in-bank is a vector and don't need to filter and apply max and find first instead.
• Malachi: so your review of the original post is "use a vector it's faster" ? this isn't a good review, you should explain how it makes the code faster and better.
• edbond: @Malachi yes, it's the answer to "suggest a better (more Clojure-like) way of implementing it". It is more concise, faster and more Clojure-like.