Project Euler Exercise 1

Ok, so this is the first of what I hope to be a whole series of blogs about my attempts at each of the Project Euler exercises. I’m doing them all in C# – the main thing I’m trying to get from doing these exercises is more TDD practise.

Project Euler Exercise 1 is stated as:

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.

Take 1 – Iterator / Visitor Pattern

I decided to use something approximating a Visitor / Iterator pattern – this was a pattern I saw on JP Boodhoo’s Nothin’ But .NET course recently.

I started off with an AggregatorTests class. I wrote an integration test to begin with, to know when the different components to be developed were working together to give the answer in the worked example in the problem, i.e. 3 + 5 + 6 + 9 = 23. The first draft of these tests contained something similar to the following:

var iterator = new Iterator(0, 10, isMultipleOf3Or5);

So I initially realised my Iterator should be given a minimum number, a maximum number, and some injected algorithm to determine if any given number within that range should be outputted in the resultset – this algorithm is represented by a generic predicate isMultipleOf3Or5:

private Predicate<int> isMultipleOf3Or5 = i => i % 3 == 0 || i % 5 == 0;

My iterator class also originally had an IEnumerable<int> GetValues() method. This method then yield-returned all the matching values in the range to the Aggregator, which then totalled them up. So the iterator was responsible for getting the sequence of matching numbers, and the aggregator added them all up. These 2 classes maintained these 2 responsibilities throughout all refactorings, even though the signatures changed.

So then I saw some opportunities for reuse, refactoring to make my iterator generic, so that it could handle more than just integers. Notice the extra lambda expression at the end of the Iterator constructor:

private Predicate<int> isMultipleOf3Or5 = i => i % 3 == 0 || i % 5 == 0;

[Test]
[Category("Integration")]
public void TheSumOfAllMultiplesOf3Or5Below10Equals23() // i.e. 3 + 5 + 6 + 9 = 23.
{
var iterator = new Iterator<int>(0, 10, isMultipleOf3Or5, i => i + 1);
var aggregator = new Aggregator(iterator);

int result = aggregator.GetSum();
Assert.That(result, Is.EqualTo(23));
}

What you see above is now the result of various refactorings. The Iterator class is now generic, and while more “reusable”, i.e. I can instantiate an Iterator of different generic types, everything has got a bit more complicated. We’ve got what I believe now is quite an unintuitive not-very-readable lambda expression at the end of the Iterator constructor which lets the generic Iterator know how to advance on to the next value in the range to check. I also got rid of the IEnumerable<int> GetValues() method as it didn’t quite fit in with my Visitor pattern. It would probably help at this point to show the generic Iterator class:

public class Iterator<DataType> : IIterator<DataType> where DataType : IComparable
	{
		private readonly DataType min;
		private readonly DataType max;
		private readonly Predicate<DataType> isMatch;
		private readonly Func<DataType, DataType> advanceToNext;

		/// <summary>
		/// Initializes a new instance of the <see cref="Iterator&lt;DataType&gt;"/> class.
		/// </summary>
		/// <param name="min">The inclusive minimum.</param>
		/// <param name="max">The exclusive maximum.</param>
		/// <param name="isMatch">The criteria to include the currently examined element in the result set.</param>
		/// <param name="advanceToNext">How to advance to the next element in the sequence from the current element.</param>
		public Iterator(DataType min, DataType max, Predicate<DataType> isMatch, Func<DataType, DataType> advanceToNext)
		{
			this.min = min;
			this.max = max;
			this.isMatch = isMatch;
			this.advanceToNext = advanceToNext;
		}

		public void Visit(Action<DataType> visit)
		{
			var current = min;
			while (current.CompareTo(max) < 0)
			{
				if (isMatch(current))
				{
					visit(current);
				}
				var next = advanceToNext(current);
				if (next.CompareTo(current) <= 0)
				{
					throw new ArgumentException("Invalid incrementing function - next value is less than or equal to the current value, and so will never reach maximum value.");
				}
				current = next;
			}
		}
	}

So the Iterator class needs the advanceToNext delegate, as, being generic, we can’t just add 1 to move on to the next value to be compared – we’re not necessarily dealing with integers in this Iterator any more. On top of that, if we’re going to be passed in the algorithm for moving from minimum towards maximum, we need to verify the algorithm does indeed move the while loop towards completion, so that we don’t end up in an infinite loop.

And the Aggregator’s GetSum() method is now as follows:

public int GetSum()
{
	var total = 0;
	iterator.Visit(i => total += i);
	return total;
}

So, when I started writing this blog post, I realised that I had fallen into one of the traps that many developers frequently do – I was anticipating how we might want to use this component in a different context later – hence the Iterator class being generic – note that there’s nothing in the Project Euler exercise that says anything about using anything other than integers.This code kata has reminded me of one of the many suggestions made at JP’s course:

Ask “What now”? Don’t ask “What if?”

In other words, don’t try to anticipate all possible scenarios that a particular class could be useful in – having instinctively done that above, I believe the end result is code that is more complicated than it needs to be, with advanceToNext algorithms having to be injected into the Iterator constructor, making the class less encapsulated.

Take 2 – The Visitor has outstayed his Welcome

