Project Euler Problem 4

This post tackles Problem 4 in the Project Euler series, which wants us to find the largest palindrome that is a product of two, three digit, numbers.

Without further ado, here's my solution:

    public class Problem4
    {
        public static void Main()
        {
            (
             from x in 100.To(999)
             from y in 100.To(999)
             let product = x * y
             where product.IsPalindromic()
             orderby product descending
             select product
             )
             .First()
             .DisplayAndPause();
        }

    }

If you've not had much exposure to C#3.0, this might come as quite a shock: maybe you're wondering whether I slipped up, and pasted in some mutant SQL? But I can assure you that what I have written is quite legal, and I've no fear that Anders will be issuing an arrest warrant for me!

This snippet introduces several new features of C# 3.0, so we'll work through it slowly.

The part inside the brackets is a Query Expression. It might look like an island of SQL in an ocean of C# - albeit backwards SQL. In fact it's actually a different way (in many cases a more natural way) of writing the kind of expressions which query sequences that we've written in previous posts. The compiler will take that expression and translate it into a chain of calls to the appropriate extension methods on the Enumerable class. I'll let Anders supply the details of how that works.

The from clause defines the source of the data for the query, and names a range variable that you use in subsequent clauses: the range variable is a bit like the iteration variable in a foreach loop. But what is the source of data here? What I've done is to define an extension method, To, that I can call as if it where a member of int. It creates an iterator that produces all the integers in the range of specified.

I've mentioned extension methods in previous posts. Now's the time to see how they work. This is the definition of To:

public static class Problem4Extensions
{
    public static IEnumerable To(this int first, int last)
    {
        for (int i = first; i <= last; i++)      
        { 
            yield return i;
        } 
    }
}

As you can see, To is just a static method defined in a public class (that's a key requirement of extension methods, by the way - they won't work if you try putting them anywhere else). The only thing special about it is that the first parameter has the this keyword in front of it. The "this" keyword marks out the type that will appear to be extended with the new method. The extension method body is written just as any other static method would be. So don't get too excited: extension methods don't give you any special powers to delve into the internals of the classes that you're extending.

We use two from clauses here, and this will generate for us all possible pairs of numbers between 100 and 999.

The let clause is nice: it allows us to store the result of an expression to save duplicting it throughout the query. Because, having generated the product of x and y, we then need to check whether it is palindromic - the where clause filters it out if it's not. For that we've got another extension method:

    public static class Problem4Extensions
    {
        ...

        public static bool IsPalindromic(this int number)
        {
            var digits = number.ToString().ToCharArray();

            return digits.SequenceEqual(digits.Reverse());
        }
    }

Using the orderby clause we sort the palindromes, so that the biggest ones come first. To complete the query expression, we need a select statement to actually suck some data out of the query. Here we just pull out the product (that we now know is a palindrome). The answer to the problem is clearly the first number in this sequence, which First() kindly gives us. Finally, so that I can boast again of having solved the problem in one line of code, I've defined an extension method to print the result to the console, and wait for the user admire it:

    public static class Problem4Extensions
    {
        ...
        public static void DisplayAndPause(this int number)
        {
            Console.WriteLine(number);
            Console.ReadLine();
        }
    }

You can download the complete solution here. I should point out that this brute-force means of finding the answer is by no means the best. Look on the Project Euler forums for more mathematically informed ways of tackling the problem.