Project Euler #11 - C

Question:

In the 2020 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 2020 grid?

Solution:

Now this was a fun one! The obvious, super slow way to do this one is to find each maximum in successive loops... maximum product of left-to-right, then of top-to-bottom, then of diagonal-right, then of diagonal-left. But that requires 4 loops and loads of time to complete. My goal was to calculate all 4 of these products in each iteration, effectively cutting the time required to complete this program by 4. 

I decided that throwing the above matrix into a text file and using string.h functions would be cheating so I decided to create an array exactly as it appears visually, a 20 x 20 array of integers. I also decided that placing each item manually into the array was cheating. So, I turned it into a long string of 2-digit integers and loop through each value 1-by-1 and enter them into the array as we go. This requires a fairly ugly line of code which requires you to understand how strings are represented in C (which if you are reading this, I assume you understand). 

for (i = 0; i < size; i++)

{

for (j = 0; j < size; j++)

{

int str_2_int = (*(matrix_as_string + k) - '0') * 10 + *(matrix_as_string + k + 1) - '0';

matrix[j][i]  = str_2_int;  

k+=3; // jumps to beginning of next number

}

}

So, a quick explanation... i and j are used as the indices into the array: i for row, j for column. k is used as the offset into the string. The variable matrix_as_string I believe is self explanatory and is essentially a pointer to the first item in the string of integers. By adding the offsets k and k+1, we are essentially plucking out two consecutive integers. To turn a char into an int in C, you simply subtract '0'. The integer found at offset k should be the 10s digit and the integer at offset k+1 is our 1s digit, so all we need to do is multiply offset k by 10 and then add the two numbers together... voila! Our integer representation of the number is produced. To get to the next number we need to parse, we add 3 to the offset and begin the next iteration of the loop.

Now on to the confusing aspect of this problem (if you were confused before, just wait!): finding 4 products at a time. Namely, a left-right product, up-down product, diagonal-right product, and a diagonal-left product. The first three products can all be found from the same starting point in the matrix, but the last product cannot. Why? Well, just look at the problem. If you take a look at the top left corner in the array, there is no diagonal-left product. So the way I tackled this problem was to work from left->right and top->bottom for the first 3 products and from right->left top->bottom for the diagonal-left product. 

So now that we know how we are going to compute these products, we have to determine when the products should be calculated. By looking at the matrix, it can be seen that we stop calculating the left-right product when i > 16 (remember, index 0-19 for 20 item array), stop calculating up-down when j > 16, and stop calculating the diagonal-right when i > 16 OR j > 16. Since the diagonal left just moves in the opposite direction, it shares the same properties of i and j as the diagonal right but will just use different indices (as will be shown soon).

So, to simplify I will say that the variable 

stop = SIZE - 3. 

Then,

if ( j < stop)

calculate left-right

if ( i < stop )

calculate up-down

if ( j < stop && i < stop )

calculate diagonals

Now the last tricky part is getting the correct indices for each item. Left-right and up-down are simple as they are simply 4 consecutive numbers in one direction. The trick is to remember that in an array in C and most programming languages, the COLUMNS are listed before the ROWS! So:

lr_prod = matrix[j][i] * matrix[j+1][i] * matrix[j+2][i] * matrix[j+3][i];
ud_prod = matrix[j][i] * matrix[j][i+1] * matrix[j][i+2] * matrix[j][i+3];

dr_prod = matrix[j][i] * matrix[j+1][i+1] * matrix[j+2][i+2] * matrix[j+3][i+3];

dl_prod = matrix[size-(j+1)][i] * matrix[size-(j+2)][i+1] * matrix[size-(j+3)][i+2] * matrix[size-(j+4)][i+3];

Now that these four products can be calculated, we compare them to the highest product encountered thus far. If one of these products is higher, replace the current high product and continue to the next iteration. When the loops complete, our answer should appear. 

The complete code:

#include <stdio.h>
#define size 20


int max (int, int, int, int, int);


int main (void)
{
int matrix[size][size] = {{0}};
char * matrix_as_string = "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 high_prod = 0;


int i = 0;
int j = 0;
int k = 0;


for (i = 0; i < size; i++)
{
for (j = 0; j < size; j++)
{
int str_2_int = (*(matrix_as_string + k) - '0') * 10 + *(matrix_as_string + k + 1) - '0';
matrix[j][i]  = str_2_int;  
k+=3; 
}
}


/* MAIN LOOP*/

for (i = 0; i < size; i++) 
{
for (j = 0; j < size; j++)
{
int lr_prod = 0, ud_prod = 0, dr_prod = 0, dl_prod = 0;
int stop = size- 3;


if ( j < stop)
lr_prod = matrix[j][i] * matrix[j+1][i] * matrix[j+2][i] * matrix[j+3][i];


if ( i < stop )
ud_prod = matrix[j][i] * matrix[j][i+1] * matrix[j][i+2] * matrix[j][i+3];



if ( j < stop && i < stop )
{
dr_prod = matrix[j][i] * matrix[j+1][i+1] * matrix[j+2][i+2] * matrix[j+3][i+3];
dl_prod = matrix[size-(j+1)][i] * matrix[size-(j+2)][i+1] * matrix[size-(j+3)][i+2] * matrix[size-(j+4)][i+3];
}

high_prod = max(lr_prod, ud_prod, dr_prod, dl_prod, high_prod);


}
}


printf("The high product of any 4 adjacent numbers is: %d\n", high_prod);


return 1;
}


int max (int a, int b, int c, int d, int e)
{
a = (a > b) ? a : b;
a = (a > c) ? a : c;
a = (a > d) ? a : d;
a = (a > e) ? a : e;


return a; 
}

 If you made it through that, congratulate yourself! Now its time for a beer!