Thursday, November 18, 2010

Project Euler Problem 1 in Clojure

Presented in this article is my progressively refined solution to Project Euler Problem 1.
Project Euler's Problem 1 is:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
My first cut reveals me structured programming background. I'm sure any functional programming experts will run screaming at the sight of it. The only redeeming feature (in my opinion) of my implementation is the use of iteration through recursion.
(defn div-3? [n] (= 0 (mod n 3)))
(defn div-5? [n] (= 0 (mod n 5)))
(defn div-3-or-5? [n] (or (div-3? n) (div-5? n)))

(defn euler1 [total count max-count]
  (if (>= count max-count)
      (if (div-3-or-5? count)
        (recur (+ total count) (inc count) max-count)
        (recur total (inc count) max-count)))))

(def result (euler1 0 0 1000))

(println result)
My first refactoring of this code came about when I realised the div-3?, div-5? and div-3-or-5? functions are actually predicates (functions that return true or false) and can be passed to the Clojure supplied higher order function filter. Applying to the sequence of consecutive integers from 0 to 1000 yields the sequence of integers divisible by 3 or 5 which are the integers that need to be summed to yield the final result. The summation can be peformed with Clojure's reduce function.
(defn div-3? [n] (= 0 (mod n 3)))
(defn div-5? [n] (= 0 (mod n 5)))
(defn div-3-or-5? [n] (or (div-3? n) (div-5? n)))

(defn euler1 []
  (reduce +
    (filter div-3-or-5? (range 1000))))

(def result (euler1))

(println result)
My final refactoring is simply a reduction of the code into a single line. The major Clojure feature exhibited here is the use of an inline function provided to the filter function.
  (reduce +
      #(or (= 0 (mod % 3)) (= 0 (mod % 5)))
      (range 1000))))
This is where I left my solution to the problem, though I wasn't entirely happy with it. In particular, the (= 0 (mod % 3)) lines felt unclear.

Other solutions in Clojure can be found in GitHub (search for clojure euler). Csaba Okrona has also provided Clojure solutions to some Project Euler problems.

Creative Commons License

No comments: