How to write this small program better?

Question

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 [1] (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))))))

Answer 1

How about something like this:

(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 [1] (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!

Answer 2

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 [1] (repeat max-coin 0))
=>
(into [1] (repeat max-coin 0))

Answer 3

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.

Answer 4

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