Bill Blogs in C#

Bill Wagner discusses C#, LINQ, and other items of interest

Euler Problem 11, or it’s about time I wrote some code

I just needed to write some code last night, so I figured I’d pull out the Euler problems and solve another.

Problem 11 asks you to find the largest product of any sequence of 4 numbers in a 20 x 20 grid. The sequence can be horizontal, vertical, or diagonal. As with the other problems, my goal is to display how C# 3.0 syntax enhancements can be best exploited for this problem.

I wrote two very similar solutions to problem 11 so that you can see how LINQ mixes imperative and functional styles, and how lazy evaluation means that the different expressions of the solution actually have similar characteristics at runtime.

The algorithm must search through the grid four times finding all the candidate sequences: horizontal, vertical, down-right, and down-left. There are four LINQ queries that find possible answer sequences. To find the single answer, you must find the max value across all four queries.

A more pure functional solution creates a single query by concatenating the four queries together. Then, after concatenating all four queries, it calls order by to find the max:

   1: var best = (from x in Enumerable.Range(0, 17) // horizontal
   2:             from y in Enumerable.Range(0, 20)
   3:             let first = data[x, y]
   4:             let second = data[x + 1, y]
   5:             let third = data[x + 2, y]
   6:             let fourth = data[x + 3, y]
   7:             let answer = first * second *
   8:                     third * fourth
   9:             select new
  10:             {
  11:                 X = x,
  12:                 Y = y,
  13:                 Direction = "Right",
  14:                 Values =
  15:                  string.Format("{0}, {1}, {2}, {3}",
  16:                     first, second,
  17:                     third, fourth),
  18:                 Answer = answer
  19:             }).Concat(from x in Enumerable.Range(0, 20) // Vertical
  20:                       from y in Enumerable.Range(0, 17)
  21:                       let first = data[x, y]
  22:                       let second = data[x, y + 1]
  23:                       let third = data[x, y + 2]
  24:                       let fourth = data[x, y + 3]
  25:                       let answer = first * second *
  26:                               third * fourth
  27:                       select new
  28:                       {
  29:                           X = x,
  30:                           Y = y,
  31:                           Direction = "Down",
  32:                           Values =
  33:                            string.Format("{0}, {1}, {2}, {3}",
  34:                               first, second,
  35:                               third, fourth),
  36:                           Answer = answer
  37:                       }).Concat(from x in Enumerable.Range(0, 17)  // Down to the right
  38:                                 from y in Enumerable.Range(0, 17)
  39:                                 let first = data[x, y]
  40:                                 let second = data[x + 1, y + 1]
  41:                                 let third = data[x + 2, y + 2]
  42:                                 let fourth = data[x + 3, y + 3]
  43:                                 let answer = first * second *
  44:                                         third * fourth
  45:                                 select new
  46:                                 {
  47:                                     X = x,
  48:                                     Y = y,
  49:                                     Direction = "DownRight",
  50:                                     Values =
  51:                                      string.Format("{0}, {1}, {2}, {3}",
  52:                                         first, second,
  53:                                         third, fourth),
  54:                                     Answer = answer
  55:                                 }).Concat(from x in Enumerable.Range(3, 17)
  56:                                           from y in Enumerable.Range(0, 17)
  57:                                           let first = data[x, y]
  58:                                           let second = data[x - 1, y + 1]
  59:                                           let third = data[x - 2, y + 2]
  60:                                           let fourth = data[x - 3, y + 3]
  61:                                           let answer = first * second *
  62:                                                   third * fourth
  63:                                           select new
  64:                                           {
  65:                                               X = x,
  66:                                               Y = y,
  67:                                               Direction = "DownLeft",
  68:                                               Values =
  69:                                                string.Format("{0}, {1}, {2}, {3}",
  70:                                                   first, second,
  71:                                                   third, fourth),
  72:                                               Answer = answer
  73:                                           }).OrderByDescending((record) => record.Answer).First();
  74:  
  75: Console.WriteLine(best);

Of course, many folks are turned off by seeing 70+ lines of code with a single semi-colon. So here’s a different refactoring of the same code. In the following version, I construct four different queries. It’s important to understand that constructing a query in LINQ is not the same as executing it. After constructing four distinct queries, I concatenate them, and find the max.  The C# compiler can correctly determine that all four queries project a sequence of the same anonymous type, so all four query results can be concatenated.  (If you really want, you can look in Reflector and find that the compiler generates only one anonymous type for the query result objects.)

