So where was I? Ah, I was about to solve Project Euler Problem 2:
Problem 2
Even Fibonacci numbers
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.
In my previous Clojure post, I got to the point where I had a function, which, given a vector of Fibonacci numbers, could sum the two last numbers of the vector and extend the vector by this number.
Since the problem requires me to find all even numbers which do not exceed four million, I figured that it would be smart to make a function which would return an array of all Fibonacci numbers not exceding four million.
I did, however, not know how many Fibonacci numbers I would need to generate to pass four million. To generate new Fibonacci numbers until a certain condition was met, I would need a while loop.
At this point I did not know how to use while loops in Clojure, so instead of accepting the challenge, I took a slightly smaller first step: Creating a function which would return a vector of the n first Fibonacci numbers:
(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))
(defn fib-array [number]
(loop [vector [1 2]] ;; Why square brackets around arguments? That's just how it is.
(if (= (count vector) number)
vector
(recur (sum-end vector)))))
;;(println (fib-array 7)) => [1 2 3 5 8 13 21]
As you might see from my implementation, I did end up using a while loop after all. I had to ask a colleague at work about how to use while loops. Take a look at the code and see if you understand it.
Apparently, while loops take their arguments from within a set of square brackets. To me, this seemed to diverge from the otherwise consistent Clojure syntax. When I asked my colleague why the for loop needed square brackets around its arguments while regular functions don't, he said that that's just how it is. Also, note the recur function (it is a function, right?). It takes the result of the function given to it and sets the vector variable to have this value, even if we have not explicitly told it that it's the vector's value we're recurring over. Since vector is a parameter of the loop, it is implicitly given to functions within the loop, if that makes sense.
Realizing that I was solving this whole problem the hard way, I continued by implementing a function which would find the index of the highest Fibonacci number not exceeding four million. In hindsight, I realize that now that I knew how to write for loops, I could simply generate a vector of Fibonacci numbers by extending it until the last element exceeded four million, then remove the last element, filter away the odd numbers and take the sum of all the elements in the vector and the problem would be solved.
Well, just in case you were curious, I have included the function which finds the index of the highest Fibonacci number below a certain number:
(defn index-of-highest-fib-below [number]
(- (loop [index 2]
(if (> (last (fib-array index)) number)
index
(recur (inc index))
)
) 1)
)
(println (index-of-highest-fib-below 7)) ;; ==> 4
As you can probably tell, this implementation is a bit inefficient, since it recalculates every previous Fibonacci number every time the vector is extended by one. At this point you might have realized that this blog series is not about teaching you how to write Clojure, but rather a description of my experience with the language and the challenges it brings to my JavaScript-oriented mind.
Maybe we should solve the actual Project Euler problem now?
Let's do it!
First, we make a function which lists all the Fibonacci numbers not exceeding a certain number:
(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))
(defn fib-array-lower-than [number]
(butlast
(loop [vector [1 2]]
(if (> (last vector) number)
vector
(recur (sum-end vector)))))
)
(println (fib-array-lower-than 8)) ;; => (1 2 3 5 8)
Next, we filter away all the numbers which are odd:
(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))
(defn even-fib-array-lower-than [number]
(filter #(zero? (rem % 2))
(butlast
(loop [vector [1 2]]
(if (> (last vector) number)
vector
(recur (sum-end vector)))))
)
)
(println (even-fib-array-lower-than 34)) ;; => (2 8 34)
Lastly, we set the input parameter to 4 000 000 and sum all the elements.
(defn sum-end [vector] (conj vector (+ (last vector) (last (butlast vector)))))
(defn sum-of-even-fib-array-lower-than [number]
(apply +
(filter #(zero? (rem % 2))
(butlast
(loop [vector [1 2]]
(if (> (last vector) number)
vector
(recur (sum-end vector))))
)
)
)
)
;; Project Euler 02
(println (sum-of-even-fib-array-lower-than 4000000)) ;; => 4613732
So there you have it. The answer to Project Euler Problem 2 is 4613732. I don't know if my Clojure follows typical Clojure best practices, but it did work and it's just slightly readable, and at the end of the day, that's what Clojure's all about.