Solving Project Euler problem 2 in Clojure

Here’s a Clojure solution to problem 2 from Project Euler (use tag euler to see solutions to some of the other problems):

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

; Problem:
; Each new term in the Fibonacci sequence is generated by adding the previous two terms. 
; By starting with 1 and 2, the first 10 terms will be:
;
; 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
;
; By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
; find the sum of the even-valued terms.

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

(defn fibs 
  ([] (fibs 1 2))
  ([a b] (lazy-seq (cons a (fibs b (+ a b))))))

(deftest fibs-test
  (is (= (take 10 (fibs)) '(1 2 3 5 8 13 21 34 55 89))))

(run-tests)

(defn solution []
  (println (reduce + (filter #(= 0 (mod % 2)) (take-while (partial > 4e6) (fibs))))))
(solution)

Let’s dissect the main points there. First, the test

(deftest fibs-test
  (is (= (take 10 (fibs)) '(1 2 3 5 8 13 21 34 55 89))))

(run-tests)

This is the test as outlined in the problem. The above just takes first 10 elements of sequence generated by fibs function and compares to the expected result.

fibs function looks like this:

(defn fibs 
  ([] (fibs 1 2))
  ([a b] (lazy-seq (cons a (fibs b (+ a b))))))

There are two very important features of Clojure in play here:

  • Destructuring, a very good explanation here
  • Lazy sequences, excellent answer from mikera

Destructuring in the above case is used in a way you would use default parameters in some languages. The above just says:

  • When no arguments are passed, run (fibs 1 2), essentially defaulting the parameters to 1 and 2
  ([] (fibs 1 2))
  • For all other cases (including the one from above – the default parameters case), expect two parameters a and b and run this:
  ([a b] (lazy-seq (cons a (fibs b (+ a b))))))
  • Note that you are allowed to call fibs only in the above two cases – running it in any different way – e.g. (fibs 1 2 3) will result in an exception such as:
Wrong number of args (3) passed to: problem2$fibs
  [Thrown class java.lang.IllegalArgumentException]

Lazy sequences are a powerful abstraction. This is not new to Clojure – e.g. Haskell is a programming language that is lazy by default. However, Clojure being a JVM language offers something new in that area.

The idea behind the lazy sequence is to do two things – evaluate only when the result is actually needed and cache the result for future invocations. Caching is enabled by Clojure’s immutability by default – in general, Clojure data structures are immutable.

In our case:

  ([a b] (lazy-seq (cons a (fibs b (+ a b))))))

What happens is that when fibs is called with two arguments, a lazy sequence is returned and no evaluation of it’s inner parts – i.e. the following part:

(cons a (fibs b (+ a b)))

occurs at this time. The evaluation is triggered whenever fibs is called. For example, we can do something like this in REPL:

user> (ns com.icyrock.clojure.euler.problem2)
com.icyrock.clojure.euler.problem2> (take 5 (fibs))
(1 2 3 5 8)

What happens here is that take function actually asks fibs to produce results. At this point, lazy-seq’s inner part is called and, replacing the starting parameters, we get this:

(cons 1 (fibs 2 (+ 1 2)))

What we get is a cons. When you say:

(cons a bs)

you basically have a two-cell data structure. The first cell contains a and the second cell contains bs. Note that bs is a sequence – in other Lisps, this was usually denoted by adding an “s” to the name, to make it look like a plural form of “b”. This is the basis for a list – a list is a list of cons. As an example:

(list 1 2 3 4)

is logically much the same as:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

taking into account that nil is the same as the empty list or ‘().

To return to our example:

(cons 1 (fibs 2 (+ 1 2)))

gives us a cons of 1 and (fibs 2 (+ 1 2)). Given the previous discussion, you can look at this as a list which has elements 1 and then all elements of (fibs 2 (+ 1 2)), whatever they are. Note, however, one important thing here – fibs will again return a lazy sequence. So, if you only wanted the first element of the list – e.g.

com.icyrock.clojure.euler.problem2> (take 1 (fibs))
(1)

this is all that would be evaluated. The next call to fibs – (fibs 2 (+ 1 2)) would not occur at this time.

Now, we did take of 5, so we are going to need more elements. And what are they? Well, the call is (fibs 2 (+ 1 2)) which is the same as (fibs 2 3) after the sum is calculated. Expanding that in the same way we get:

(cons 2 (fibs 3 (+ 2 3)))

So our list is basically 1, 2 and then whatever (fibs 3 (+ 2 3)) returns. And so on until we figure out the first 5 elements. After that, we would be left with a lazy sequence as the second part of our last cons which would not be evaluated.

There are two huge benefits here. First, it’s obvious that we evaluate only what we need, so we don’t waste either time or memory (and possibly other resources) evaluating unnecessary parts of the sequence.

Even more important is the fact that we have an infinite list. fibs can go on and on and will never finish, but being lazy allows us to handle that.

At the end, we do what we really need to arrive at the result we are looking for:

(defn solution []
  (println (reduce + (filter #(= 0 (mod % 2)) (take-while (partial > 4e6) (fibs))))))
(solution)

A lot of nesting here – let’s break this one down inside-out:

  • Calling:
(fibs)

will lazily generate all Fibonacci numbers

  • Let’s first examine:
(partial > 4e6)

What this does is make a function that when passed an argument returns whether 4e6 is greater then the argument passed in. This is the same as:

#(> 4e6 %)
  • This part:
(take-while (partial > 4e6) (fibs))

is a simple and powerful concept for filtering lists.

  • What it does is following:
    • Take the input sequence (let’s call it I) – whatever (fibs) returns, and it’s Fibonacci list in this case
    • Start generating a new sequence (let’s call it S) from the beginning of the sequence
    • S is generated by adding the members of I one by one while the given function is true
    • Function in this case is (partial > 4e6), so what we essentially achieve here is generate a sequence of numbers not greater then 4 million, as per the problem requirement. Let’s call this list L4 going forward
  • In the next step we have
(filter #(= 0 (mod % 2)) L4)
  • What filter does is:
    • Go through the given list – L4 in this case and return a list of the elements that satisfy the given function
    • The function in this case is #(= 0 (mod % 2)), which basically gives us elements that are evenly (with no remainder) divisible by 2
    • Let’s call this list L2
  • The next part:
(reduce + L2) 

is again a nice function

  • What it does:
    • Let’s assume we have a list l = (a1, a2, a3, a4, a5, …, aN)
    • What (reduce f l) basically does is this:
      • r1 = (f a1 a2)
      • r2 = (f r1 a3)
      • r3 = (f r2 a4)
      • rN-1 = (f rN-2 aN)
      • rN-1 is the result returned by (reduce f l)
    • In our case, what it would do is basically apply a sum (+) function to the list, effectively giving us a sum of the numbers in the list

Finally, we print the result and that’s what we use to solve the problem.


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.