var horizontal = from x in Enumerable.Range(0, 17) // horizontal
                 from y in Enumerable.Range(0, 20)
                 let first = data[x, y]
                 let second = data[x + 1, y]
                 let third = data[x + 2, y]
                 let fourth = data[x + 3, y]
                 let answer = first * second *
                         third * fourth
                 select new
                 {
                     X = x,
                     Y = y,
                     Direction = "Right",
                     Values =
                      string.Format("{0}, {1}, {2}, {3}",
                         first, second,
                         third, fourth),
                     Answer = answer
                 };
var vertical = from x in Enumerable.Range(0, 20) // Vertical
               from y in Enumerable.Range(0, 17)
               let first = data[x, y]
               let second = data[x, y + 1]
               let third = data[x, y + 2]
               let fourth = data[x, y + 3]
               let answer = first * second *
                       third * fourth
               select new
               {
                   X = x,
                   Y = y,
                   Direction = "Down",
                   Values =
                    string.Format("{0}, {1}, {2}, {3}",
                       first, second,
                       third, fourth),
                   Answer = answer
               };
var downRight = from x in Enumerable.Range(0, 17)  // Down to the right
                from y in Enumerable.Range(0, 17)
                let first = data[x, y]
                let second = data[x + 1, y + 1]
                let third = data[x + 2, y + 2]
                let fourth = data[x + 3, y + 3]
                let answer = first * second *
                        third * fourth
                select new
                {
                    X = x,
                    Y = y,
                    Direction = "DownRight",
                    Values =
                     string.Format("{0}, {1}, {2}, {3}",
                        first, second,
                        third, fourth),
                    Answer = answer
                };
var downLeft = from x in Enumerable.Range(3, 17)
               from y in Enumerable.Range(0, 17)
               let first = data[x, y]
               let second = data[x - 1, y + 1]
               let third = data[x - 2, y + 2]
               let fourth = data[x - 3, y + 3]
               let answer = first * second *
                       third * fourth
               select new
               {
                   X = x,
                   Y = y,
                   Direction = "DownLeft",
                   Values =
                    string.Format("{0}, {1}, {2}, {3}",
                       first, second,
                       third, fourth),
                   Answer = answer
               };
 
var best = horizontal.
    Concat(vertical).
    Concat(downRight).
    Concat(downLeft).
    OrderByDescending((record) => record.Answer).First();
Console.WriteLine(best);

There’s one other interesting bit of syntax that should be noted here.  I’ve used ‘let’ in all the queries to avoid recomputing the same result, and to ensure that I’ve avoided any copy/paste errors as I put together the answer.

Published Thu, Oct 2 2008 3:17 PM by wwagner

Comments

# re: Euler Problem 11, or it’s about time I wrote some code@ Thursday, October 02, 2008 4:52 PM

Wouldn't you want the last to be

x in Enumerable.Range(3, 20)

And Direction to actually be different on every query?

by Jeff

# re: Euler Problem 11, or it’s about time I wrote some code@ Thursday, October 02, 2008 8:50 PM

I do feel turned off by 70+ lines of code. I have been looking at the Project Euler problems in F#, but a friend has been using purely LINQ. He passed this solution on to me for a look after I mention I saw your blog, thought you may be interested.

long[][] g = new long[][] { new long[] { 08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08 },

new long[] { 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00, },

<snip />

new long[] { 20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54, },

new long[] { 01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48 } };

var answer = new long[] {

// Hoziontal

Enumerable.Range(0,19).SelectMany( y => Enumerable.Range(0,16).Select( x => g[y].Skip((int)x).Take(4).Aggregate( 1L, (m, k) => m * k ) ) ).Max(),

// Vertical

Enumerable.Range(0,19).SelectMany( x => Enumerable.Range(0,16).Select( y => new long[] { g[y][x], g[y+1][x], g[y+2][x], g[y+3][x] }.Aggregate( 1L, (m, k) => m * k ) ) ).Max(),

// Diagonal L-R

Enumerable.Range(0,16).SelectMany( x => Enumerable.Range(0,16).Select( y => new long[] { g[y][x], g[y+1][x+1], g[y+2][x+2], g[y+3][x+3] }.Aggregate( 1L, (m, k) => m * k ) ) ).Max(),

// Diagonal R-L

Enumerable.Range(3,19).SelectMany( x => Enumerable.Range(0,16).Select( y => new long[] { g[y][x], g[y+1][x-1], g[y+2][x-2], g[y+3][x-3] }.Aggregate( 1L, (m, k) => m * k ) ) ).Max()

}.Max();

by Charles

# Project Eurler #12@ Saturday, October 04, 2008 11:45 AM

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

by Patrick Steele's .NET Blog

# Project Eurler #12@ Saturday, October 04, 2008 12:27 PM

I see that Bill did Euler #11 earlier this week so I thought I&#39;d tackle #12 . The first thing I wanted

by Patrick Steele