It has been a while since I have attempted a project Euler problem, mainly because of university exams taking up the majority of my spare time, but today I managed to spare a few minutes to make an attempt at problem 11.
The Problem In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
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
The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
The Solution (Un-Optimized) So I did a brute force attempt at solving this problem in C# – I am sure there is possibly a more elegant way of solving this problem, but for now this is what I have got…
delegate int TableFunction(int x, int y, int[,] table);
class Program
{
private static int GetSumDown(int x, int y, int[,] table)
{
int result = 1;
int y1 = (y) % 20;
int y2 = (y + 1) % 20;
int y3 = (y + 2) % 20;
int y4 = (y + 3) % 20;
result *= table[y1, x];
result *= table[y2, x];
result *= table[y3, x];
result *= table[y4, x];
return result;
}
private static int GetSumUp(int x, int y, int[,] table)
{
int result = 1;
int y1 = (y) % 20;
int y2 = (y - 1) % 20;
int y3 = (y - 2) % 20;
int y4 = (y - 3) % 20;
if (y1 < 0) y1 = (20 - y1) % 20;
if (y2 < 0) y2 = (20 - y2) % 20;
if (y3 < 0) y3 = (20 - y3) % 20;
if (y4 < 0) y4 = (20 - y4) % 20;
result *= table[y1, x];
result *= table[y2, x];
result *= table[y3, x];
result *= table[y4, x];
return result;
}
private static int GetSumRight(int x, int y, int[,] table)
{
int result = 1;
int x1 = (x) % 20;
int x2 = (x + 1) % 20;
int x3 = (x + 2) % 20;
int x4 = (x + 3) % 20;
result *= table[y, x1];
result *= table[y, x2];
result *= table[y, x3];
result *= table[y, x4];
return result;
}
private static int GetSumLeft(int x, int y, int[,] table)
{
int result = 1;
int x1 = (x) % 20;
int x2 = (x - 1) % 20;
int x3 = (x - 2) % 20;
int x4 = (x - 3) % 20;
if (x1 < 0) x1 = (20 - x1) % 20;
if (x2 < 0) x2 = (20 - x2) % 20;
if (x3 < 0) x3 = (20 - x3) % 20;
if (x4 < 0) x4 = (20 - x4) % 20;
result *= table[y, x1];
result *= table[y, x2];
result *= table[y, x3];
result *= table[y, x4];
return result;
}
private static int GetSumDiagonalDownRight(int x, int y, int[,] table)
{
int result = 1;
int x1 = (x) % 20;
int x2 = (x - 1) % 20;
int x3 = (x - 2) % 20;
int x4 = (x - 3) % 20;
int y1 = (y) % 20;
int y2 = (y - 1) % 20;
int y3 = (y - 2) % 20;
int y4 = (y - 3) % 20;
if (y1 < 0) y1 = (20 - y1) % 20;
if (y2 < 0) y2 = (20 - y2) % 20;
if (y3 < 0) y3 = (20 - y3) % 20;
if (y4 < 0) y4 = (20 - y4) % 20;
if (x1 < 0) x1 = (20 - x1) % 20;
if (x2 < 0) x2 = (20 - x2) % 20;
if (x3 < 0) x3 = (20 - x3) % 20;
if (x4 < 0) x4 = (20 - x4) % 20;
result *= table[y1, x1];
result *= table[y2, x2];
result *= table[y3, x3];
result *= table[y4, x4];
return result;
}
private static int GetSumDiagonalDownLeft(int x, int y, int[,] table)
{
int result = 1;
int x1 = (x) % 20;
int x2 = (x - 1) % 20;
int x3 = (x - 2) % 20;
int x4 = (x - 3) % 20;
int y1 = (y) % 20;
int y2 = (y + 1) % 20;
int y3 = (y + 2) % 20;
int y4 = (y + 3) % 20;
if (y1 < 0) y1 = (20 - y1) % 20;
if (y2 < 0) y2 = (20 - y2) % 20;
if (y3 < 0) y3 = (20 - y3) % 20;
if (y4 < 0) y4 = (20 - y4) % 20;
if (x1 < 0) x1 = (20 - x1) % 20;
if (x2 < 0) x2 = (20 - x2) % 20;
if (x3 < 0) x3 = (20 - x3) % 20;
if (x4 < 0) x4 = (20 - x4) % 20;
result *= table[y1, x1];
result *= table[y2, x2];
result *= table[y3, x3];
result *= table[y4, x4];
return result;
}
/// <summary>
/// Applies a function to every cell of a table and returns a result
/// </summary>
/// <param name="table"></param>
/// <param name="tableFunction"></param>
/// <returns></returns>
private static int[,] GenerateProcessedTable(int[,] table, TableFunction tableFunction)
{
int[,] result = new int[20, 20];
for (int x = 0; x < 20; x++)
{
for (int y = 0; y < 20; y++)
{
result[y, x] = tableFunction(x, y, table);
}
}
return result;
}
/// <summary>
/// Returns the largest cell in a table
/// </summary>
/// <param name="table"></param>
/// <param name="tableFunction"></param>
/// <returns></returns>
private static int GetLargestCellInTable(int[,] table)
{
int result = 0;
for (int x = 0; x < 20; x++)
{
for (int y = 0; y < 20; y++)
{
if (result <= table[y, x])
{
result = table[y, x];
}
}
}
return result;
}
static void Main(string[] args)
{
int[,] table = new int[20, 20]
{
{ 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 },
};
int NormalTable = GetLargestCellInTable(table);
int TableSumRight = GetLargestCellInTable(GenerateProcessedTable(table, GetSumRight));
int TableSumLeft = GetLargestCellInTable(GenerateProcessedTable(table, GetSumLeft));
int TableSumDown = GetLargestCellInTable(GenerateProcessedTable(table, GetSumDown));
int TableSumUp = GetLargestCellInTable(GenerateProcessedTable(table, GetSumUp));
int TableSumDiagonalDownRight = GetLargestCellInTable(GenerateProcessedTable(table, GetSumDiagonalDownRight));
int TableSumDiagonalDownLeft = GetLargestCellInTable(GenerateProcessedTable(table, GetSumDiagonalDownLeft));
Console.WriteLine(GenerateProcessedTable(table, GetSumDiagonalDownRight)[0, 0].ToString());
Console.WriteLine("Normal table : {0}", NormalTable);
Console.WriteLine("Right table : {0}", TableSumRight);
Console.WriteLine("Left table : {0}", TableSumLeft);
Console.WriteLine("Down table : {0}", TableSumDown);
Console.WriteLine("Up table : {0}", TableSumUp);
Console.WriteLine("Diagonal Right table : {0}", TableSumDiagonalDownRight);
Console.WriteLine("Diagonal Left table : {0}", TableSumDiagonalDownLeft);
Console.ReadLine();
}
}
