November 25, 2014

Project Euler p. 2

The next one was a bit trickier to figure out, due to my inexperience with looping constructs in Clojure. The actual Fibonacci is quite simple, the problem description contain all the information you need:

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.

Following the simple rule we can get the “next” number by: (+ a b) where a and b are known terms of the sequence. In the problem description they start with 1 and 2, but often it is started with 0 and 1, giving 1, 1, 2 as the first 3 terms in the sequence. I will use 0 and 1 to start off my Fibonacci sequence.

Let’s make a quick function that given two terms will give us the next term in the sequence:

(defn next-fib
  [a b]
  (+ a b))

Nothing fancy going on here, it is just an alias to the + function, but it encodes our domain which makes the next function a bit easier to reason about:

(defn fib [n]
  "Takes a number 'n' which signifies the position in the
  fibonacci sequence to lookup"
  (loop [i 1
         a 0
         b 1]
    (if (> i n)
      a
      (recur (inc i) b (next-fib a b)))))

This still looks a bit odd to me, but Clojure lacks tail-rercursion optimizations due to lack for them in the JVM. This can be solved by calling recur as the tail, rather than the function name, so just imagine it being an alias for the function’s name, fib in this case.

Looking a bit closer at it, there are three steps, loop, if and recur. Let’s start at the top (mapping n to 1).

First up, a loop:

(loop [i 1
       a 0
       b 1])

This is essentially a while (true) loop from the C-family. The first argument (a vector), allows us to define a set of local variables for use in the loop. Here i is used as the iteration index, and a and b are for the first two positions in the Fibonacci sequence.

The first instruction in the loop is a call to the if special form. The if looks odd at first, when used to the C-family, but it works just as you would expect. if takes two or three arguments, a predicate, a then statement and an optional else.

(if :predicate
  :then
  :else)

What we are interested in, is simply to end the loop when we have computed the desired position in the Fibonacci sequence. Since n = 1 and i starts off as i = 1, we will only be looping once. And select the then branch.

We can see in the following code that the predicate is (> i n) which we determined should fire, thus giving us a, which has a value of 0.

(if (> i n)
  a
  (recur (inc i) b (next-fib a b)))

If we now decide that we want n = 3, we are going to have to loop a few times. Which leaves us with the then statement.

(recur (inc i) b (next-fib a b))

What recur does here is call, not the function fib but loop. This time incrementing the first argument, supplying b for the new a, and then uses our nifty next-fib function to calculate our new b value.

As such, after evaluating the sub-expressions we get:

(recur 2 1 1)

Which will feed into the loop as i=2 a=1 b=1. The next three recurs would thus be:

(recur 3 1 2)
(recur 4 2 3)
(recur 5 3 5)

Et voilà, we have a Fibonacci generator. Nice! Now on to solving the the problem. There are (at least) two very different ways to structure the following code;

(reduce + (filter even?
  (take-while
   #(< % 4000000)
   (map fib
        (range 100000000)))))

and

(->>
 (range 1000000000)
 (map fib)
 (take-while #(< % 4000000))
 (filter even?)
 (reduce +))

These two block do the same thing, in the same order, but we can use the clever macro ->> to rearrange the former code to be read as steps top to bottom, substituting the first expression as the second argument for the following row, rather than inside-out.

  1. Take a large set of numbers
  2. Use them with fib to generate a large sequence of Fibonacci numbers
  3. Only take the ones that are less than 4 million
  4. Select the ones that are even
  5. Sum the even fibonacci numbers to get the final answer.

Don’t let the large set of numbers (1000000000) scare you, Clojure is lazy, and will not actually calculate all of them before moving on. Once one Fibonacci number has hit 4 million, it will stop (more or less).

I went the ->> route on this one, partly because I wanted to try the syntax out, and because it is easier to read.

Here is the whole solution:

(ns euler.p02)

(defn next-fib
  [a b]
  (+ a b))

(defn fib [n]
  "Takes a number 'n' which signifies the position in the fibonacci
   sequence to lookup"
  (loop [i 1
         a 0
         b 1]
    (if (> i n)
      a
      (recur (inc i) b (next-fib a b)))))

(->>
 (range 1000000000)
 (map fib)
 (take-while #(< % 4000000))
 (filter even?)
 (reduce +))

© Sebastian Hörberg 2018

Powered by Hugo & Kiss.