C#.Net through Euler #9

+Randall Munroe often talks about how much he likes learning a new programming language by solving problems  on the website http://projecteuler.net. I have taken the habit of doing the same, not only to learn new languages but also when trying to exploit a languages features and specialization.

The situation

I have been working on a small C# project recently that included some data management and live presentation and manipulation. Even thought I had already worked with C#/WPF, I never had the time to learn and make mistakes. This time, everything is different. I most have rewritten the whole application 3 or 4 times trying to get closer to the idiomatic way of doing things. That led me to some of +Jon Skeet old blogs on rewriting linq to object in C#.

The problem

We are going to do Euler Problem #9 and look at an implementation featuring concepts of C# and LINQ in action.

Euler Problem #9

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

a² + b² = c²

Find the product abc.

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

http://projecteuler.net/problem=9

First thoughts and background

A quick search on Wikipedia.org shows that there is a way to generate primitive Pythagorean triplet from a ternary tree (a 3-branch on each node tree). Basically, you can start from the first know triplet (3, 4, 5) and than apply one of three transformation to obtain another and from there you can do the same thing. 

The article also says that if (a, b, c) is a primitive triplet, for any positive integer k, (ka, kb, kc) is also a triplet.

First implementation

From that information, I knew some way of generating triplet and knew my stopping conditions from Euler's problem. I got cracking.

Having done some Haskell recently in which generating infinite sequence is an easy task, I went on thinking I would use the same pattern. I am using a BreathFirstSearch of my Tree instead of a DepthFirst in order to kept my triple in ascending order. Don't look too much as to why I am using a SortedSet instead of a Queue, we will check that later.

Expectations

Having done some LINQ before, this is what I came with. I thought that it seemed pretty reasonable and easy to read. We have some fonction that generates a infinite enumerable element and from those elements, we want only those whose sum is below or equal to 1000.

What really happened : The program outputted the correct data (yes!) but hanged forever after... 

Thinking about it, it was to be expected the implementation of LINQ "Where" operator is a much or less a foreach with a predicate and iterating over our infinite collection will take an infinite time.

Fix

We know that we currently have more than we really need. We have a collection that is more or less sorted and we know that our infinite generator will stream object that have a constantly growing sum. We therefore only need to stop when we are over our target.

There is a useful concept that has this effect : the iterator. I therefore went on implementing an IEnumerator infinite generator. It were doing the right thing, and I could stop the iteration after as many step as I wanted. But what I really wanted is to apply a filter that would do that automatically. Bad luck, when trying autocomplete, our new IEnumerator seemed pretty lonely having MoveNext() and Current() as its only two methods not deriving from "object".

I went on writing a static class for extension methods named EnumeratorEx with a TakeWhile() method that takes a predicate and iterates while the predicate is true. All when on working just fine, but this didn't seemed right.

Deferred execution

Deferred execution is the act by which we defer something until we no longer have the choice to do it. I shouldn't have to explain it in too much detail since it's self-explanatory for anyone who attended university. A quit search on Google showed that there were three operator in LINQ that offered deferred execution "Take", "TakeWhile", "Skip", "SkipWhile".

There we go, not only do we have what we need, it even has the same name as what we have given it.

De-fixing

After redoing everything to use an Enumerator, we now know that TakeWhile is using the IEnumarable.GetEnumerator and handling all of the fun stuff itself. It also means that we have to revert to our first implementation. Using the new TakeWhile, instead of the Where gives us exactly what we want and even stop when it's no longer needed.

Final Straight

We can now print all element up whose sum is up to 1000 and, bad luck, our item isn't a primitive Pythagorean Triple. We have to calculate our composite triples, but knowing the deferred execution trickery, we can use a number generator to dynamically calculate those.

We also see that GenerateInfinitePrime isn't really generating purely ascending items because the three modification used to obtain the next item doesn't guarantee order (the reason for the SortedSet instead of the Queue). Now, we have purely ascending primitive and are ready to make composite.

Composite

For each primitive that we have generated, we are going to calculate an infinite series starting at 1 and growing by 1. To those element we will use the "Select" operator to transform our input "an int" into something else "a triple". Now we have infinite composites!

Final

Now that everything is in place, we can show our final query. Our whole program is only an infinite generator of IEnumerable and filters as if we were in a functional language.

A fast topo of the function that are used :

• Generate
• Purpose built function for infinite generation based on a pattern.
• TakeWhile
• Deferred execution that enumerates until the predicate is false.
• Select
• Allow to "project" meaning to associate each element of our enumeration to something else.
• Where
• Filter element in an enumeration based on a predicate.
• First
• Returns the first element.
• new {
• Creates an anonymous type on the fly with the names attributes.