Project Eurler #12

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.