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 typeint
with 4 values which are the values of the first 4 adjacent numbers. The parameters arestartingIndex
which serve's as a starting point and a boolean variable to determine whether it should go left/right/top/bottom. InDiagonalValues
method the parameterbool 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
andIsInMaxBounds
they both take the same parametersint number
and one moreint
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 variableint tolerance = (number/20)*20
which 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 usingint
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 haveint 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 theIndexOutOfRange
, once they do that we know it's time to stop checking for specific direction.RowValues Method
If we have
startingIndex = 0
andright = true
the first 4 adjacent numbers are at indexes :0, 1, 2, 3
so thefor
loop will end atstartingIndex + RowIncreasment
whereRowIncreasment
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 thestartingIndex
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 thestartingIndex
is greater than 0, it has to be at least 3 in order to get 4 adjacent numbers.CollumnValues
If we have
startingIndex = 0
andtop = false
the first 4 adjacent numbers are at indexes :0, 20, 40, 60
so thefor
loop will start atstartingIndex + CollumnIncreasment
and end atstartingIndex
whereCollumnIncreasment
is 60 and it should decrease by60/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 thestartingIndex
to be at least 60 so that thefor
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 thefor
loop, now we have thestartingIndex
as our starting point, and we end atstartingIndex + 63
because the last number will be located atx + 21 * 3
where x is ourstartingIndex
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 thefor
loop, the starting point here will be19 * 3 + startingIndex
and it will end atstartingIndex
, 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;
}
}