Skip to content

Instantly share code, notes, and snippets.

@kidpollo
Last active August 29, 2015 14:20
Show Gist options
  • Save kidpollo/9da8d4779ed0695667f0 to your computer and use it in GitHub Desktop.
Save kidpollo/9da8d4779ed0695667f0 to your computer and use it in GitHub Desktop.
(defn make-change [x coinset]
(loop [x x
change []]
(let [possible-coins (take-while #(when (>= x %) %) coinset)
current-coin (some #(when (zero? (rem x %)) %) possible-coins)]
(cond
(= x (reduce + possible-coins))
(concat possible-coins change)
(= x 0)
change
(nil? current-coin)
(throw (Exception. "cant make change"))
:else
(recur (- x current-coin) (conj change current-coin))
)
)
))
=> #'user/make-change
(make-change 5 [2 5])
=> (5)
(make-change 6 [2 5])
=> (2 2 2)
(make-change 7 [2 5])
=> (2 5)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment