Recently I’ve been doing some Project Euler problems as exercises to help improve my coding skills. We do this internally at NimblePros periodically and also at last weeks Hudson Software Craftsmanship meeting, which I co-run. In doing these problems, I’ve been trying to approach them both from a traditional C# 1.0 standpoint as well as using newer constructs such as lambda expressions, LINQ, and iterators. It’s amazing how much more flexible a design can be through the use of these tools.
For example, the first Euler problem simply asks that you add together all natural numbers that are multiples of either 3 or 5 and less than 1000. A simple design of this problem might be to write a for() loop that runs from 1 to 999 (< 1000) and checks if the current number MOD 3 or MOD 5 equals 0, and if so, add it to the sum. Pretty straightforward, but it comingles several concerns.
What are the moving parts in the problem?
- Generating a List of Numbers to Check
- Checking If A Number Is a Multiple of 3 or 5
- Summing Numbers Together
When you move on to the second Euler problem, which wants the sum of all even-valued terms in the Fibonacci sequence less than or equal to 4,000,000, you end up writing a lot more code if you didn’t separate out the initial concerns.
Let’s look at the first moving part, generating numbers. An iterator provides a useful solution here:
Now you can use this with various LINQ expressions to generate sets of numbers. Here’s a simple test showing how to get 10 numbers with this iterator.
Next you want to be able to check for various things. For example, the first problem wants only numbers that are multiples of 3 or 5, while the second problem wants numbers that are even (multiples of 2). Assuming you’ve pulled the modulo logic into a simple extension method like IsMultipleOf(x) you can use LINQ again to generate only numbers of a particular kind:
Of course, for common expressions like even numbers, you don’t want to repeat the logic throughout your code, so once you see that you’re using things like IsMultipleOf(2) in more than a few places, you can easily create a new Generator that only generates even numbers:
More complex expressions can be stored separately using Func, which can be an extremely powerful way to follow OCP by allowing you to pass in criteria to an operation, rather than explicitly encoding it within a method. For example, here’s the Problem 1 criteria expressed as a Func<long,bool>:
Using this expression without LINQ (using standard loops and such), you can encapsulate the logic of summing numbers in its own class while keeping the criteria separate, like so:
Alternately, with LINQ and the NumberGenerator already shown, the expression can be evaluated like this instead:
The real value of this as you move through one Euler problem and go to solve another one is that you can do so by building on what you’ve already written, but without cutting and pasting it. You get real code reuse, not cut-and-paste reuse. One of the fundamental principles of the Open-Closed Principle is that new functionality is achieved by writing new code, not by changing existing code.
Look at how easy it is to do problem 2 once the components have been well-factored using the techniques shown above:
Since I’m not trying to spoil anyone’s fun solving these problems, I’ll leave actually writing the IsFib method to the reader, but my point is that using these techniques can really result in much less code which is far more expressive and reusable. And if you make IsFib() an extension method, you can rewrite problem 2 as just one line like this:
I’m really digging LINQ and expressions these days! When you get to Problem 3, which deals with primes, all you need to do to get started is generate a series of primes like this: