Solving Project Euler problem 1 in Clojure « Blog Archive

Posted on June 25th, 2011 by icyrock.com

Solving Project Euler problem 1 in Clojure

I’ve been playing with Clojure lately and what better way to engage in a new general-purpose programming language then Project Euler. I’m going to be showing my solutions to problems. You can find solutions to other problems by looking at the posts tagged euler.

Note that you should carefully consider taking this as an example of good Clojure programming – I’m fairly new to the language. This also holds true for other sides of this: functional programming style or solving problems in general. Project Euler forums will probably provide a good set of tips whether the solution I provide is at all good and I will, in fact, try to comment on the solution after I solve it by comparing it to other solutions that I can find either on the forum or on other web sites.

Maybe the best way to depict what I’ll be doing is a variation of Project Euler’s disclaimer:

Providing quality problems for entertainment and educational purposes 
will continue to be the main goal of Project Euler, regardless of the 
intentions of a minority of the members.

In my case – all I’m trying is to hopefully learn Clojure and maybe some math in the process. Hope it’s useful, but take all with a grain of salt.

Solution to problem 1

Here’s one way to solve it:

; The following problem is taken from Project Euler.
; http://projecteuler.net/index.php?section=problems&id=1

; Problem:
; 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.

(ns com.icyrock.clojure.euler.problem1
  (:use clojure.test))

(defn sum-multiples [upTo]
  (let [nums (range 1 upTo)
        f3 #(= 0 (mod % 3))
        f5 #(= 0 (mod % 5))
        f3or5 (fn [n] (or (f3 n) (f5 n)))
        filtered (filter f3or5 nums)]
    (apply + filtered)))

(deftest sum-multiples-test
  (is (= (sum-multiples 10) 23)))

(run-tests)

(defn solution []
  (println (sum-multiples 1000)))

(solution)

Before I discuss the above, a small digression.

Template

I decided to do two things wile solving all the problems:

Put the problem itself (or as much as feasible – e.g. some problems require using additional files or have embedded graphics) at the top of the file
Use TDD process to solve these

so I made a small template to be used for all problems. It’s fairly simple and obvious from the below problem’s code. Some common things are:

The comment section with the attribution to Project Euler and the direct link to the problem itself

; The following problem is taken from Project Euler.
; http://projecteuler.net/index.php?section=problems&id=1

; Problem:
; 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.

Namespace definition and including the necessary libraries

(ns com.icyrock.clojure.euler.problem1
  (:use clojure.test))

Here I define the namespace, which will always be the same as above, except the number at the end will be unique to each of the problems. Namespaces are Clojure’s way to separate mappings from each other in a meaningful way. To read more, go here. :use symbol in the ns macro is used to include things from other namespaces. You can read about it here.

In the above example, I’m just including one namespace and that’s clojure.test, which contains deftest and is macros and run-tests function for TDD. Look here for the API reference of clojure.test

Following the above is a set of functions that I’ll be combining to get to the solution – in the above case, it’s this block of code:

(defn sum-multiples [upTo]
  (let [nums (range 1 upTo)
        f3 #(= 0 (mod % 3))
        f5 #(= 0 (mod % 5))
        f3or5 (fn [n] (or (f3 n) (f5 n)))
        filtered (filter f3or5 nums)]
    (apply + filtered)))

(deftest sum-multiples-test
  (is (= (sum-multiples 10) 23)))

I’ll focus on the above in the next section. One general note here is that the tests are usually taken from the samples from the problems. That is, Project Euler problems are usually designed so they explain the problem on a simple(r) case, which makes a great test case and fits neatly into TDD. Sometimes, when problems are more complex, I use more examples or add tests for other functions that I made.

Finally, I call run-tests to run all the tests and I define a simple function called solution that I usually pass some parameters to get to the actual solution to the problem:

(run-tests)

(defn solution []
  (println (sum-multiples 1000)))

(solution)

The reason I’m passing an argument 1000 to sum-multiples is because I usually try to make functions a bit more generic than necessary for the problem. This makes me think more and hopefully learn some more things about Clojure.

The solution itself

To return to the solution itself:

(defn sum-multiples [upTo]
  (let [nums (range 1 upTo)
        f3 #(= 0 (mod % 3))
        f5 #(= 0 (mod % 5))
        f3or5 (fn [n] (or (f3 n) (f5 n)))
        filtered (filter f3or5 nums)]
    (apply + filtered)))

is fairly linear:

I define nums to be all numbers we are interested in – range is the function that gives us exactly that
f3 and f5 represent anonymous functions that, when applied to a number, will tell you whether the number is evenly divisible by 3 and 5, respectively
f3or5 is a combination of the above – it’s again an anonymous function, though defined with (fn …) instead of #(…) – but these are the same things anyway. You can read more about this and a lot of other Clojure things in this great article, specifically this chapter
filtered is a variable that we get using the filter function, which filters the given collection (nums in this case) with a given function (f3or5 in this case). The end result is only the items from a collection that we care about – and these are the ones divisible by 3 or 5, or the ones for which f3or5 returns true.
At the end, (apply + filtered) will apply the + function to the filtered numbers, which will essentially sum all the numbers – and that’s the solution we need

The test is fairly simple and is based on the example in the problem itself:

(deftest sum-multiplesTest
  (is (= (sum-multiples 10) 23)))

So we expect the sum of all numbers 1 – 10 to be 23.

icyrock.com