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!