Project Euler Problem 11

What's your strategy for solving a word search? What - you haven't got one? OK, I'll be honest: I usually start out by just staring at the grid, hoping that words will magically stand out. Sometimes they do. But more often than not, I'm left with a list of words that refuse to be stared out of their hiding places. What then?

I ask, because Problem 11 is a mathematicians equivalent of a word search: given a 20 x 20 grid of numbers, find the line of four numbers that has the maximum product. Since they have yet to implement the "stare" keyword in C#, we need to find an methodical way for the computer to search the grid.

When I'm trying to unearth a particular stubborn word in a grid, I'll usually start from the bottom right (to force myself to look more carefully), scanning to find its first letter. Once I've got that, I'll look at all the letters encircling it; if any of them are promising, I just need to follow the line that the two letters begin to see if I've found the word. To search the number grid we can do something similar. The computer doesn't need to start at the bottom right: it will look carefully anyway. But we'll still get it to work through every square of the grid, looking at every line of four numbers that starts from that square: every possibility needs to be checked to be sure we find the maximum.

But we don't need to repeat ourselves. If I've already checked out the line that goes down from a square to the fourth row directly beneath it, I don't then need to check the line going up from that fourth row. In other words we only need to check four directions from each square: a line horizontally to the left, a line vertically down, a line diagonally down to the left, and a line diagonally down to the right. That will cover all the possibilities. We'll split the algorithm into two stages: generating a list of all the possible quadruplets in the grid, then checking the quadruplets to find the one with the maximum product.

Before we get ahead of ourselves, we need to convert the grid we're given into a form we can search. I've chosen to use a List of Lists of Integers, since this is the easiest to construct in a LINQ query. The outer list represents rows, the inner list columns of numbers.

The query to convert the input string to a List of Lists looks like this:

const string NumberString = @"
            08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
            49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
            81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
            52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
            22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
            24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
            32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
            67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
            24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
            21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
            78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
            16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
            86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
            19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
            04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
            88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
            04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
            20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
            20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
            01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
            ";

// create a list of lists of ints representing the cells
var digits = NumberString.
                // split string into rows
                Split(new[]{Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
                .Select(line =>
                    // split row into columns
                    line.Split(' ')
                    // ignore any whitespace
                    .Where(token => token.IsInteger())
                    // convert string to number
                    .Select(token => int.Parse(token))
                    .ToList()
                    )
                .ToList();

Now we can start collecting the quadruplets. In each case we use two from clauses to iterate through all the possible starting positions in the grid. From each position we use an inner Select clause to select the appropriate line of four numbers out from that position.

var horizontals = 
  // start from the left, and stop four cells before the right edge
  from x in 0.To(16)
  // include all rows from top to bottom
  from y in 0.To(19)
  select (from offset in 0.To(3)
        select digits[x + offset][y]);

var verticals =
  from x in 0.To(19)
  from y in 0.To(16)
  select (from offset in 0.To(3)
        select digits[x][y + offset]);

var forwardDiagonals =
  from x in 0.To(16)
  from y in 0.To(16)
  select (from offset in 0.To(3)
        select digits[x + offset][y + offset]);

var reverseDiagonals =
  from x in 3.To(19)
  from y in 0.To(16)
  select (from offset in 0.To(3)
        select digits[x - offset][y + offset]);

Each of the queries above generates an individual sequence of quadruplets, one query for each direction - the order that we process the different directions doesn't matter since we have to cover them all anyway. We need to be able to process all these sequences together. The Enumerable class does have a Concat method that will join two sequences, returning one longer sequence, but we need to join 4. For that, I've create the Concat() extension method.

It does the same job as Enumerable.Concat(), but works on a sequence of sequences (which is why I've stuck the individual sequences together in an array in the code below: arrays of type T implement IEnumerable<T>). Then it's just a case of calculating the Product of each quadruplet, and finding the maximum of all products:

new[]
{
    horizontals,
    verticals,
    forwardDiagonals,
    reverseDiagonals
}
    .Concat()
    .Select(quadruplet => quadruplet.Product())
    .Max()
    .DisplayAndPause();

Here's the complete listing. The full code can be found on the MSDN Code Gallery site.

[EulerProblem(11, Title = "What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?")]
public class Problem11
{
    public void Solve()
    {
        const string NumberString =
                    @"
                    08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
                    49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
                    81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
                    52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
                    22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
                    24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
                    32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
                    67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
                    24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
                    21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
                    78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
                    16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
                    86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
                    19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
                    04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
                    88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
                    04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
                    20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
                    20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
                    01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
                    ";

        // create a list of lists of ints representing the cells
        var digits = NumberString.
            // split string into rows
            Split(new[] {Environment.NewLine}, StringSplitOptions.RemoveEmptyEntries)
            .Select(
            line =>
            // split row into columns
            line.Split(' ')
                // ignore any whitespace
                .Where(token => token.IsInteger())
                // convert string to number
                .Select(token => int.Parse(token))
                .ToList()
            )
            .ToList();

        var horizontals = 
            // start from the left, and stop four cells before the right edge
            from x in 0.To(16)
            // include all rows from top to bottom
            from y in 0.To(19)
            select (from offset in 0.To(3)
                    select digits[x + offset][y]);

        var verticals =
            from x in 0.To(19)
            from y in 0.To(16)
            select (from offset in 0.To(3)
                    select digits[x][y + offset]);

        var forwardDiagonals =
            from x in 0.To(16)
            from y in 0.To(16)
            select (from offset in 0.To(3)
                    select digits[x + offset][y + offset]);

        var reverseDiagonals =
            from x in 3.To(19)
            from y in 0.To(16)
            select (from offset in 0.To(3)
                    select digits[x - offset][y + offset]);

        new[]
        {
            horizontals,
            verticals,
            forwardDiagonals,
            reverseDiagonals
        }
            .Concat()
            .Select(quadruplet => quadruplet.Product())
            .Max()
            .DisplayAndPause();
    }
}

public static class Extensions
{
    public static void DisplayAndPause(this object result)
    {
        Console.WriteLine(result);
        Console.ReadLine();
    }

    public static bool IsInteger(this string value)
    {
       int number;
       return int.TryParse(value, out number);
    }

    public static IEnumerable<T> Concat<T>(this IEnumerable<T[]> sequences)
    {
       return sequences.SelectMany(sequence => sequence);
    }

    public static int Product(this IEnumerable factors)
    {
        int product = 1;

        foreach (var factor in factors)
        {
            product *= factor;
        }

        return product;
    }
}