counting_coins_cfi.clj

;; Counting Coins
;; problem from "Coding for Interviews" news letter. 
;; notes: switching to vector from raw list gave a tremendous performance boost
;; uses memoize as variant of Y-combinator.

(let
    [coins (map read-string (clojure.string/split (read-line) #","))
     amt (read-string (read-line))
     change3 (fn [rec amt coins]
               (cond
                (= amt 0) 1
                (empty? coins) 0
                :true (let [c (peek coins)
                            ways (for [x (range 0 (inc (quot amt c)))]
                                   (rec rec (- amt (* x c) ) (pop coins)))]
                        (reduce + ways))
                )
                )]
  (println (change3 (memoize change3) amt (vec coins))))