0031b.clj

; In England the currency is made up of pound, £, and pence, p, and
; there are eight coins in general circulation:
;
;    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
;
; It is possible to make £2 in the following way:
;
;    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
;
; How many different ways can £2 be made using any number of coins?

; 0031b.clj, but cleaned up for "modern" clojure and idioms

(defn countpence
  ([] (countpence 0 [200 100 50 20 10 5 2 1]))
  ([sum opts]
    (cond
      (== sum 200) 1
      (>  sum 200) 0
      (not opts)   0
      :else (+ (countpence sum (rest opts))
               (countpence (+ sum (first opts)) opts)))))

(prn (countpence))

;; Recursive solution changing coins and amount
(defn make-change-recurse
  "Return the number of ways to make the correct change for `amount` given a
  vector of `coins` sorted from smallest to largest."
  [coins amount]
  (cond
    (neg? amount) 0
    (zero? amount) 1
    (= [1] coins) 1
    (= [1 2] coins) (inc (quot amount 2))
    :else (apply +
                 (for [sub-coins (rest (reductions conj [] coins))]
                   (make-change-recurse sub-coins
                                        (- amount (last sub-coins)))))))

(defn make-change [total [coin & coins]]
  (cond
    (zero? total) 1
    (nil? coin) 0
    :else (apply +
                 (for [branch (range (inc (quot total coin)))]
                     (make-change (- total (* branch coin)) coins)))))