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.

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.

StackExchange Code Review Q#70223, answer score: 4