Learning Clojure - Part 3 | Solving Project Euler 01

[oyvindsabo]

I'll try to make this post short and to the point (yeah, right...).

As an introduction to the Clojure programming language, I decided to solve Project Euler Problem 01:

Problem 1
Multiples of 3 and 5
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.

After spending some time studying the ClojureDocs and discussing with one of my colleagues, I had finally learnt enough Clojure to solve the problem. I ended up with the following solution:

(apply + (filter
  #(zero? (* (rem % 3) (rem % 5))) 
  (range 1000)))

;; => 233168

I will show the steps I took to get to this solution. When working with Clojure, I like to start from the inside and work my way out.

Let's start by defining a range (technically I guess we're not defining it, but whatever...):

(range 1000)

;; => (1 2 3 4 5 6 7 8 9 10 ... 997 998 999)

In this range, we want to only consider the numbers which are divisible by 3 and 5. To find those numbers, we can use the modulo operator. For instance, (mod 18 3) = 0 because 18/3 gives a remainder of zero. This means that 18 is divisible by 3, which means that 18 is a multiple of 3. To only keep those numbers which fulfill this criteria, we will use the filter function, which takes a functon and a collection of items and keeps any of those items which return true when put into the function. As usual, everything has to be written in prefix notation:

(filter
  (fn [x](or (= 0 (mod x 3)) (= 0 (mod x 5)))) 
  (range 1000))

;; => (0 3 5 6 9 10 12 15 18 20 ... 995 996 999)

Now we simply want to sum all these numbers together. To do this, we can use the reduce function, whose input parameters are a function and a collection of items. A reducer works by repeatedly evaluating the provided function with an accumulator and the next item in the collection of items. For instance, (reduce + (1 2 3 4)) means (+ (+ (+ 1 2) 3) 4). Implementing a reducer to our filtered collection of numbers yields:

(reduce + (filter
  (fn [x](or (= 0 (mod x 3)) (= 0 (mod x 5)))) 
  (range 1000)))

;; => 233168

At this point we've actually completed the task, but there are a few changes we can do. My colleague prefers to use zero? instead of = 0. In our case where we are simply summing all items in a collection, we could also use the apply function instead of the reduce function. After some googling, I'm still not sure whether this yields a performance improvement or not. Furthermore, we could use rem rather than mod. They're technically not the same if we're dealing with negative numbers, but we're only evaluating whether they return 0, so in our case they're equivalent. We can even save some space by not evaluating the two rem evaluations separately. Instead, we can evaluate the product of them. After all, if either of them is zero, the product of them will be zero. Implementing these changes, our function may look like this:

(apply + (filter
  (fn [x](zero? (* (rem x 3) (rem x 5)))) 
  (range 1000)))

;; => 233168

Did you think we were done now? We can make the code even shorter. In our reducer (which we replaced with apply), we defined (okay, I guess we didn't technically define it...) a function which simply returns an evaluation. There is really no reason to encapsulate this evaluation in a function, since the evaluation itself will evaluate to the same as the function. Still, the reducer has to recognize the evaluation as a function, so we can add a hashtag (#) in front of the evaluation to make it a function. Now we don't have to write any input parameters. They are implicitly given and can be accessed via the percent symbol (%). This change leaves us with this final piece of code:

(apply + (filter
  #(zero? (* (rem % 3) (rem % 5))) 
  (range 1000)))

;; => 233168

Did I say final? You might even write all the code in one line to be even more badass.

(apply + (filter #(zero? (* (rem % 3) (rem % 5))) (range 1000)))

;; => 233168

I hope this post taught you a lot of Clojure (even though I doubt it). It's just two days since I started this little learning project of mine and even though there is still a lot to learn, I already feel like I'm understanding some of the core principles of the language.

Happy 4. July to you American readers:)

Cheers!