Skip to content

Instantly share code, notes, and snippets.

@thomascothran

thomascothran/coinChange.clj

Created October 25, 2017 00:07
Show Gist options
  • Save thomascothran/ad54f7ec484359203ae1fe805f128d08 to your computer and use it in GitHub Desktop.
Save thomascothran/ad54f7ec484359203ae1fe805f128d08 to your computer and use it in GitHub Desktop.
Download ZIP
Coin Change Algorithm
Raw
coinChange.clj
; Answer to the challenge at https://www.hackerrank.com/challenges/coin-change
(use '[clojure.string :only (split triml)])
; Put our input into a form we can use
(def input (let [i (line-seq (java.io.BufferedReader. *in*))]
(-> i
(#(clojure.string/join " " %))
(#(split % #" "))
(#(map read-string %)))))
; The core logic
(def answer-helper (memoize (fn [amt coins]
(cond (= amt 0) 1 ; You've calculated change without any remainder!
(or (< amt 0) (= (count coins) 0)) 0 ; No coins left or no amount left to change
:else (+ (answer-helper amt (rest coins)) ; Add the ways change can be made w/o the first coin
(answer-helper (- amt (first coins)) coins)))))) ; to the ways it can be made using the first coin
(defn answer [[total _ & denominations]]
; Pass off all the work to our helper function
(answer-helper total denominations))
(println (answer input))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment