Project Euler #11 Largest product in a grid

Question

Question

Link to the exercise : https://projecteuler.net/problem=11

I'm currently working on the Project Euler exercise's and I just finished the eleven exercise. It's working fast enough it takes around 15-25 ms to calculate the output, the volume of the code is probably bigger than it should be.I barely used any mathematics in order to find the solution I just don't see the mathematics in the question some people will just need a quick glance and they will have an idea how to solve it using math. I'm looking forward to see answer's concerning the code style, of course how to shorten the code and maybe an overall idea of how should I approach such type of tasks.

Explanation

General Info

There are 3 methods CollumnValues, RowValues, DiagonalValues they return array of type int with 4 values which are the values of the first 4 adjacent numbers. The parameters are startingIndex which serve's as a starting point and a boolean variable to determine whether it should go left/right/top/bottom. In DiagonalValues method the parameter bool leftDiagonal if it's value is true we take the following diagonal :

10 11 12 13

14 15 16 17

18 19 20 21

22 23 24 25

If the value is false we take :

10 11 12 13

14 15 16 17

18 19 20 21

22 23 24 25

This one is the one that might not be that accurate so I decide to show it. The other's are pretty much self explanatory :
- CollumnValues - bool top if it's false we go down, else we go up.
- RowValues - bool right if it's false we go left, else we go right.
There are 2 more methods that probably need explanation - IsInMinBounds and IsInMaxBounds they both take the same parameters int number and one more int which is the max or the min. They're job is to check whether the input number is in the bounds of the array, for example in order to go left we first need the starting point to be greater than 2 so we can get values at indexes : 0, 1, 2, 3. They also declare variable int tolerance = (number/20)*20which make's sure that the code will detect all the lines, what I mean by this :
- We have 20x20 grid so the last index in our first line of array is 19.
- While the number is less than 20 we are on the first line.
So the way this helps us is that while number < 20 we have the following : int tolerance = 0 * 20 because the number is always smaller than 20 we get something below zero , we are using int so it round's it up to 0 which multiplied by 20 is 0. Zero added to the max or min. will just give us the max or the min, in other words it will check only on the first line. However if we have a number greater or equal to 20, that means we have a number that's on the second row in this case we have int tolerance = 1 * 20 resulting in 20 so now we are checking if the max or the min which we passed as parameters + the tolerance are greater or smaller than the input number. The overall idea is to give the method just the starting line maximum or minimum and still work for all the lines.

We also have 3 try/catch blocks in the Main method. They will not catch any other exception aside from the IndexOutOfRange, once they do that we know it's time to stop checking for specific direction.
RowValues Method

If we have startingIndex = 0 and right = true the first 4 adjacent numbers are at indexes : 0, 1, 2, 3 so the for loop will end at startingIndex + RowIncreasment where RowIncreasment is 3 it's always 3 because we need 4 numbers we already have the first one so we need to add just 3 also we need to check if the startingIndex is in the bounds because we cant go right and still get 4 adjacent if the starting index is greater than 16 because the maximum is 19. If we are going left however we need to check if the startingIndex is greater than 0, it has to be at least 3 in order to get 4 adjacent numbers.
CollumnValues

If we have startingIndex = 0 and top = false the first 4 adjacent numbers are at indexes : 0, 20, 40, 60 so the for loop will start at startingIndex + CollumnIncreasment and end at startingIndex where CollumnIncreasment is 60 and it should decrease by 60/3 just so we don't use magic numbers (we always check 60 indexes below). If we are going top however (top=true) we need the startingIndex to be at least 60 so that the for loop can go up 4 times and still not end in negative index resulting in exception.
DiagonalValues If we have startingIndex = 0 && right = true the first 4 adjacent numbers are at indexes : 0, 21, 42, 63 so we have increase of 21 so we put that in the for loop, now we have the startingIndex as our starting point, and we end at startingIndex + 63 because the last number will be located at x + 21 * 3 where x is our startingIndex the last thing is to check if the starting point is in the bounds. If we go left we see that the first numbers are located at the following indexes : 3, 22, 41, 60 the increase here is 19, so we write it in the for loop, the starting point here will be 19 * 3 + startingIndex and it will end at startingIndex, again lastly we check if the starting point is in the bounds.

Lastly we have 3 more methods SumOfDiagonals, SumOfRows, SumOfCollumns. They just take the returned array from the DirectionValues methods and return the higher product out of the the by switching the bool variable taken as parameter from them.

Here's the code :

internal class Program
{
    private const string text =
        "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";
    private static readonly string[] digits = text.Split(' ');

    private const int RowIncreasment = 3;
    private const int CollumnIncreasment = 60;


    private static void Main()
    {
        int[] maxSum = new int[3];
        int sumOfDiagonals = 0;
        int sumOfRows = 0;
        int sumOfCollumns = 0;
        bool stopDiagonals = false;
        bool stopRows = false;
        bool stopCollumns = false;
        Stopwatch sw = new Stopwatch();
        sw.Start();

        for (int i = 0; i < digits.Length; i++)
        {
            if (!stopDiagonals)
            {
                try
                {
                    sumOfDiagonals = SumOfDiagonals(i);
                }
                catch (Exception)
                {
                    stopDiagonals = true;
                }
            }
            if (!stopRows)
            {
                try
                {
                    sumOfRows = SumOfRows(i);
                }
                catch (Exception)
                {
                    stopRows = true;
                }
            }
            if (!stopCollumns)
            {
                try
                {
                    sumOfCollumns = SumOfCollumns(i);
                }
                catch (Exception)
                {

                    stopCollumns = true;
                }
            }
            if (maxSum[0] < sumOfCollumns)
            {
                maxSum[0] = sumOfCollumns;
            }
            if (maxSum[1] < sumOfDiagonals)
            {
                maxSum[1] = sumOfDiagonals;
            }
            if (maxSum[2] < sumOfRows)
            {
                maxSum[2] = sumOfRows;
            }
        }

        sw.Stop();
        Console.WriteLine(maxSum.Max());

        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

    private static bool IsInMaxBounds(int number, int max)
    {
        int tolerance = (number/20)*20;
        return number <= max + tolerance;
    }

    private static bool IsInMinBounds(int number, int min)
    {
        int tolerance = (number / 20) * 20;
        return number >= min + tolerance;
    }

    private static IEnumerable<int> RowValues(int startingIndex, bool right)
    {
        List<int> rowValues = new List<int>();
        if (right && IsInMaxBounds(startingIndex,16))
        {
            for (int i = startingIndex + RowIncreasment; i >= startingIndex; i--)
            {
                rowValues.Add(int.Parse(digits[i]));
            }
        }
        else if (IsInMinBounds(startingIndex, 3))
        {
            for (int i = startingIndex - RowIncreasment; i <= startingIndex; i++)
            {
                rowValues.Add(int.Parse(digits[i]));
            }
        }
        return rowValues.Count != 4 ? new[] {0, 0, 0, 0} : rowValues.ToArray();
    }

    private static IEnumerable<int> CollumnValues(int startingIndex, bool top)
    {
        List<int> collumnValues = new List<int>();
        if (!top && IsInMaxBounds(startingIndex, 380))
        {
            for (int i = startingIndex + CollumnIncreasment; i >= startingIndex; i -= CollumnIncreasment / 3)
            {
                collumnValues.Add(int.Parse(digits[i]));
            }
        }
        else if (top && IsInMinBounds(startingIndex,60))
        {
            for (int i = startingIndex - CollumnIncreasment; i <= startingIndex; i += CollumnIncreasment / 3)
            {
                collumnValues.Add(int.Parse(digits[i]));
            }
        }
        return collumnValues.Count != 4 ? new[] { 0, 0, 0, 0 } : collumnValues.ToArray();
    }

    private static IEnumerable<int> DiagonalValues(int startingIndex, bool leftDiagonal)
    {

        List<int> diagonalValues = new List<int>();
        if (leftDiagonal && IsInMaxBounds(startingIndex, 19) && IsInMinBounds(startingIndex, 3) &&
            IsInMaxBounds(startingIndex, 323))
        {
            for (int i = 57 + startingIndex; i >= startingIndex; i -= 19)
            {
                diagonalValues.Add(int.Parse(digits[i]));
            }
        }
        else if (!leftDiagonal && IsInMinBounds(startingIndex, 0) && IsInMaxBounds(startingIndex, 16) &&
                 IsInMaxBounds(startingIndex, 317))
        {
            for (int i = startingIndex; i <= startingIndex + 63; i += 21)
            {
                diagonalValues.Add(int.Parse(digits[i]));
            }
        }
        return diagonalValues.Count != 4 ? new[] { 0, 0, 0, 0 } : diagonalValues.ToArray();
    }

    private static int SumOfDiagonals(int currentNumber)
    {
        IEnumerable<int> outputSumOfLeftDiagonals = DiagonalValues(currentNumber, true);
        IEnumerable<int> outputSumOfRightDiagonals = DiagonalValues(currentNumber, false);
        int sumOfRightDiagonals = outputSumOfRightDiagonals.Aggregate(1, (current, diagonal) => current*diagonal);
        int sumOfLeftDiagonals = outputSumOfLeftDiagonals.Aggregate(1,(current, diagonal) => current * diagonal);
        return sumOfLeftDiagonals > sumOfRightDiagonals ? sumOfLeftDiagonals : sumOfRightDiagonals;
    }

    private static int SumOfRows(int currentNumber)
    {
        IEnumerable<int> outputSumOfLeftRows = RowValues(currentNumber, false);
        int sumOfLeftRows = outputSumOfLeftRows.Aggregate(1, (current, row) => current * row);
        IEnumerable<int> outputSumOfRightRows = RowValues(currentNumber, true);
        int sumOfRightRows = outputSumOfRightRows.Aggregate(1, (current, row) => current*row);
        return sumOfLeftRows > sumOfRightRows ? sumOfLeftRows : sumOfRightRows;
    }

    private static int SumOfCollumns(int currentNumber)
    {
        IEnumerable<int> outputSumOfTopCollumns = CollumnValues(currentNumber, true);
        IEnumerable<int> outputSumOfBottomCollumns = CollumnValues(currentNumber, false);
        int sumOfTopCollumns = outputSumOfTopCollumns.Aggregate(1,(current, collumn) => current * collumn);
        int sumOfBottomCollumns = outputSumOfBottomCollumns.Aggregate(1,(current, collumn) => current * collumn);
        return sumOfTopCollumns > sumOfBottomCollumns ? sumOfTopCollumns : sumOfBottomCollumns;
    }
}

Can you please add the full description of what the code is supposed to do? — nhgrif
– nhgrif, Commented Apr 3, 2016 at 23:11
If you glance at my solution's Java code, you might be left speechless by its brevity: github.com/nayuki/Project-Euler-solutions/blob/master/java/… — Nayuki
– Nayuki, Commented Apr 4, 2016 at 2:46

janos · Accepted Answer · 2016-04-18 21:55:35Z

Don't use exceptions for flow control

The purpose of this code is to ignore the sum of a row if an exception is thrown during calculation:

if (!stopRows)
{
    try
    {
        sumOfRows = SumOfRows(i);
    }
    catch (Exception)
    {
        stopRows = true;
    }
}

There are several problems with this approach:

It's a bad practice to throw generic Exception instead of something more specific
It's a bad practice to catch generic Exception instead of something more specific
Exceptions are designed to handle unexpected conditions, not for simple flow control
An exception is never actually thrown

You can replace the above code with this single line:

sumOfRows = SumOfRows(i);

The try-catch for summing columns and diagonals are bad too. You should eliminate them. That won't be as simple as with rows, because during these operations there may be exceptions. You need to understand where those exceptions come from: index out of bounds. The right way to handle these is to check boundaries and thereby eliminate index of bounds exceptions. I will give you some hints in a later section.

Overcomplicated code

This method is really unnecessarily complicated:

private static int SumOfRows(int currentNumber)
{
    IEnumerable<int> outputSumOfLeftRows = RowValues(currentNumber, false);
    int sumOfLeftRows = outputSumOfLeftRows.Aggregate(1, (current, row) => current * row);
    IEnumerable<int> outputSumOfRightRows = RowValues(currentNumber, true);
    int sumOfRightRows = outputSumOfRightRows.Aggregate(1, (current, row) => current*row);
    return sumOfLeftRows > sumOfRightRows ? sumOfLeftRows : sumOfRightRows;
}

You are calculating products from left, and also from right. But the calculations from left and right will be the same, so it's enough to do one of them: from left only, for example. So we can simplify the method to this:

private static int SumOfRows(int currentNumber)
{
    IEnumerable<int> outputSumOfLeftRows = RowValues(currentNumber, false);
    int sumOfLeftRows = outputSumOfLeftRows.Aggregate(1, (current, row) => current * row);
    return sumOfLeftRows;
}

You can further simplify this by cutting out the unnecessary local variables:

private static int SumOfRows(int currentNumber)
{
    return RowValues(currentNumber, false)
             .Aggregate(1, (current, row) => current * row);
}

And since it's enough to sum from left, you can simplify RowValues accordingly, eliminate the bool right parameter.

You can do similarly for SumOfCollumns:

private static int SumOfCollumns(int currentNumber)
{
    return CollumnValues(currentNumber, true)
             .Aggregate(1,(current, collumn) => current * collumn);
}

And also adjust CollumnValues accordingly.

In case of the diagonals, you do need to calculate from both the left and the right. However, as mentioned earlier, you should check the bounds rather than letting the process end in an index out of bounds exception.

Naming

The method and variables should be improved. Most notably, the program is about calculating products, so all the methods and variables with "sum" should be renamed to "product".

Also, column is misspelled as "collumn" at many places.

Finding the max value

You really don't need an int[3] to store the max values of the row, column, diagonal products. A single int and some Math.Max calls could do it. So instead of this:

if (maxSum[0] < sumOfCollumns)
{
    maxSum[0] = sumOfCollumns;
}
if (maxSum[1] < sumOfDiagonals)
{
    maxSum[1] = sumOfDiagonals;
}
if (maxSum[2] < sumOfRows)
{
    maxSum[2] = sumOfRows;
}

You could simplify to this:

max = Math.Max(max, sumOfCollumns);
max = Math.Max(max, sumOfRows);
max = Math.Max(max, sumOfDiagonals);

brichins · Accepted Answer · 2016-04-20 03:14:31Z

First of all, this looks like a great start, especially as you say you are self-taught (in your profile) - not a bad running time! Realize though that even in this age of plentiful memory and fast processors, a millisecond is not insignificant. Especially in any core functionality - code that will get called constantly as a program runs.

So, here are some things that I see that could be optimized:

1. Only parse the numbers once
You currently call Parse in 6 different places, all inside loops. Given that each number is used up to 4 times in each loop (indices 0-3 in successive windows), you are parsing each number up to 24 times.

Instead, parse the numbers once up-front and put them into a 20x20 array - int[,]. Or you could stick with a one-dimensional array and manually calculate offsets as you are doing now, but I think 2D is simpler, as explained below in item 5.

2. Eliminate unneeded calculations
There are really only 4 directions, not 8: vertical, horizontal, and two diagonals (/ or \). You don't need to go both ways along each line, e.g. columns up and columns down - the product of the 4 numbers is the same both directions. This will eliminate half of the code from your windowing functions - no more if(right) else with duplicate loops inside.

3. Re-use variables instead of recreating them
Each time you call your static methods (e.g. RowValues), you create the same new variables (List<int> rowValues = new List<int>();). You could make this List<int> a private field instead and allocate it once, then just write over it each time. Incidentally, the default size for a new List is 10 elements, you could initiallize it to the required 4 instead since that's known up front (new List<int>(4)).

4. Avoid unneeded casting/converting of types
Each of your IEnumerable<int> methods starts off with a List, then ends by converting it to an Array. A List is already an IEnumerable, no need to convert it and copy values to a newly-created Array before returning.

5. Restructure logic flow to make use of known boundaries
You currently are checking the start and end indices before each windowing loop, then seeing if your current window falls completely inside the original array - e.g., a row window doesn't wrap onto the next line. At least, I assume this is what the IsIn[Min/Max]Bounds functions are doing?

However, you know that instead of a 1D, 400-length integer array, you really have a 2D 20x20 array. If you use that arrangement instead, you can just loop over a known size (for (int i = 0; i < 20; i++)) and be guaranteed to stay inside the bounds. Depending on your exact structure, you would actually want i<16 because that is the beginning of your final 0-indexed window [16,17,18,19].

This also eliminates the use of expected "Exceptions" for logic control, as well as "magic number" statements like 57 + index and i -= 19.

6. Don't store intermediate results that don't do anything
Each scan through the grid is storing a maximum for each direction, then comparing them internally. Then finally you compare all the results to find the One True Number.

However, you only ever plan to have one final maximum, and don't ever need the other numbers again. Use a single "global" variable and just keep replacing it as you check each product: MyMaxInt = Math.Max(MyMaxInt, contender). Of course if you were aggregating more complex objects, intermediate results can be useful for simplicity or speed, but for something as simple as a single int there's no need to track it in multiple places.

On a related note, you could actually eliminate the need to copy out values to a List<int> entirely and instead Aggregate over an iterator block that provides a moving window on the original data. I highly recommend Jon Skeet's excellent book C# in Depth for an explanation on iterator blocks, as well as C# in general. Well worth the price of admission to save the time searching StackOverflow / Google.

7. Keep it DRY (Don't Repeat Yourself)
Your last three methods (SumOf[WindowDirection]) are basically all doing the same thing - find all the windows of a given direction, get the resulting mathematical products, and return the maximum. You could instead have a single function that accepts any 4-digit window, computes the product, and sets the new maximum to date.

However, this becomes tricky and figuring out the windowing for reuse may end up making the code less readable than having separate functions, without any significant benefits. This would be a matter of preference and very possibly premature optimization.

Thank you a lot for the answer I will make sure to remember those tips for my future project ! — Denis
– Denis, Commented Apr 20, 2016 at 13:35

Stack Exchange Network

Project Euler #11 Largest product in a grid

Question

Explanation

2 Answers 2

Don't use exceptions for flow control

Overcomplicated code

Naming

Finding the max value

You must log in to answer this question.

Hot Network Questions

Project Euler #11 Largest product in a grid

Question

Explanation

2 Answers 2

Don't use exceptions for flow control

Overcomplicated code

Naming

Finding the max value

You must log in to answer this question.

Related

Hot Network Questions