Project Euler Exercise 4

Ok – so I decided to skip blogging about exercise 3 – you can find it on my github account though. I’m trying to spend about 20 minutes a day doing these code katas, but I only have time to blog about once a week, so I’ll typically stick to blogging about the most recent / interesting one.

So I’m going to focus on my second attempt at exercise 4. I’m happy to say that this was “pure TDD”, in that I wrote the test not having any idea how I was going to implement it! I focussed purely on the design and how I wanted it to look to consumers of these components. I decided I’d try a Fluent Interface style – and I’m pretty happy with the result! So the first test I wrote is as follows:

[Test]
public void CanFindMaximumPalindromeUsingFluentSyntax()
{
	var result = Find.Maximum(number => number.IsPalindrome()).ThatIsProductOf.TwoNumbersEachLessThanOrEqualTo(99);
	Assert.That(result, Is.EqualTo(9009));
}


So the idea of the Fluent Interface is that it reads pretty much like a sentence – “Find the maximum number that is a palindrome that’s a product of 2 numbers each less than or equal to 99”.

The Find Class – A Static Gateway

So the means by which you start with this fluent syntax is through the Find class. The code for it is as follows:

public static class Find
{
	public static MaximumMatchingCriteria Maximum(Predicate<int> isMatch)
	{
		return new MaximumMatchingCriteria(isMatch);
	}
}

You can see this class has one static function, Maximum, which takes a Predicate<int> and returns a MaximumMatchingCriteria. The predicate is just passed straight through to the MaximumMatchingCriteria’s constructor. This way, I can defer what happens with the “number => number.IsPalindrome()” argument in the test until later on, when we’ve got the list of numbers we want to work on. So this class doesn’t really do anything more than facilitate this syntax style. The MaximumMatchingCriteria is then passed back to allow us to continue with the rest of the “sentence”.

Getting the Maximum number from a list – MaximumMatchingCriteria

Next then, we’ll have a look at the MaximumMatchingCriteria:

public class MaximumMatchingCriteria
{
	private readonly Predicate<int> isMatch;

	public MaximumMatchingCriteria(Predicate<int> isMatch)
	{
		this.isMatch = isMatch;
	}

	public ProductSequenceGenerator ThatIsProductOf
	{
		get { return new ProductSequenceGenerator(isMatch, list => list.Max()); }
	}

}

So we have the constructor, that in our test case, is storing the “number => number.IsPalindrome()” lambda expression in the isMatch field, and the ThatIsProductOf property. This property is quite similar to the Find.Maximum function in that it just passes the isMatch parameter on to the constructor of the next class, and returns that next class, in this case the ProductSequenceGenerator class. But it does a little more than that as well, in that it also passes on a lambda expression in the constructor to determine what to do given a list of integers – i.e. find the maximum integer from this list of integers.

Getting all Permutations of 1..99 * 1..99 and Calculating the Final Result

Next, the ProductSequenceGenerator:

public class ProductSequenceGenerator
{
	private readonly Predicate<int> isMatch;
	private readonly Func<IEnumerable<int>, int> aggregator;

	public ProductSequenceGenerator(Predicate<int> isMatch, Func<IEnumerable<int>, int> aggregator)
	{
		this.isMatch = isMatch;
		this.aggregator = aggregator;
	}

	public int TwoNumbersEachLessThanOrEqualTo(int inclusiveMax)
	{
		var matches = new List<int>();
		for (int i = 1; i <= inclusiveMax; i++)
		{
			for (int j = 1; j <= inclusiveMax; j++)
			{
				var product = i*j;
				if (isMatch(product))
				{
					matches.Add(product);
				}
			}
		}
		return aggregator(matches);
	}
}

So, focusing on the TwoNumbersEachLessThanOrEqualTo function, we take the inclusiveMax, i.e. 99 in our test case, and look at each permutation of every number less than or equal to 99 being multiplied by every other number less than or equal to 99. If it’s a match, i.e. a palindrome in our case, add it to a list of matching numbers. Then call the aggregator function with the list of numbers, i.e. palindromes, and return whatever number that aggregator returns, i.e. the maximum number from the list.

