Patrick Steele's .NET Blog : Project Euler, .NET

Project Euler #14

PSteele — Sat, 20 Dec 2008 02:19:40 GMT

I had so much fun doing #13 I thought I'd tackle #14 as well.

This problem wasn't too bad. I started by defining some extension methods on long:

        1: static class Extensions

       2: {

       3:     public static long NextInSequence(this long number)

       4:     {

       5:         if (number % 2 == 0)

       6:         {

       7:             return number / 2;

       8:         }

       9:         else

      10:         {

      11:             return 3 * number + 1;

      12:         }

      13:     }

      14:  

      15:     public static IList<long> GenerateSequence(this long number)

      16:     {

      17:         List<long> seq = new List<long>();

      18:  

      19:         long next = 0;

      20:         do

      21:         {

      22:             next = number.NextInSequence();

      23:             seq.Add(next);

      24:             number = next;

      25:         } while (next != 1);

      26:  

      27:         return seq;

      28:     }

      29: }

While I don't necessarily need the full list of terms (GenerateSequence), I used the list in testing to make sure my sequence logic was correct.

Now, the only thing left to do was to find the longest sequence. I used a LINQ query to order the list of sequence counts in descending order so the longest would be at the top:

       1: var range = Enumerable.Range(1, 1000000);

       2:  

       3: var biggest = (from n in range

       4:                let size = ((long)n).GenerateSequence().Count

       5:                orderby size descending

       6:                select new { Number = n, Length = size }).ToArray();

       7:  

       8: Console.WriteLine("{0} has a sequence of {1}", biggest[0].Number, biggest[0].Length);

Technorati Tags: Project Euler,.NET,LINQ

Project Euler #13

PSteele — Fri, 19 Dec 2008 20:52:30 GMT

It's been a while since I did one of the Project Euler problems. And since a lot of my work recently has been fixing bugs and working on some design documents, I was itching to do some "real" coding. So it's on to problem #13.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

It would be nice if I could have stuck all of those numbers in an integer and simply added them up, but they were too big for that. The solution I came up with kind of feels like I cheated a bit, but it gives me the correct answer! What I did was take the list of 50-digit numbers and stick a decimal point in the middle (at the 25th character). This gives me a number that .NET's double data type can handle. I just had to make sure I removed the decimal point before grabbing my answer.

So my final solution was:

        1: string[] numbers = {

       2:     // giant list of numbers from website clipped

       3:                    };

       4:  

       5: var list = from num in numbers

       6:            select double.Parse(num.Insert(25, "."));

       7:  

       8: var sum = list.Sum();

       9: string answer = sum.ToString().Replace(".", "").Substring(0, 10);

Technorati Tags: Project Euler,.NET,LINQ

Project Eurler #12

PSteele — Sat, 04 Oct 2008 15:43:28 GMT

I see that Bill did Euler #11 earlier this week so I thought I'd tackle #12.

The first thing I wanted to do was write a routine to generate a triangle number. As we've seen throughout this series, LINQ can come in very handy:

static int TriangleOf(int number){    return Enumerable.Range(1, number).Sum();}

Now I needed to find all the divisors of a number. I have to "eat crow" and admit the first time I did this, I used the brute force method:

static IEnumerable<int> FindAllDivisors(int number){    return from d in Enumerable.Range(1, number)           where number % d == 0           select d;}

I didn't like it. I knew I could use the square root to reduce the number of iterations in this loop, but that would mean every "select" of my LINQ query would need to return more than one result -- the divisor and the number / divisor. I couldn't see any easy way to create two results from a query so I just left this as-is and moved on to actually solving the problem.

Again, LINQ made this extremely easy:

var answer = (from d in Enumerable.Range(1, int.MaxValue)          where FindAllDivisors(TriangleOf(d)).Count() > 500          select d).Take(1);

As you might expect, this wasn't very quick. In fact, I let it run overnight since I didn't start on this till later in the evening. It ended up taking 5 hours and 15 minutes. NOT A SOLUTION!

So I started researching how I could return multiple items from a single LINQ query. The answer was embarassingly simple -- create an array!

var values = from d in Enumerable.Range(1, (int)Math.Sqrt(number))         where number % d == 0         select new int[] { d, number / d };

But now I've got an IEnumeable<int[]> and I want all the divisors together in an IEnumerable<int>. I looked around at the extension methods on IEnumerable<T> and found SelectMany. This method will project each element into an IEnumerable<T> and flatten the result into a single sequence.

So my revised FindAllDivisors now looks like this:

static IEnumerable<int> FindAllDivisors(int number){    var values = from d in Enumerable.Range(1, (int)Math.Sqrt(number))             where number % d == 0             select new int[] { d, number / d };    return values.SelectMany(x => x);}

Now this completes in a respectable 5 - 6 seconds. MUCH better than my first attempt. Sometimes, KISS only gets you so far.

Technorati tags: Euler, IEnumerable, SelectMany

Euler 10

PSteele — Wed, 27 Aug 2008 13:10:00 GMT

After tackling number 9 yesterday, I thought I'd do #10 real quick since it seemend pretty easy.

Calculate the sum of all the primes below two million.

The code for the algorithm was a simple 2 lines:

var range = GeneratePrimes().TakeWhile(x => x < 2000000);int sum = range.Sum();

But I have to confess that I took most Bill's GeneratePrimes() from is solution to Euluer #7. I say "most" because I didn't grok his implementation of IsPrime(). I read his description a number of times and even stepped through the code a couple of iterations, but I still didn't "get" his use of the List<int> to keep a list of already found primes.

So I wrote my own IsPrime(). I used the canonical definition of a prime number ("a number which is evenly divisible by one 1 and itself").

public static bool IsPrime(this int number){    if (number == 1)        return false;    if (number == 2)        return true;     var range = Enumerable.Range(2, number - 2).ToList();    return range.TrueForAll(n => number % n != 0);}

So I started running my solution. After about 10 minues, I paused and saw that I was still generating prime numbers in the 20,000-30,000 range. Hmmm... Ok, I'll just let it run overnight.

I got up about 7.5 hours after going to bed and my app was still running! I paused it and saw it was only in the 950,000 range of determining primes below 2 million (not even half way through!). So I decided to take 20 seconds and really THINK about my IsPrime() method and realized how inefficient it was to generate that huge range to use the 'TrueForAll' on.

So I eliminated the LINQ code and did a simple for loop that will break out as soon as it finds a number that is evenly divisible:

public static bool IsPrime(this int number){    if (number == 1)        return false;    if (number == 2)        return true;     for (int n = 2; n < number; n++)    {        if (number % n == 0)            return false;    }     return true;}

Now I ran the code and after about 20 minutes ran into a new problem: An overflow exception calling range.Sum(). On the good side, it only took about 20 minutes to get my primes under two million. On the bad side, I should have thought about that line of code a little more. Adding up all of the primes below two million is probably going to produce a huge number (much bigger than a 32-bit integer could hold).

So I decided to move the range "up" to use longs (I didn't feel like going back and changing the extension method to use longs):

var longrange = range.Cast<long>();var sum = longrange.Sum();

Success in about 20 minutes!

PS - I went back and ripped out my IsPrime() and put Bill's back in. Now it completes in about 5 minutes. How come the boss is always right?

Project Euler #9

PSteele — Tue, 26 Aug 2008 21:22:00 GMT

So I decided to start looking into the Project Euler problems. A number of fellow SRT employees have been tackling these over the past few months and after recently reading Bill's solutions for problems #7 and #8 I decided to look at #9.

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

I thought about this for quite a while. I was trying to see how I could utilize LINQ to make this easier. In the end, I decided to just use the brute force method of nested loops:

private static void Euler9(){    for (int a = 0; a < 1000; a++)    {        for (int b = a + 1; b < 1000; b++)        {            for (int c = b + 1; c < 1000; c++)            {                if (a + b + c == 1000 && (Math.Pow(a, 2) + Math.Pow(b, 2) == Math.Pow(c, 2)))                {                    Console.WriteLine("{0},{1},{2}", a, b, c);                    return;                }            }        }    }}

I added a few optimizations in an effort to speed this up:

Since a+b+c has to equal 1000, no single element (a or b or c) can be greater than 1000. Therefore my loops are pretty short.
I took advantage of C#'s short-circuiting to do the simple "a + b + c == 1000" check before doing the squares.

It runs pretty quick (under a second). The first time I ran it I took out the "return" to make sure my logic only produced a single result. It did! :)