Monday, 24 March 2008

Problem 1

This post tackles Problem 1 in the Project Euler Series.

As you would expect, Problem 1 won't tax our mathematical skills too far, but it does let us get stuck into the new features of C#3.0.

We're asked to find the sum of all multiples of 3 or 5 below one thousand.

I'd be tempted to dive straight in, and code up a for loop. But that's the old way of doing things. We want to be Functional. How about telling the compiler what we want, and letting it figure out how to get it?

I guess we want to start with all the numbers from 1 to 999, drop all those that aren't divisible by 3 or 5, and then add up the rest.

This is where the excitement begins. A lot of the power of the new Language INtegrated Query (LINQ) features in C#3.0 come from tools to work with sequences. We use sequences all the time: whenever we use foreach on an IEnumerable type, we're iterating through a sequence.

LINQ and its associated APIs allow us to process sequences of things, without there being a for, or an i or a j in sight.

Some of the APIs produce sequences for us. Enumerable.Range(int start, int count) for example will produce a sequence of consecutive integers beginning with start.

Other APIs take a sequence as an input, tweak it in some way, and return a new sequence. Such is the Enumerable.Where method. This takes a sequence, drops things that don't meet a certain condition, then returns a sequence containing everything else.

Here's how you might use this:

Enumerable.Range(1, 999).Where(x => x % 5 == 0 || x % 3 == 0)

This is doing the first part of what we need: taking all the integers less than 1000, and giving us a sequence containing only the ones divisible by 3 and 5.

There are two curious things about that piece of code. One is the way we are calling the Where method. Surely the Range method returns an IEnumerable? Since when did IEnumerable have a Where method? That's the magic of Extension methods, which we'll dig into another time. For now, its enough to know that the Enumerable class adds many useful methods, include Where, which you can call on any object that implements the IEnumerable generic interface. You just need to add a reference to the System.Linq namespace to your code, and the extension methods magically appear.

The other interesting thing is how we're specifying the condition to the Where method. What's up with the "=>" symbol? That tells the compiler that we are creating a Lambda expression. A lambda expresssion is just a little inline block of code that we can pass to another method. This expression just takes one argument x, and returns true or false depending on whether x is divisible by 5 or 3. Isn't the syntax elegant? No need for the return keyword, and no need to tell C# that x is an int or that the expression returns a bool. It works all that out for itself.

Now that it has the lambda expression, the Where method can take every item in its input sequence (the one that it's getting from Enumerable.Range), call the expression to see whether the item meets the condition, and if it does, pass it though to the output sequence.

So it looks like we're almost ready to give Euler his answer. Except that he asked for the sum of all these numbers. That's easy. Enumerable provides another extension method, Sum(), that will get that for us. We just tag it on the end of what we've got already:

static int SumMultiplesOfThreeAndFive()
{
    return Enumerable.Range(1, 999)
            .Where(x => x % 5 == 0 || x % 3 == 0)
            .Sum();
}
Sum just works its way through a sequence, adding up everything it encounters and returns the result.

And there you have it. A Functional solution, in one line of code (ignoring a few newline characters!) to Project Euler, Problem 1.

[Updated to correct a few typos on 24/3/2008]

[Updated to correct a few typos on 25/3/2008]

[Updated to correct solution in line with change to problem on 5/5/2008]

8 comments:

roman_fresneda said...

Sam

I thought this was the best way to give my humble opinion on your blog. I will keep sniffing on it later, but so far I think it's simply great.Being a "published author" was just a matter of luck, I bet that most of my *new team* could be in that category if just had the opportunity.

Nice you came across with the idea of showing the new functional aspects of C# in your blog, many people are still attached to what you called "old way to do things". IMHO, functional languages are a really neat thing since they show the intent of the programmer in a clear, concise way.

So, keep up the good work. It is an honor to come to Paragon, a dream come true.

Hope to be working hard soon

Roman

Stuart Hillary said...

Just spotted a typo. The && in the Where clause should be replaced by a ||.

Sam said...

Thank's Stu: I just noticed that on Saturday as well. I've got a feeling they've change the problem since I first posted the solution!

Lonnie VanZandt said...

Hmm, on my screen, the Where clause lambda expression is missing the logical operator entirely: no AND nor OR.

Sam said...

Lonnie,
I was hedging my bets!!

Thanks for pointing that out. Should be fixed (again!).

Sam

Anonymous said...

You should say this is not an efficient solution. It is effectively a brute force solution.
Mark

Link.fr said...

Hello,

Your solution with Linq is O(n). Linq would not do the job if the target number is very big (65000000000 for instance). The best approach would be to use inclusion exclusion principle in order the get O(1) algorithm :

static ulong SumDivisibleBy(ulong target, uint n)
{
   ulong p = target / n;
   return n * p * (p + 1) / 2;
}

ulong target = 999; // 65000000000
UInt64 s = SumDivisibleBy(target, 3) + SumDivisibleBy(target, 5) - SumDivisibleBy(target, 15);

Kind regards

William Blackburn said...

i like your blogs.  thanks for writing

Post a Comment