-
-
Save mikelikesbikes/3907239 to your computer and use it in GitHub Desktop.
Change Maker in clojure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns katas.change-maker) | |
(defn num-pairs | |
"Returns all combinations of [x y] and (<= x y) where (= cents (+ x y))" | |
[cents] | |
(for [x (reverse (range 1 (inc (quot cents 2)))) ;; use the range from midpoint to 1 so that we walk the | |
;; shortest side of the tree first | |
:let [y (- cents x)]] | |
[x y])) | |
;; Not tail recursive so can blow the stack | |
(defn change-maker | |
([cents] (change-maker cents '(25 10 5 1))) | |
([cents coins] | |
(cond | |
(zero? cents) [] | |
(some #{cents} coins) [cents] | |
:else (let [pairs (num-pairs cents) | |
stacks (for [[x y] pairs] | |
(concat | |
(change-maker x coins) | |
(change-maker y coins))) | |
optimal-stack (apply min-key count stacks)] | |
(sort-by - optimal-stack))))) | |
(alter-var-root #'change-maker memoize) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns katas.change-maker) | |
;; tail recursive but naive — will miss some test cases | |
(defn change-maker | |
([cents] (change-maker cents '(25 10 5 1) [])) | |
([cents coins] (change-maker cents coins [])) | |
([cents coins change] | |
(if (or (zero? cents) (empty? coins)) | |
change | |
(let [coin (apply max (filter (partial >= cents) coins))] | |
(recur (- cents coin) coins (conj change coin)))))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns katas.change-maker-test | |
(:use clojure.test | |
katas.change-maker)) | |
(deftest change-maker-tests | |
(are [cents coins] (= (change-maker cents) coins) | |
0 [] | |
26 [25 1] | |
24 [10 10 1 1 1 1] | |
49 [25 10 10 1 1 1 1] | |
1000 (repeat 40 25)) ;; this will blow the stack for a suboptimal recursively memoized implementation | |
(are [cents coins] (= (apply change-maker cents) coins) | |
'(26 [10 25 1 5]) [25 1] | |
;; the following two won't work with a greedy change maker: | |
'(24 [10 7 1]) [10 7 7] | |
'(14 [10 7 1]) [7 7])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment