# Clojure programming exercise for calculating change

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))))))


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.

• 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.

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

• 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. – Thumbnail Nov 19 '14 at 16:54

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.

• why is it better than the original post? – Malachi Nov 18 '14 at 22:30
• @Malachi it's shorter and easier to read. – edbond Nov 19 '14 at 12:09
• also note that in-bank is a vector and don't need to filter and apply max and find first instead. – edbond Nov 19 '14 at 12:10
• 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. – Malachi Nov 19 '14 at 14:15
• @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. – edbond Nov 19 '14 at 14:40