How to Solve Project Euler #2 in Kotlin
Today we’re going to solve Project Euler Problem 2 in Kotlin. If you’re missing background on Project Euler and why I’m working through its problem set, take a look at Project Euler #1.
Here’s our problem statement for today:
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.
To solve this problem, we’re going to combine Kotlin’s Sequences with Kotlin’s Tuple Types
Because we need two values to seed our sequence generation instead of one, we’ll need a way to pass two values as the seed argument to generateSequence. Now we could easily declare a data class that encapsulates the two values, but for situations like this it seems like overkill. Fortunately the designers of the Kotlin standard library agreed and added two such types for convenience: Pair and Triple. These types encapsulate two and three values (of any type!), respectively.
Now we can pass the argument Pair(0, 1) to generateSequence!
Our function to generate the next value looks a little tricky, so let’s break it down. We’re returning Pair(it.second, it.first + it.second). Why does this work? Well, we know that the first two values in the Fibonacci sequence are 0 and 1. This means that the second Pair in our sequence is Pair(1, 1). Continuing we find:
Pair(1, 2)
Pair(2, 3)
Pair(3, 5)
…
Comparing this sequence of pairs to the Fibonacci sequence described above, we can see that we are accumulating the entire sequence in the first value of each Pair!
The reset of the computation falls out nicely:
We map each Pair to its first value.
Next, we takeWhile the value is less than our upperBound.
Then, we filter to only even numbers using it % 2 == 0. (For the uninitiated, % is the modulus operator!)
And finally, we take the sum.
Running our program tells us the answer: 4613732.
To learn more about Kotlin Tuples, take a look at Pair and Triple in the Kotlin documentation.
To see the code for this essay, take a look at its Atomic Repo at https://atomicrepos.dev/repos/project-euler-2-kotlin/.