Sorry – I couldn’t resist that pun! So while I fully intended to use TDD for this exercise, I also had also decided before I started that I was going to use a Visitor / Iterator pattern. So what I failed to do was let the tests drive out the design. After making this realisation, I went back and did the kata again – see Take2 folder versus Take1 in the Code Kata solution. I’m pleased to say that this time, I succeeded in sticking to a TDD approach, writing the tests first, and then filling in the code to make the tests pass. Even more encouraging for me though, is that I did this second take in a small fraction of the time that the first take took – of course having done it once already, it would make sense that the second time would be quicker, but I believe that my sticking to the brief, and allowing the tests to drive out the design, resulted in a big productivity gain.

So, in this second take, I started off writing a test:

[Test]
[Category("Integration")]
public void AddingAllMultiplesOf3Or5ThatAreLessThan10AddsUpTo23()
{
	var iterator = new Iterator(0, 10, i => i % 3 == 0 || i % 5 == 0);
	var aggregator = new Aggregator(iterator);
	int result = aggregator.GetSum();

	Assert.That(result, Is.EqualTo(23));
}

I wrote this test from the bottom up – I wrote the assertion first, then defined and initialised the result from the aggregator.GetSum(). And then, I had to instantiate a new Aggregator, passing in the iterator, and from there, I initialised the Iterator. By writing the test from the assertion first, I’m essentially doing a top-down design. This is what I mean by letting the test drive out the design.

Now, this is an integration test – as we’ve got an Iterator and Aggregator class working together. To get this test to pass, the functionality of each of these classes needs to be complete. So we’ll put this one test to the side for the minute – so far, at least, it’s helped drive out the signature of the Aggregator.

So I wrote a unit test next, as opposed to an integration test. Being a properly isolated unit test, I could write it, then follow it up with the small amount of functionality that would make it pass.

[Test]
public void AggregatorCanSumAllValuesReturnedFromIterator()
{
	var iterator = MockRepository.GenerateStub<IIterator>();
	iterator.Stub(it => it.GetValues()).Return(new[] { 3, 5, 6, 9 });

	var aggregator = new Aggregator(iterator);
	int result = aggregator.GetSum();

	Assert.That(result, Is.EqualTo(23));
}

The only real difference between this test and the previous one is that I’m mocking out the IIterator dependency in this unit test. In mocking it out, I added the GetValues() signature to the IIterator, and said that for this particular test, the dynamically generator mocked iterator should return a list of numbers – 3, 5, 6 and 9. This allows me to maintain my focus on the Aggregator’s functionality. Getting this test to pass was as simple as adding the following to the Aggregator class:

public int GetSum()
{
	return iterator.GetValues().Sum();
}

With the Aggregator functionality complete, I switched my focus to the Iterator class. I wrote a number of tests around this class, the main one being:

[Test]
public void ValuesReturnedContainsAllValuesWithinRangeThatMatchCriteria()
{
	var iterator = new Iterator(0, 10, i => i % 3 == 0 || i % 5 == 0);
	Assert.That(iterator.GetValues().Contains(3));
	Assert.That(iterator.GetValues().Contains(5));
	Assert.That(iterator.GetValues().Contains(6));
	Assert.That(iterator.GetValues().Contains(9));
}

The Iterator code to make that test was as follows:

public class Iterator : IIterator
{
	private readonly int inclusiveMinimum;
	private readonly int exclusiveMaximum;
	private readonly Predicate<int> isMatch;

	public Iterator(int inclusiveMinimum, int exclusiveMaximum, Predicate<int> isMatch)
	{
		this.inclusiveMinimum = inclusiveMinimum;
		this.exclusiveMaximum = exclusiveMaximum;
		this.isMatch = isMatch;
	}

	public IEnumerable<int> GetValues()
	{
		int current = inclusiveMinimum;
		while(current < exclusiveMaximum)
		{
			if(isMatch(current))
			{
				yield return current;
			}
			current++;
		}
	}
}

All that was left to do was add the test to add all the multiples of 3 and 5 less than a thousand:

[Test]
[Category("Integration")]
public void AddAllMultiplesOf3Or5ThatAreLessThan1000AddsUpTo233168()
{
	var iterator = new Iterator(0, 1000, i => i % 3 == 0 || i % 5 == 0);
	var aggregator = new Aggregator(iterator);
	int result = aggregator.GetSum();

	Assert.That(result, Is.EqualTo(233168)); // see Verification.xls for confirmation of this result.
}

Conclusion

Hopefully you’ll agree with me that the second attempt was a lot more straightforward than the first attempt. I believe this was in large part due to my sticking to TDD, only writing the functionality that the tests demanded. My old habits are hard to break! Sticking rigidly to TDD in the second attempt meant that I had to let go of my notion of using the Iterator / Visitor pattern – let the tests drive out the design.

Wow – that post was a LOT longer than I intended! It’s taken an age to write, so I might need to cut it down for future posts. All code for this post can be found here. Let me know what you think!

Advertisements

2 responses to “Project Euler Exercise 1

  1. Hey Ronan, thank you for sharing. Keep on posting and try to keep the rhythm of your katas (I lost mine a little, so this post reminds to get back on track).

    Greetings.

  2. Very thorough examination of your approaches. It’s very valuable for readers like me to see your thinking as well as your code.

    Please keep this up – we’re waiting for more insight into how TDD makes us more efficient/productive, and how to write true unit tests (not integration tests).

    Thank you!

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