euler31.clj

; 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).")