Project Euler Exercise 2

I need to start spending more time reading requirements!

Project Euler Exercise 2 is stated as follows:

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.

My first 2 implementations of this completely missed the “even-valued” aspect of this task – I just added up everything in the sequence. Let’s move swiftly on from that! After having re-read the problem, I started again and wrote the following test:

[Test]
public void CanGetTotalOfAllEvenNumbersInFibonacciSequenceUpToAndIncluding4Million()
{
	var fibonacci = new FibonacciSequence(4000001);
	var result = fibonacci.GetValues().Where(i => i % 2 == 0).Sum();
	Assert.That(result, Is.EqualTo(4613732));
}


As you can see from the above test, the filtering of only even numbers, and summing results is being done inline in the test using Linq. The summing and filtering seemed that trivial that I didn’t see the benefit of creating classes specifically for them. So the only other aspect of the exercise is determining values of the Fibonacci sequence:

public class FibonacciSequence
{
	private readonly int inclusiveMax;

	public FibonacciSequence(int inclusiveMax)
	{
		this.inclusiveMax = inclusiveMax;
	}

	public IEnumerable<int> GetValues()
	{
		var sequence = new List<int> { 1, 2 };
		var finished = false;
		while (!finished)
		{
			int nextValueToAddToList = sequence[sequence.Count - 1] + sequence[sequence.Count - 2];
			if (nextValueToAddToList <= inclusiveMax)
			{
				sequence.Add(nextValueToAddToList);
			}
			else
			{
				finished = true;
			}
		}
		return sequence;
	}
}

So I initialise the list with the first 2 numbers of the sequence, and then keep iterating, summing the last 2 elements of the list to determine the next element to add. If the value that I’m about to add to the sequence is above the maximum value, it bails out.

I haven’t learnt a lot from this exercise up to this point, except that TDD won’t help you if you haven’t read the requirements right!

Job done then?

So, that’s all there was to it. I was going to leave it at that, and then I remembered an interesting exercise we did in JP Boodhoo’s Nothin’ But .NET course recently. A lot of us use the various Linq extensions without necessarily thinking too much how they might work under the hood. So we recreated some of these extensions. So, doing so here, let’s consider the test I wrote above. Specifically, look at the following:

var result = fibonacci.GetValues().Where(i => i % 2 == 0).Sum();

I changed this test class to remove the System.Linq using statement, and proceeded to develop new extensions and delegates to match this Linq syntax with my own custom classes.

Let’s look first at the Where clause. From above, we can see that given an IEnumerable of a certain generic type, and a filter clause supplied as a lambda expression, it will return a filtered list of IEnumerable of the same generic type. We could write the signature as follows:

public static IEnumerable<T> Where<T>(this IEnumerable<T> unfilteredList, Predicate<T> filter)

Creating the Where Clause with A Custom Filter instead of the Generic Predicate

The first parameter above, of type IEnumerable, is the type that we’re extending with the Where method. The second parameter of Predicate allows a lambda expression that takes a parameter of that generic type and returns a bool. The generic Predicate is a delegate that allows a caller to filter on any type. Delegates are something that I’ve generally been happy to use, but have never really thought to create, for no other reason than I wasn’t that familiar with them. So, fighting that urge here, I created my own generic delegate equivalent to the Predicate – I called it a Filter.

public delegate bool Filter<in TypeToConsiderFiltering>(TypeToConsiderFiltering objectToCheck);

Having created that, let’s slightly alter the above Where extension method signature to use it, instead of the Predicate:

public static IEnumerable<T> Where<T>(this IEnumerable<T> unfilteredList, Filter<T> filter)

This revised signature can then be called in exactly the same manner as if we used the Predicate.

So here’s the Where extension in full:

public static class EnumerableExtensions
{
	public static IEnumerable<T> Where<T>(this IEnumerable<T> unfilteredList, Filter<T> filter)
	{
		foreach (var item in unfilteredList)
		{
			if (filter(item))
			{
				yield return item;
			}
		}
	}
}

So, in my test, I have an IEnumerable<int>, which means the generic parameter T in the Where method represents an int in this test case, and my filter parameter represents a method that can take an int and return a bool, as done in the if statement in this Where method. That method is written as an inline lambda expression in our test:

.Where(i => i % 2 == 0)

Creating the Sum Extension

So, with the Where clause returning a filtered IEnumerable <int>, next I needed to create the Sum() extension. This doesn’t take any parameters except the instance being extended, and returns an int, representing the total of all elements in the IEnumerable being extended.

public static int Sum(this IEnumerable<int> list)
{
	var total = 0;
	foreach (var item in list)
	{
		total += item;
	}
	return total;
}

Just iterate through all the elements in the list and add them up.

Summary

So, due to the fairly straightforward nature of this exercise, the main focus of this post has been creating custom generic delegates and extension methods to mimic the behaviour of common delegates and Linq methods. I see no reason to define your own Where or Sum extensions in practice – this was more an exercise to show you how this syntax could be achieved. Similarly, I’d probably favour the Predicate in practice as well over my custom Filter, as other developers looking at my code could potentially instantly recognise the out-of-the-box Predicate. Hope you found it useful.

As before, all code is available from my github code katas repository.

Advertisements

2 responses to “Project Euler Exercise 2

  1. I think your inclusiveMax, combined with a test value of 4000001 will exceed the specified maximum of four million.

    Also, I personally have issues with the “i % 2 == 0” pattern for testing even numbers. I’d rather use an extension method “i.IsEven()” because it’s quicker for me to mentally compute when debugging. With the former I have to mentally determine what the result and comparison are before I understand that evenness is being tested. With the latter extension method it’s a no brainer.

    Maybe I’m just lazy, or I’m humble enough to assume that the brilliant minds that made Linq are going to do a far better job of sum() than I would, so I lean on the framework as much as I can. (“The best code you write is the code you don’t write.” and all that.)

  2. Well done in spotting the “deliberate mistake” :-). I switched between exclusiveMax and inclusiveMax, and missed updating the arguments. If 4,000,000 was a fibonacci number, it would have affected the result of the test.

    I like the isEven() integer extension – I’ll probably make that change alright – as discussed offline, .Where(number.IsEven()) has a lot more instant meaning attached than .Where(i => i % 2 == 0).

    As far as using Linq goes, I’m completely with you on that – I like that quote about the code you don’t write. I think it makes sense to know how to allow your components to use this Linq-style syntax though, whether it’s as extension methods over 3rd party components, or just adding to your own classes. If something’s there in the framework already, I’d find it difficult to justify creating my own.

    Thanks for your comments, Bernhard – keep ’em coming!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s