break-coins.clj

break_coins.clj

(ns my-coins-project.core)

;; Return all the different ways you can make change for a given amount of cents. 
;; Basic idea is to start with number of pennies and then successively apply `apply-coin` for each coin in order from
;; largest to smallest. `apply-coin` will take a lazy seq of existing combinations and return a new lazy seq that includes
;; a new combination with each possible quantity of the coin in question for each existing combination.
;;
;;  (apply-coin [:quarter 25] [{:penny 60}])
;;  ;; -> [{:quarter 0, :penny 60}, {:quarter 1, :penny 35}, {:quarter 2, :penny 10}]
;;
;;  (apply-coin [:dime 10] [{:quarter 0, :penny 60}, {:quarter 1, :penny 35}, {:quarter 2, :penny 10}])
;;  ;; -> [{:quarter 0, :dime 0, :penny 60} {:quarter 0, :dime 1, :penny 50} ...]

(def ^:private coins
  [[:quarter 25] [:dime 10] [:nickel 5]])

(defn- apply-coin [[coin-name coin-value] ms]
  (for [{:keys [penny], :as m} ms
        total-value            (range 0 (inc penny) coin-value)
        :let                   [quantity (/ total-value coin-value)]]
    (assoc m coin-name quantity, :penny (- penny total-value))))

(defn- change [amount]
  (loop [[coin & more] coins, acc [{:penny amount}]]
    (let [acc (apply-coin coin acc)]
      (if-not (seq more)
        acc
        (recur more acc)))))

Version that works without pennies

(ns my-coins-project.core)

(def ^:private coins
  [[:quarter 25] [:dime 10] [:nickel 5] [:penny 1]])

(defn- apply-coin [[coin-name coin-value] ms]
  (for [{:keys [remaining], :as m} ms
        total-value            (range 0 (inc remaining) coin-value)
        :let                   [quantity (/ total-value coin-value)]]
    (assoc m coin-name quantity, :remaining (- remaining total-value))))

(defn- change [amount]
  (loop [[coin & more] coins, acc [{:remaining amount}]]
    (let [acc (apply-coin coin acc)]
      (if-not (seq more)
        (filter (comp zero? :remaining) acc)
        (recur more acc)))))