Factor Mystic

5Jul/102

Project Euler in F#: Problem 2

Problem 2

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, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The Thinking

The problem is similar to Problem 1, but this time instead of a natural number sequence, we're to use a fibbonacci sequence, evens only, less than 4 million. Then, we'll need to sum them up; that we did in Problem 1 with Seq.sum. How can we generate the sequence? I'll be taking a simple two-step approach. First, figure out a function to generate a fibbonacci sequence (up through 4,000,000), then take all the evens. We can Seq.sum that resulting sequence to find our answer.

Generating a Fibonacci Sequence

Generating a fibbonacci sequence in F# is a textboook case, and so much so that it's actually an example snippet for the built-in F# function we're going to use to generate it: Seq.unfold. Seq.unfold is a  function that returns a sequence, based on a function we provide. It takes two parameters: a sequence element generator function, and the inital value to start with.

Seq.unfold generator state

The generator function must be defined with a single input parameter (the "state value"), and returning an "option tuple of the next element in the sequence and the next state value" (from documentation).

A fibbonacci algorithm requires two inputs (the previous two digits), but we can only pass one parameter. Luckily in F# we have Tuples. A tuple lets us package up several values into a single group, and is written with as a comma separated list inside parenthesis:

let sometuple = ("this", "is", "a", "single", "tuple")

The return value is also something new, using the built-in Option module. We'll be returning an Option, either Some or None. None is a signal to unfold that this is the end of sequence, and for all the rest of the return results, we need to return Some-thing (the next element of the sequence as well as the next state value in tuple form) as we learned above, from the documentation for unfold.

This might seem like a lot to process all at once, but it ends up looking pretty simple when it's all put together. The generator function for fibbonacci numbers less than 4m looks like this:

let fibgen (x,y) = //define a function 'fibgen' and pass in a single parameter, a tuple that represents the most recent two digits of the fibbonacci sequence so far
if(x < 4000000) then // define a cut-off threshold to keep the sequence from going on forever
Some(x+y, (y, x+y)) // return an Option tuple; the next elemnet of the sequence: x+y (the two most recent elements added together), and the next state value- a single tuple that will be used next time the funciton is run
else None // we're up to 4m, so tell unfold we're done with the sequence

And now, we can plug that into Seq.unfold:

let fibseq = Seq.unfold fibgen (1,1) // (1,1) is a single tuple parameter with the initial values for the fibgen function

If we run this in the Interactive F# window in Visual Studio, we can confirm this produces the full fibbonacci sequence:

val it : seq = seq [2; 3; 5; 8; ...]

Getting Just The Evens

If you recall our solution to Problem 1, it should be easy to figure out how to make a new sequence with only the even values by using seq, modulo, and yield that we've already learned.

let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}

My Solution

Putting it all together, with Seq.sum to add up the sequence:

let fibgen (x,y) = if(x < 4000000) then Some(x+y, (y, x+y)) else None
let fibseq = Seq.unfold fibgen (1,1)
let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}
let result = Seq.sum fibevens
printfn "%A" result

Project Euler Problem 2: Answered

Further Reading

A Post Script

Each part of the above solution is named for clarity. We could easily compose these functions for a more compact solution:

printfn "%A" (Seq.sum(seq{for i in ((1,1) |> Seq.unfold(fun (x,y) -> if(x < 4000000) then Some(x+y, (y, x+y)) else None)) do if i % 2 = 0 then yield i}))

The only thing that gets weird in this compact version is the anonymous replacement for fibgen, which uses lambda syntax fun & ->, and the pipeline operator, |> to pass in the intial state. There are some goofy rules for when you can and cannot use piplineing; check out the Pipeline section of Chapter 8 of The F# Survival Guide for a good primer.

19Jun/101

Project Euler in F#: Problem 1

About Project Euler

I've wanted to take a crack at Project Euler for some time now. If you're not familiar, it's basically a list of mathematical problems. From the site:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

And they keep score! In addition, I've also been looking for an excuse to learn F#. In truth, I've wanted to get down and dirty with some functional language, to learn the principles and hopefully become a better programmer. I chose F# because it's part of Visual Studio (starting with 2010), and I'm already handy with .NET, so in theory that will lower the barrier to entry just a little bit. At the very least, it allows me to dodge the hassle of installing another interpreter or environment on my system.

Blogging It

As I continue though Project Euler, I'll be posting my solutions here on my site under http://factormystic.net/projects/code, and you can also check my progress by looking at my Project Euler profile and I look forward to your mocking laughter gentle guidance as I fumble around in F#.

On to Problem 1

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.

Straightforward enough, and easy to form a mental model around the problem. But how to implement this in F#? For a quick language primer, I skimmed An Introduction to Functional Programming for .NET Developers and noticed a few things I might need:

  • An add function
    let add x y = x + y
  • Sequence syntax and list comprehension
    let numbers = {0..10}
  • Modulo and ternary operators
    string result = x % 2 == 0 ? "yes" : "no";

The Thinking

The thinking is this: sequences could be used to build a list of integers 1 to 1000; I could use modulo to get multiples of 3 and 5 (think FizzBuzz), and somehow use that add function to get the sum. Reading the documentation for sequence expressions turned out to be quite rewarding (!), as you can embed a filter on a sequence when you declare it:

let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }

Yield is already a familiar concept from C#, from using Enumerables. In fact, from the documentation:

Sequences are represented by the seq<'T> type, which is an alias for IEnumerable<T>. Therefore, any .NET Framework type that implements System.IEnumerable can be used as a sequence. The Seq module provides support for manipulations involving sequences.

Thus our F# is roughly analogous to something like

public static IEnumerable GiveMults()
{
foreach (int i in Enumerable.Range(1, 1000))
if (i % 3 == 0 || i % 5 == 0)
yield return i;
}

Now that we have our sequence of natural numbers, let's figure out how to sum them up. I have the add function I grabbed from the article, and while poking around with the Seq module, I noticed a reduce function, which can apply an accumulator. That would give us

let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }
let add x y = x + y
let result= Seq.reduce add multiples
printfn "%A" result

(Side note: printfn is how we can write to stdout, much like Console.Writeline. The "%A" stuff works like string.Format parameters- %A indicates "Formats any value, printed with the default layout settings." In the case of a sequence, that means printing the first few values)

...and that code does indeed sum the multiples, as you would expect. But there is a better way. After all, we should expect something as simple as adding up a list to be built in already, and we do have our Seq module functions available.

Indeed, there is a Seq.sum function that does exactly what we're seeking to do, sum a sequence. Rewritten, we have:

let result = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }
let total = Seq.sum result
printfn "%A" total

And this prints an answer, but that answer is WRONG. See the bug? The original problem stated that we're to "sum of all the multiples of 3 or 5 below 1000", but the list comprehension syntax (1..1000) is inclusive. Thus, our answer includes 1000, which is evenly divisible by 5, and is summed into the final total. The fix is simple, just write 1..999:

My Solution

let multiples = seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }
let result = Seq.sum multiples
printfn "%A" result

Bingo.
Project Euler Problem 1: Answered

Further Reading

A Post Script

For the code golf crew:

printfn "%A" (Seq.sum (seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }))