;; Count Change Function
;; The =count-change= function has two parts, the first (at the end)
;; sorts the coins from largest to smallest, and calls the /inner
;; function/, =change-acc=.
;; After covering the end cases, tHe inner function simply counts the
;; possibilities based on each of the two paths, and returns the sum.
(defn count-change
"Returns the number of ways to make change for an amount with a list of coins."
[money coins]
(letfn [(change-acc [money coins]
(let [available-coins (filter (fn [c] (<= c money)) coins)]
(cond
(= money 0) 1 ;; Happy Ending!
(< money 0) 0
(= (count available-coins) 0) 0
:else
(+ (change-acc (- money (first coins)) coins)
(change-acc money (rest coins))))))]
(if (= money 0)
0
(change-acc money (reverse (sort coins))))))
;; This /naive approach/ begins by sorting coins from highest to
;; lowest, and then we use the top coin, and make change with
;; the money left.
(defn get-change
"Return a list of coins needed to make change for an amount with a list of coins."
[money coins]
(letfn [(get-change-acc [money coins]
(let [available-coins (filter (fn [c] (<= c money)) coins)]
(cond
(= money 0) '() ;; Happy Ending!
(= (count available-coins) 0) '()
:else
(let [biggest-coin (first available-coins)]
(cons biggest-coin
(get-change-acc (- money biggest-coin)
available-coins))))))]
(if (= money 0)
'(0)
(get-change-acc money (reverse (sort coins))))))
;; Better Approach
;; The next idea is to simply run the =get-change= function with
;; subset collections of the coin list to see which is the smallest
;; approach.
(defn get-better-change
"Returns a smaller number of coins to make change"
[money coins]
(letfn [(get-all-change [money coins]
(if (> (count coins) 0)
(cons (get-change money coins)
(get-all-change money (rest coins)))))
(smallest-list [list-a list-b]
(if (< (count list-a) (count list-b))
list-a
list-b))]
(reduce smallest-list (get-all-change money (reverse (sort coins))))))