coinstar.clj

;; This one doesn't agree with Danny's test-cases but I think it matches the spirit of
;; the problem a little better in that it doesn't include an entry for the coin if
;; the quantity of that coin would be zero.
;;
;; Also, we're global, so I used UK coins
;;
;; So e.g. (change-coins 18) = {10 1, 5 1, 2 1, 1 1}

(def coins [100 50 20 10 5 2 1])

(defn change-coins
  [x]
  (cond
    (= x 0) {}
    :else (let [coin (first (filter #(<= % x) coins))
                qty (quot x coin)]
            (merge
             {coin qty}
             (change-coins (- x (* coin qty)))))))