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

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.