Question: 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?

Answer: Given any connected shape with n tiles, you can:  Find the tiles with the the smallest y coordinate, and choose the one of those with the smallest x coordinate. This is the "starting tile" Traverse the remaining tiles using BFS. As you consider the neighboring cells of each tile, keep track of which ones you examine, mark them seen, and only examine cells you haven't seen before. When you examine a new (unseen) cell:  If there's a tile in the cell, then output 1 and add the tile to your BFS queue; Otherwise write a 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)]