# Counting ways to form an amount using coins

This is just a fun little exercise I had to do for a homework once (in Java rather than Clojure though). Basically, the goal is to find the number of different coin stacks you can build with the coins 1,2,5 and 10 to form a number N (I believe a closed form solution for this exists, but this isn't what this is about).

My solution here works, but I'm not quite happy with it:

• Explicit loop. Not sure how to do away with it though.
• A few functions there that I think should be core functions, but I can't find them.
• Even if they aren't in core, my functions could probably be written somewhat more concisely

Anyways, here's my code (by the way, the function is called "fast-iterative" because the exercise was about calculating these values recursively. Which I think is insane due to the branching factor, but whatever):

(ns test.coin-stacks)

(def maximum (partial reduce max))

(defn shift-vector
"Shifts v one to the left, insert shift-val at the right"
[v shift-val]
(conj (vec (rest v)) shift-val))

(defn update
"Updates ks in m with f applied to ks.
I can't believe I have to write this myself."
[m ks f]
(apply assoc m (interleave ks (map (comp f m) ks))))

(defn fast-iterative-coinstacks
"Returns the number of ways to form a coin stack with a total
value of n with coins"
[n coins]
(let [max-coin (maximum coins)
initial-stacks (apply conj  (repeat max-coin 0))]
(loop [stacks initial-stacks iteration 0]
(if-not (< iteration n)
(first stacks)
(recur (shift-vector (update stacks coins (partial +' (stacks 0))) 0)
(inc iteration))))))


(defn shift-vector
"Shifts v one to the left, insert shift-val at the right"
[v shift-val]
(conj (subvec v 1) shift-val))

(defn update-in-all
"Updates ks in m with f applied for each value at k."
[m ks f]
(reduce (fn [m' k] (update-in m' [k] f)) m ks))

(defn fast-iterative-coinstacks
"Returns the number of ways to form a coin stack with a total
value of n with coins"
[n coins]
(let [max-coin (reduce max coins)
initial-stacks (into  (repeat max-coin 0))
process-stacks (fn [stacks]
(-> stacks
(update-in-all coins (partial + (first stacks)))
(shift-vector 0)))]
(-> (iterate process-stacks initial-stacks)
(nth n)
first)))


Some explanations:

• update-in works both with vectors and maps, and can update nested values as well,

• the threading macro -> makes the flow of your code easier to follow,

• iterate is a really convenient function that given f and x returns a lazy sequence of x, (f x), (f (f x))...

• you can do a lot of things with reduce!

I would write (def maximum (partial reduce max)) as:

(defn max-coll [coll] (apply max coll))


although writing a special function for (apply max coll) seems a bit overdone in my taste.

Another minor rewrite:

(apply conj  (repeat max-coin 0))
=>
(into  (repeat max-coin 0))


There's a nice recursive solution to this problem:

(defn options [total available-coins]
(if (seq available-coins) ;; have we got any coins left?
(let [[[coin max-available] & more-coins] (seq available-coins)
needed (quot total coin)
rem (mod total coin)]
(mapcat
(fn [n]
(map #(if (> n 0) (merge % {coin n}) %)
(options (- total (* coin n)) more-coins))) ;; recursive call
(range 0 (inc (min needed max-available)))))       ;; all possible quantities
(if (== total 0)
[{}]  ;; empty solution, no coins required
[]))) ;; no solution


This outputs the solutions for making a total using a map of coins -> count e.g.

(options 50 {10 3 20 3})
=> ({10 1, 20 2}
{10 3, 20 1})


Obviously, you can just count the number of solutions if you want the number of different stacks that could be made.

• I don't understand this one, what do you pass to this function and what do you return? – Cubic Oct 29 '12 at 9:26
• @Cubic: You pass 1) value of the wanted coin stack (total) and 2) "a map of coins -> count" (available-coins) and return a list of map of coins -> count. – user272735 Oct 29 '12 at 13:03
• In that case, this really doesn't solve the same problem. The problem I described doesn't actually put any limits on the coins that can be used, and the ordering of the coins in the stack matters (hence the metaphor of a stack). – Cubic Oct 29 '12 at 14:04

Your guess is almost right. Because your shift-vector function simply performs dequeue and enqueue, it can be rewritten using clojure.lang.PersistentQueue.

(defn shift-vector
[q x]
(-> q pop (conj x)))


You can use Clojure queues by starting with clojure.lang.PersistentQeueue/EMPTY.

By the way, your task seems to be a typical DP problem, since you mentioned that the order of coins mattered. I may show you another solution of O(n) DP using an array destructively.

(defn solve
[n coins]
(let [dp (doto (long-array (inc n))
(aset 0 1))]
(loop [i 0]
(if (< i n)
(do
(doseq [c coins]
(let [j (+ i c)]
(if (<= j n)
(aset dp j (+ (aget dp i)
(aget dp j))))))
(recur (inc i)))
(aget dp n)))))


Examples:

user> (solve 1 [1 2 5 10])
1
user> (solve 2 [1 2 5 10])
2
user> (solve 5 [1 2 5 10])
9
user> (solve 82 [1 2 5 10])
7637778505022614185

• I didn't use PersistentQueue because I wanted random access for my algorithm. I also didn't want to use more space than strictly necessary (this might be an unnecessary concern, since it takes pretty long with a million elements anyways), so I create a smaller vector than you do. I don't know what a "dp" is or how your solution is different from mine though. – Cubic Oct 31 '12 at 16:10