Project Euler: my solutions

I started working on the Project Euler problems tonight. I just posted my solutions (in C#) to problems 1-7 on Github.

I’m sort of regretting doing these in C#. I may switch to a functional language like F# to clean up the syntax. So far most of the problems are pretty trivial to brute force (eg. it only takes about 5 seconds to calculate the 10,001st prime on my computer). I believe the spirit of the problems are to require optimization so I might switch to C so I can focus on benchmarking my solutions. The JIT compiler and garbage collection in C# and F# make them difficult languages to accurately benchmark.

The most interesting problem so far was #4. The goal is to find the largest palindromic number that’s the multiple of two 3 digit numbers. There are only 998,001 multiples (and half are duplicates) so you could just calculate them all and sort them, but instead I decided to traverse a matrix in descending order to limit CPU time. To find the pattern I created the matrix in Excel and applied a color scale.

From here it’s obvious the correct traversal order to get the largest multiples first is diagonally starting from the bottom left.

The key is to observe that the sum of the column and row indexes are constant on the diagonal. The traversal algorithm then looks like:

public static IEnumerable<T> Traverse<T>(int rows, int cols, Func<int, int, T> generator)
{
var stripes = rows + cols - 1;
for (int stripe = 1; stripe < stripes; stripe++)
{
for (int col = 1; col <= stripe; col++)
{
for (int row = stripe; row > stripe-col; row--)
{
if ((col + row == stripe + 1) && (col >= row))
{
yield return generator(row-1, col-1);
}
}
}
}
}

This only computes the matrix cells that the caller asks for. Quite a neat trick.

Edit: I added some non-LINQ solutions which are much faster than the original solutions. I still prefer writing the original solution in LINQ and then optimizing.