Codelesson Clojure Assignment 2

assignment_2.clj

;; ... Given a bunch of dollar bills, in how many ways can they be broken into coins?
;;
;; ======================
;; Algorithm
;;
;; For each coin, calculate a set of multiples from zero to the largest
;; number which is less than or equal to the dollar-value goal.  Find
;; the combinations, choosing one multiple from each set, which total to 
;; the goal.
;;
;; For example, to calculate combinations of 50c, 25c, 10c, and 5c, that
;; total to 50c, choose one value from each row.  (Edge case: need to
;; return 0 where the requested total is 0)
;; 
;; 1*50 0*50
;; 2*25 1*25 0*25
;; 5*10 4*10 3*10 2*10 1*10 0*10
;; 10*5 9*5 8*5 7*5 6*5 5*5 4*5 3*5 2*5 1*5 0*5
;;

(ns codelesson.assignment-2)

(defn max-multiple
  "the maximum multiple of this coin that is less than or equal to goal-cents"
  [goal-cents coin-value]  
  (- goal-cents (mod goal-cents coin-value)))

(defn multiples
  "all the multiples of the coin value that are less than goal-cents, including zero"
  [goal-cents coin-value]
  (range (max-multiple goal-cents coin-value) -1 (- coin-value)))
  
(declare count-coin-combinations-cents)

(defn- find-combinations  
  "find combinations with other coin-values which go with this coin-multiple"
  [goal-cents coin-value-set current-multiple]
  
  (if (= current-multiple goal-cents) ; found match, prune the results
    1
    (if (empty? coin-value-set) ; can't make an exact match, halt
      0
      (count-coin-combinations-cents (- goal-cents current-multiple) coin-value-set))))

(defn- count-coin-combinations-cents [goal-cents coin-value-set]
  {:pre  [(pos? goal-cents)] }      
  (let [multiples-of-coin-value (multiples goal-cents (first coin-value-set))
        remaining-coin-value-set (rest coin-value-set)]
    (reduce +
            ;; for each coin-multiple, search for combinations that fit with it
            (map #(find-combinations goal-cents remaining-coin-value-set %)
                 multiples-of-coin-value))))

(defn count-coin-combinations
  "Calculate the combinations of coins in coin-value-set that make up a dollar"
  [goal-dollars coin-value-set]
  (count-coin-combinations-cents (* 100 goal-dollars) coin-value-set))

(ns codelesson.test.assignment-2
  (:use codelesson.assignment-2)
  (:use clojure.test))

(deftest ten-dollars-with-50-25
  (is (= 3 (count-coin-combinations 1 [50 25]))))

(deftest ten-dollars-with-50
  (is (= 1 (count-coin-combinations 10 [50]))))

(deftest one-dollar-with-50-25-10-5-1
  (is (= 292 (count-coin-combinations 1 [50 25 10 5 1]))))

(deftest two-dollars-with-100-50-25-10-5-1
  (is (= 2728 (count-coin-combinations 2 [100 50 25 10 5 1]))))

(deftest one-dollar-with-49-1
  (is (= 3 (count-coin-combinations 1 [49 1]))))

(deftest zero-dollars-fails-assertion
  (is (thrown? Throwable #"Assert failed" (count-coin-combinations 0 [49 1]))))