Last active
October 11, 2015 18:47
-
-
Save bjeanes/3902930 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 (range 1 cents) | |
:let [y (- cents x)] | |
:when (<= x y)] | |
[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)] | |
(reverse (sort 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) | |
26 [25 1] | |
24 [10 10 1 1 1 1] | |
49 [25 10 10 1 1 1 1] | |
0 []) | |
(are [cents in-coins out-coins] (= (change-maker cents in-coins) out-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])) |
Also the second set of tests can be a little cleaner since are
supports more than two bindings:
(are [cents in-coins out-coins] (= (change-maker cents in-coins) out-coins)
26 [10 25 1 5] [25 1]
...)
Oh duh... I didn't even think about having more than two bindings. That's pretty fricking obvious :P. Damn it >.<
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I bet changing line 7 to
(reverse (range 1 cents))
would cause it to not blow the stack on any reasonable input.