Project Euler Problem 9

I've never seen a popularity contest for Mathematical theorems. If one was ever held, I'd bet on Pythagoras's Theorem taking the number one spot - because his is the only theorem that most people have ever heard of. I'd further bet (if I was a betting man) that a good number of them would even be able to quote it - having had it caned into them at school:

"The square on the hypotenuse is equal to the sum of the squares on the other two sides".

Or as my old maths teacher used to say,

"The squaw on the hippopotamus is equal to the sum of the squaws on the other two hides."

(He had a really terrible joke, with this as its punchline; if you're feeling desperate enough, you can read it, and a few others, here)

And so we come to today's problem, Problem 9, which deals with Pythagorean triplets. These are just sets of three integers (a,b,c) with a ^ 2 + b ^2 = c^2; basically, numbers that satisfy Pythagoras's theorem. The problem is to find the unique set of numbers where a + b + c = 1000, and a < b < c.

We'll use a brute force method to solve this. We just need to note that since a must be less than b, and a + b + c = 1000, neither a nor b can exceed 500.

Here's the solution, using C# query syntax:

class Problem9
    {
        public static void Main()
        {
            (
             from a in 1.To(500)
             from b in a.To(500)
             let c = 1000 - a - b
             where a * a + b * b == c * c
             select new { a, b, c, product = a * b * c }
            )
            .Single()
            .DisplayAndPause();
        }
    }

(You can find the code for the two extension methods , To, and DisplayAndPause in the last post)

We're using the two from clauses to generate all possible pairs of numbers (a,b) where a is between 1 and 500, and b is between a and 500. The let clause calculates the value of c, storing it as an intermediate result; The where clause makes sure that a,b and c are truly pythagorean.

In the select clause I'm generating a new anonymous type using the new {...} expression. Anonymous types are just a shorthand way of grouping together a set of properties, without going to the trouble of defining a class to hold them. In many cases you don't even need to give names to those properties: C# will infer names from the variables or properties that you assign into them. So the first 3 properties in this anonymous type will have names "a", "b", and "c"; for the fourth property, I have to stop being lazy and think of a name ("product"), because it gets its value from an expression ("a * b * c"), and C# isn't imaginative enough to pick a name for that.

If you want to use anonymous types yourself, you should note two things. Firstly, the properties on the type are read-only: you can't change their values once they've been initialised. Secondly, you can only easily use anonymous types within the scope of a method: you can't return them from methods for the simple reason that you don't know the name of their type - they're anonymous, duh! Actually, I lie. You can return them from methods, but only if you return them as object - but then you'd need to use Reflection to get hold of their properties.

Because there's a unique answer to this problem, the query expression between the brackets will generate a sequence containing just one element. The Single extension method will return this for us - and will even throw an exception if it finds that there's more than one, which is a useful check that we've got the query expression correct.

As a nice touch, anonymous types have their ToString() method overridden, so that when you display them, as I do in the DisplayAndPause extension method, you see the values of all their properties, like so:

{ a=???, b=???, c=???, product=????}

(except you'd see the answers, rather than the question marks I've put there to stop you cheating!).

Straight forward today, wasn't it?