And that’s all that there is to the Fluent Interface.

Checking if a number is a Palindrome

All that’s left to see is how the palindrome bit works. I wrote an Int32 extension:

public static class Int32Extensions
{
	public static bool IsPalindrome(this int numberToCheck)
	{
		char[] charArray = numberToCheck.ToString().ToCharArray();
		Array.Reverse(charArray);
		var reversedNumber = Convert.ToInt32(new string(charArray));
		return numberToCheck == reversedNumber;
	}
}

So, put all the numbers in a character array, reverse that array, create an integer from that reversed array, and check if it matches the original number passed in.

Conclusions

Some might regard the fluent syntax as a bit gimmicky, others might say it’s very readable. I know if I came across this code written by someone else tomorrow, and I hadn’t ever done this myself, rather than just accept it, my instinctive reaction would be to dig into it to see how this syntax had been achieved! So, it’s potentially quite distracting. But I guess you could argue that about anything new. I’ll discuss this with my team mates before considering whether this is just an academic exercise or a syntax that we’re all happy to use. Hope you enjoyed it – again – you can find all this at my github account. Questions, comments, even criticisms(!) – all welcome.

Advertisements

8 responses to “Project Euler Exercise 4

  1. Your IsPalindrome function in Int32Extensions could possibly be written using string Reverse() and linq SequenceEqual functions. See below;

    var original = numberToCheck.ToString();
    var reversed = original.Reverse();
    return original.ToCharArray().SequenceEqual(reversed);

    Please note: I haven’t checked the performance on both the ways.

    • @Viral Your method would compare the character arrays, and thereby not overflow if the reversed value exceeded in.MaxValue. But I wonder if it’s necessary to create a LINQ sequence and the additional overhead of sequence comparison. It seems a little overkill. My only change would be to protect against integer overflow by doing a string comparison:

      char[] charArray = numberToCheck.ToString().ToCharArray();
      Array.Reverse(charArray);
      var reversedNumber = new string(charArray);
      return reversedNumber.Equals(numberToCheck.ToString());

      • Thanks guys for your comments! While I now see the issue with IsPalindrome(), I’m on the fence with this one about which of your two approaches I prefer. I think I’m leaning towards Viral’s one – though probably mostly on the grounds that it contains an extension that I haven’t seen before! Will update solution tonight to match Viral’s suggestion (sorry Bernhard!). Anyway – wouldn’t string.Equals() be doing something similar under the hood?

  2. Should’ve mentioned in first post, but I really liked the Fluent Interface style.

  3. Few issues on design against requirements;
    Your solution iterates through all pelindromic numbers and then just return the Max.
    Also, your GetList method in ProductIterator should enumerate from max -> min instead of min -> max.
    ProductIterator range specified in unit tests could be changed from 10-99 and 100-999.

    yield i * j in GetList isn’t used as its supposed to be since the place its used isn’t breaking on finding a pelindrome.

    • On your first point, I’m not sure what the issue is – I think that is what the requirements say – get the maximum palindrome – am I missing something? (you probably told me earlier in person, but my rubbish memory is failing me now!)

      I think the GetList() method is from the first take. I should have clarified here that this blog post was about my second attempt. I’m not sure you need to break when using yield return, do you? I’ve just tried debugging it, and it seems to behave as I expected, i.e. it leaves the GetList() method with whatever the current product is – that product is then evaluated to see if it’s a palindrome, and then we’re back in the nested for loop moving on to the next iteration of the inner loop.

      The ordering from max-to-min vs min-to-max might work, but I can’t decide if it would be quicker every time.

      Fair point about iterating from 10-99 instead of 1 to 99 – the problem did say about the product of 2 2-digit numbers, not the product of 2 up-to-2-digit numbers.

  4. This was my solution when I wrote it
    https://github.com/MrKevHunter/Euler/blob/master/Euler%204/Program.cs

    I’m with Viral on the reverse function too

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