Renders coins and headaches

change.clj

;; This buffer is for Clojure experiments and evaluation.
;; Press C-j to evaluate the last expression.

;; Hey Sameer, thanks again for taking the time today. I'm afraid my
;; solution is gonna be a little disappointing; nonetheless I wanted
;; to share it.

;; The algorithm I wanted to write was: for each coin, there is a
;; positive sequence of values that represent c0, c1 ... cn where n
;; cannot be greater than the value of the change targeted. Iterating
;; over all the (finite) combinations of those sequences would either
;; yield a match or not.


;; I knew how to generate those combinations using `for`:

(defn coin-seq [value max]
  (range 0 max value))

(let [x 12]
  (for [c1 (coin-seq 1 x)
        c2 (coin-seq 5 x)
        c3 (coin-seq 10 x)]
    {:coins (zipmap [1 5 10] [c1 c2 c3]) :amount (apply + [c1 c2 c3])}))
;;=> ({:coins {1 0, 5 0, 10 0}, :amount 0} {:coins {1 0, 5 0, 10 10}, :amount 10} {:coins {1 0, 5 5, 10 0}, :amount 5} {:coins {1 0, 5 5, 10 10}, :amount 15} {:coins {1 0, 5 10, 10 0}, :amount 10} {:coins {1 0, 5 10, 10 10}, :amount 20} {:coins {1 1, 5 0, 10 0}, :amount 1} {:coins {1 1, 5 0, 10 10}, :amount 11} {:coins {1 1, 5 5, 10 0}, :amount 6} {:coins {1 1, 5 5, 10 10}, :amount 16} {:coins {1 1, 5 10, 10 0}, :amount 11} {:coins {1 1, 5 10, 10 10}, :amount 21} {:coins {1 2, 5 0, 10 0}, :amount 2} {:coins {1 2, 5 0, 10 10}, :amount 12} {:coins {1 2, 5 5, 10 0}, :amount 7} {:coins {1 2, 5 5, 10 10}, :amount 17} {:coins {1 2, 5 10, 10 0}, :amount 12} {:coins {1 2, 5 10, 10 10}, :amount 22} {:coins {1 3, 5 0, 10 0}, :amount 3} {:coins {1 3, 5 0, 10 10}, :amount 13} {:coins {1 3, 5 5, 10 0}, :amount 8} {:coins {1 3, 5 5, 10 10}, :amount 18} {:coins {1 3, 5 10, 10 0}, :amount 13} {:coins {1 3, 5 10, 10 10}, :amount 23} {:coins {1 4, 5 0, 10 0}, :amount 4} {:coins {1 4, 5 0, 10 10}, :amount 14} {:coins {1 4, 5 5, 10 0}, :amount 9} {:coins {1 4, 5 5, 10 10}, :amount 19} {:coins {1 4, 5 10, 10 0}, :amount 14} {:coins {1 4, 5 10, 10 10}, :amount 24} {:coins {1 5, 5 0, 10 0}, :amount 5} {:coins {1 5, 5 0, 10 10}, :amount 15} {:coins {1 5, 5 5, 10 0}, :amount 10} {:coins {1 5, 5 5, 10 10}, :amount 20} {:coins {1 5, 5 10, 10 0}, :amount 15} {:coins {1 5, 5 10, 10 10}, :amount 25} {:coins {1 6, 5 0, 10 0}, :amount 6} {:coins {1 6, 5 0, 10 10}, :amount 16} {:coins {1 6, 5 5, 10 0}, :amount 11} {:coins {1 6, 5 5, 10 10}, :amount 21} {:coins {1 6, 5 10, 10 0}, :amount 16} {:coins {1 6, 5 10, 10 10}, :amount 26} {:coins {1 7, 5 0, 10 0}, :amount 7} {:coins {1 7, 5 0, 10 10}, :amount 17} {:coins {1 7, 5 5, 10 0}, :amount 12} {:coins {1 7, 5 5, 10 10}, :amount 22} {:coins {1 7, 5 10, 10 0}, :amount 17} {:coins {1 7, 5 10, 10 10}, :amount 27} {:coins {1 8, 5 0, 10 0}, :amount 8} {:coins {1 8, 5 0, 10 10}, :amount 18} {:coins {1 8, 5 5, 10 0}, :amount 13} {:coins {1 8, 5 5, 10 10}, :amount 23} {:coins {1 8, 5 10, 10 0}, :amount 18} {:coins {1 8, 5 10, 10 10}, :amount 28} {:coins {1 9, 5 0, 10 0}, :amount 9} {:coins {1 9, 5 0, 10 10}, :amount 19} {:coins {1 9, 5 5, 10 0}, :amount 14} {:coins {1 9, 5 5, 10 10}, :amount 24} {:coins {1 9, 5 10, 10 0}, :amount 19} {:coins {1 9, 5 10, 10 10}, :amount 29} {:coins {1 10, 5 0, 10 0}, :amount 10} {:coins {1 10, 5 0, 10 10}, :amount 20} {:coins {1 10, 5 5, 10 0}, :amount 15} {:coins {1 10, 5 5, 10 10}, :amount 25} {:coins {1 10, 5 10, 10 0}, :amount 20} {:coins {1 10, 5 10, 10 10}, :amount 30} {:coins {1 11, 5 0, 10 0}, :amount 11} {:coins {1 11, 5 0, 10 10}, :amount 21} {:coins {1 11, 5 5, 10 0}, :amount 16} {:coins {1 11, 5 5, 10 10}, :amount 26} {:coins {1 11, 5 10, 10 0}, :amount 21} {:coins {1 11, 5 10, 10 10}, :amount 31})


;; From there it's easy to filter so that `:amount` matches our `x` and return `:coins`.

;; But alas, that approach using `for` to generate the cartesian product of all combinations
;; only works if you can hard-code in the coins, which we can't do in our problem.

;; I took a stab at a cartesian product formula by myself, but timed
;; out on it. Googling, it's fairly easy to find Alan Malloy's drop-in
;; function for that, but I don't think it's cool to pass that off
;; like I figured it out myself. In a real-life situation, I'd of
;; course use it and move forward to this:

(defn cart
  "Credit: http://stackoverflow.com/a/18248031"
  [colls]
  (if (empty? colls)
    '(())
    (for [x (first colls)
          more (cart (rest colls))]
      (cons x more))))

(defn change [coinset x]
  (let [coin-seqs (map #(coin-seq % x) coinset)]
    (or ((comp :coins first)
         (filter #(= x (:amount %))
                 (map #(hash-map :amount (apply + %) :coins (zipmap coinset %))
                      (cart coin-seqs))))
        :error)))

(change [1 5 10] 12)
;;=> {1 2, 5 0, 10 10}

(change [5 10] 12)
;; => :error

;; In terms of optimizations, we could short-circuit if x is smaller
;; than `(apply min coinset)`; that's pretty low-hanging fruit. I'd
;; need to give more thought to optimize further.

;; Like I said, appreciated meeting with you and wish you lots of
;; encouragement on the product; I think you got something (not just
;; saying that).

;; Have a good weekend.