Project Euler Problem 31 asks us to find the number of possible English coin combinations that add up to £2.

Creating a full enumeration of all possible coin combinations involving 200 coins and then filtering it would be prohibitively expensive, so instead I adopted a recursive definition that that only looks at valid combinations:

(def coins [200 100 50 20 10 5 2 1])

(defn coin-combos [sum goal maxcoin]
  (let [valid (filter #(and (>= maxcoin %)
                            (>= (- goal sum) %)) coins)]
    (if (empty? valid)
      (if (= sum goal) 1 0)
      (reduce + (map #(coin-combos (+ sum %) goal %) valid)))))

(defn euler-31 []
  (coin-combos 0 200 200))

This works, and takes about 4.5 seconds to execute. However, bibi’s solution on clojure-euler blows that out of the water, taking less than 100ms to execute:

(def coins [200 100 50 20 10 5 2 1])
 
(defn change[c v]
  (let [f (first c)]
    (if (= f 1) 1
      (reduce + (for [n (range 0 (inc (quot v f)))]
                  (change (rest c) (- v (* n f))))))))

(defn euler-31-bibi []
  (change coins 200))

Nice work, bibi!