https://projecteuler.net/problem=11 Here is the question:
int grid[20][20] =
{
{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}
};
What is the greatest product of four adjacent numbers in the "same direction" (up, down, left, right, or diagonally) in the 20 by 20 grid? At first I read the question wrong and did not see the "same direction" part. I thought the rule is every number has to be adjacent to at least one other number in the grid, not at most.
I was able to solve it fairly quickly (i also used ChatGpt to fix the syntax errors) because I am kind of new to this.
Solution:
#include <stdio.h>
// Function to find the maximum product of four adjacent numbers in a grid
int findMaxProduct(int grid[20][20], int* pos)
{
int maxProduct = 0;
// Check horizontally
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 20 - 3; j++)
{
int product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3];
printf("Checking horizontally at (%d, %d) -> product: %d\n", i, j, product);
if (product > maxProduct)
{
maxProduct = product;
pos[0] = i; pos[1] = j;
pos[2] = i; pos[3] = j + 1;
pos[4] = i; pos[5] = j + 2;
pos[6] = i; pos[7] = j + 3;
printf("New max horizontal product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
}
}
}
// Check vertically
for (int i = 0; i < 20 - 3; i++)
{
for (int j = 0; j < 20; j++)
{
int product = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j];
printf("Checking vertically at (%d, %d) -> product: %d\n", i, j, product);
if (product > maxProduct)
{
maxProduct = product;
pos[0] = i; pos[1] = j;
pos[2] = i + 1; pos[3] = j;
pos[4] = i + 2; pos[5] = j;
pos[6] = i + 3; pos[7] = j;
printf("New max vertical product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
}
}
}
// Check diagonally (down-right)
for (int i = 0; i < 20 - 3; i++)
{
for (int j = 0; j < 20 - 3; j++)
{
int product = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3];
printf("Checking diagonally down-right at (%d, %d) -> product: %d\n", i, j, product);
if (product > maxProduct)
{
maxProduct = product;
pos[0] = i; pos[1] = j;
pos[2] = i + 1; pos[3] = j + 1;
pos[4] = i + 2; pos[5] = j + 2;
pos[6] = i + 3; pos[7] = j + 3;
printf("New max diagonal down-right product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
}
}
}
// Check diagonally (down-left)
for (int i = 0; i < 20 - 3; i++)
{
for (int j = 3; j < 20; j++)
{
int product = grid[i][j] * grid[i + 1][j - 1] * grid[i + 2][j - 2] * grid[i + 3][j - 3];
printf("Checking diagonally down-left at (%d, %d) -> product: %d\n", i, j, product);
if (product > maxProduct)
{
maxProduct = product;
pos[0] = i; pos[1] = j;
pos[2] = i + 1; pos[3] = j - 1;
pos[4] = i + 2; pos[5] = j - 2;
pos[6] = i + 3; pos[7] = j - 3;
printf("New max diagonal down-left product found: %d at (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
maxProduct, pos[0], pos[1], pos[2], pos[3], pos[4], pos[5], pos[6], pos[7]);
}
}
}
return maxProduct;
}
int main(void)
{
int grid[20][20] =
{
{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}
};
int pos[8]; // To store the positions of the 4 adjacent numbers with the highest product
int maxProduct = findMaxProduct(grid, pos);
printf("The maximum product of four adjacent numbers is %d.\n", maxProduct);
printf("The positions of these numbers are:\n");
for (int i = 0; i < 8; i += 2)
{
printf("(%d, %d)\n", pos[i], pos[i + 1]);
}
return 0;
}
What if we consider numbers that aren’t in the same direction?. The only rule is every number has to be adjacent to one other number at least instead only being adjacent to one other number. Like the answer itself could be 4 numbers that are all adjacent to each other like a square 2 by 2 matrix?
Now we have to search for a lot more things. Manually finding shapes in python
def is_in_bounds(x, y, rows, cols):
return 0 <= x < rows and 0 <= y < cols
def generate_combinations(x, y):
return
[
[(x, y), (x+1, y), (x+2, y), (x+3, y)], # Horizontal line
[(x, y), (x, y+1), (x, y+2), (x, y+3)], # Vertical line
[(x, y), (x+1, y+1), (x+2, y+2), (x+3, y+3)], # Diagonal down-right
[(x, y), (x-1, y+1), (x-2, y+2), (x-3, y+3)], # Diagonal down-left
[(x, y), (x+1, y), (x, y+1), (x+1, y+1)], # 2x2 square
[(x, y), (x+1, y), (x+2, y), (x+2, y+1)], # L-shape 1
[(x, y), (x, y+1), (x, y+2), (x+1, y+2)], # L-shape 2
[(x, y), (x+1, y), (x+2, y), (x, y+1)], # L-shape 3
[(x, y), (x, y+1), (x, y+2), (x+1, y)], # L-shape 4
[(x, y), (x+1, y), (x+2, y), (x+1, y+1)], # T-shape 1
[(x, y), (x, y+1), (x, y+2), (x+1, y+1)], # T-shape 2
[(x, y), (x+1, y), (x+1, y+1), (x+1, y+2)], # T-shape 3
[(x, y), (x, y+1), (x-1, y+1), (x+1, y+1)] # T-shape 4
]
def calculate_product(grid, combination):
product = 1
for x, y in combination:
product *= grid[x][y]
return product
def find_max_product(grid):
max_product = 0
max_combination = []
rows = len(grid)
cols = len(grid[0])
for i in range(rows):
for j in range(cols):
combinations = generate_combinations(i, j)
valid_combinations = [comb for comb in combinations if all(is_in_bounds(x, y, rows, cols) for x, y in comb)]
for comb in valid_combinations:
product = calculate_product(grid, comb)
print(f"Combination: {comb} => Values: {[grid[x][y] for x, y in comb]} => Product: {product}")
if product > max_product:
max_product = product
max_combination = comb
print(f"Max product combination: {max_combination} => Product: {max_product}")
return max_product
# Example usage
grid = [[int(x) for x in line.split()] for line in """
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
""".strip().split('\n')]
print(find_max_product(grid))
But if the problem asks for n=5; I will need to manually find more shapes on pen and paper. Is there another way to find all possible "n" number combinations(where at leas one number is adjacent to another one) . Do we have a formula for this? where I plug in n and it will tell me how many possible shapes are there?
Given any connected shape with n tiles, you can:
y coordinate, and choose the one of those with the smallest x coordinate. This is the "starting tile"seen, and only examine cells you haven't seen before.1 and add the tile to your BFS queue;0.This procedure will produce a unique binary code for each tile.
If you want to find all possible tiles, you can use a recursive backtracking procedure that finds all shapes corresponding to possible outputs of this procedure:
# generate all shapes with n tiles
def genTiles(n):
if (n<1):
return []
alldirs=[]
# generate a list of all directions
for x in range(-1,2):
for y in range(-1,2):
if x!=0 or y!=0:
alldirs.append((x,y))
# we'll collect all the outputs here
ret=[]
# BFS q
q = [(0,0)]
# cells we've seen
seen = dict()
seen[(0,0)] = True
def expand(qpos, nleft, index):
if nleft < 1:
ret.append(q[:])
return
# find the next unseen cell
index -= 1
while True:
index += 1
if index >= len(alldirs):
qpos += 1
index = 0
if qpos >= len(q):
return
test = (
q[qpos][0] + alldirs[index][0],
q[qpos][1] + alldirs[index][1]
)
if test[1] < 0 or (test[1] == 0 and test[0] <= 0):
continue
if seen.get(test) != True:
break
seen[test] = True
# choose
q.append(test)
expand(qpos, nleft-1, index+1)
# unchoose
q.pop()
expand(qpos, nleft, index+1)
seen[test] = False
expand(0,n-1,0)
return ret
Add this test to print out all 110 shapes with 4 tiles.
# test
N = 4
shapes = genTiles(N)
print("there are {0} shapes with {1} tiles:".format(len(shapes), N))
for tile in shapes:
print(tile)
As you can see, allowing diagonal connections adds a lot of possibilities. Even for 3 tiles there are 20 shapes:
there are 20 shapes with 3 tiles:
[(0, 0), (-1, 1), (0, 1)]
[(0, 0), (-1, 1), (1, 0)]
[(0, 0), (-1, 1), (1, 1)]
[(0, 0), (-1, 1), (-2, 1)]
[(0, 0), (-1, 1), (-2, 2)]
[(0, 0), (-1, 1), (-1, 2)]
[(0, 0), (-1, 1), (0, 2)]
[(0, 0), (0, 1), (1, 0)]
[(0, 0), (0, 1), (1, 1)]
[(0, 0), (0, 1), (-1, 2)]
[(0, 0), (0, 1), (0, 2)]
[(0, 0), (0, 1), (1, 2)]
[(0, 0), (1, 0), (1, 1)]
[(0, 0), (1, 0), (2, 0)]
[(0, 0), (1, 0), (2, 1)]
[(0, 0), (1, 1), (0, 2)]
[(0, 0), (1, 1), (1, 2)]
[(0, 0), (1, 1), (2, 0)]
[(0, 0), (1, 1), (2, 1)]
[(0, 0), (1, 1), (2, 2)]