Using LINQ for the Euler Project

Posted on June 1st, 2008 by SealedSun

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

If you need to kill time and like mathematics and programming, Project Euler is a great source of nearly 200 tricky problems to solve. Having found a solution is especially rewarding as there is a strict policy of not providing any help apart from the problem description. If you can't solve a problem, then you can't solve it.

As of right now I have solved 26 out of 196 Problems, which according to the website makes me a 13% genius. My tool of choice is of course C# 3.0 and I must say that LINQ to Objects has allowed me to write solutions that resemble those shiny Haskell and Mathematica code snippets you find in the answer forums.

Even though I am probably not supposed to publicly post problem solutions, there is this one particular program that beautifully outlines how LINQ can be employed to compute the result:

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32

32=9, 33=27, 34=81, 35=243

42=16, 43=64, 44=256, 45=1024

52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

PLAIN TEXT
C#:
  1. public static IEnumerable Digits(this int n)
  2. {
  3.     while (n> 0)
  4.     {
  5.         yield return n%10;
  6.         n /= 10;
  7.     }
  8. }
  9. var s = (from i in 2.To(999999)
  10.     where i == i.Digits().Select(
  11.         d => (int) Math.Pow(d, 5)).Sum()
  12.     select i).Sum();

The only part where this solution could be improved is the choice of the range to search in as one could reason about the maximum number of digits (Hint: 6*95).

In the problem forums there is often a competition around writing the shortest program possible and obviously "minimalistic" (in terms of syntax) languages like J and Ruby have an advantage there. But with today's IDE support actually writing the LINQ-expression above didn't take any longer.

Tags: Programming // Add Comment »

Discussion Area - Leave a Comment




« »