Skip to content

Instantly share code, notes, and snippets.

@xavi
Created June 16, 2013 18:05
Show Gist options
  • Save xavi/5792860 to your computer and use it in GitHub Desktop.
Save xavi/5792860 to your computer and use it in GitHub Desktop.
; In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
; 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
; It is possible to make £2 in the following way:
; 1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p
; How many different ways can £2 be made using any number of coins?
;
; http://projecteuler.net/problem=31
; coins #{1 2 5 10 20 50 100 200}
;
; =>
; (
; ([1 2] [1 1]) ; 1 coin of 2p, 1 coin of 1p
; ([3 1])
; )
(defn coin-combinations [coins amount]
(let [max-coin (apply max coins)
max-coin-max-count (quot amount max-coin)]
(if (= max-coin 1)
(list (list [amount 1])) ; (([amount 1]))
(let [max-coin-counts
; ([0 max-coin] [1 max-coin] ... [max-coin-max-count max-coin])
(map #(vector % max-coin) (range (inc max-coin-max-count)))]
(reduce (fn [combinations [coin-count coin-value :as count-value-pair]]
(let [remainder-coins (disj coins max-coin)
remainder-amount (- amount (* coin-count coin-value ))]
(concat
combinations
(map #(conj % count-value-pair)
(coin-combinations remainder-coins remainder-amount)))))
()
max-coin-counts)))))
(defn format-combination [combination]
(clojure.string/join
" + "
(map #(str (first %) "x" (second %) "p")
(filter #(pos? (first %)) combination))))
(def two-pounds-combinations (coin-combinations #{1 2 5 10 20 50 100 200} 200))
(doall (map #(println (format-combination %)) two-pounds-combinations))
(println "There are" (count two-pounds-combinations) "ways of making £2 (200p).")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment