Problem statement
In the 20×20 grid below, four numbers along a diagonal line have been marked in red (bold).
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 the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
Thoughts
We can consider each position one at a time, but only need to calculate the down, right, right-down, and right-up directions; the other leftwards directions will be the same, just from a different starting position.
Solution
Iterate all the numbers, calculate the down/right/right-down/right-up product as long as we aren't within 4 places of the end/bottom.
Define the values we're working with.
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define GRID_WIDTH 20
#define GRID_HEIGHT 20
#define GROUP_LEN 4
#define GRID_SIZE GRID_WIDTH *GRID_HEIGHT
/* My editor has formatted these by line length, so it's not 20x20 anymore! */
int nums[GRID_SIZE] = {
8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77,
91, 8, 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,
4, 56, 62, 0, 81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88,
30, 3, 49, 13, 36, 65, 52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56,
1, 32, 56, 71, 37, 2, 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, 3, 45, 2,
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,
2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21, 24, 55,
58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31,
33, 95, 78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14,
9, 53, 56, 92, 16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17,
54, 24, 36, 29, 85, 57, 86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37,
44, 60, 21, 58, 51, 54, 17, 58, 19, 80, 81, 68, 5, 94, 47, 69, 28, 73,
92, 13, 86, 52, 17, 77, 4, 89, 55, 40, 4, 52, 8, 83, 97, 35, 99, 16,
7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66, 88, 36, 68, 87, 57, 62,
20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69, 4, 42, 16, 73,
38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36, 20, 69,
36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16,
20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,
5, 54, 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1,
89, 19, 67, 48
};
Define functions to compute the products in different directions
int get_horizontal(int row, int col, int offset)
{
return nums[(row * GRID_WIDTH) + col + offset];
}
int get_vertical(int row, int col, int offset)
{
return nums[(row + offset) * GRID_WIDTH + col];
}
int get_right_down(int row, int col, int offset)
{
return nums[(row + offset) * GRID_WIDTH + col + offset];
}
int get_right_up(int row, int col, int offset)
{
return nums[(row - offset) * GRID_WIDTH + col + offset];
}
Iterate each row and column to compute each direction product.
int main()
{
double largest_product = 0;
for (int row = 0; row < GRID_HEIGHT; row++) {
/* Determine whether there's enough space on each of the sides to calculate in
* that direction */
bool enough_below = row <= GRID_HEIGHT - GROUP_LEN;
bool enough_above = row >= GROUP_LEN;
for (int col = 0; col < GRID_WIDTH; col++) {
bool enough_ahead = col <= GRID_WIDTH - GROUP_LEN;
double h_product, v_product, rd_product, ru_product;
h_product = v_product = rd_product = ru_product = 1;
/* Each group is the same length, so we only need to loop once */
for (int i = 0; i < GROUP_LEN; i++) {
if (enough_ahead) {
h_product = h_product *
get_horizontal(row, col, i);
}
if (enough_below) {
v_product = v_product *
get_vertical(row, col, i);
}
if (enough_ahead && enough_below) {
rd_product =
rd_product *
get_right_down(row, col, i);
}
if (enough_ahead && enough_above) {
ru_product = ru_product *
get_right_up(row, col, -i);
}
}
/* Save the value if any of the products are larger */
if (h_product > largest_product) {
largest_product = h_product;
}
if (v_product > largest_product) {
largest_product = v_product;
}
if (rd_product > largest_product) {
largest_product = rd_product;
}
if (ru_product > largest_product) {
largest_product = ru_product;
}
}
}
printf("%.0f", largest_product);
}