Greatest product in 20×20 grid – Problem 11

We are going to solve Problem 11 of Project Euler here. The problem is about the greatest product in the 20×20 grid. Learn how to solve it in python. Learn about problem 9 here.

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 greatest product in 20×20 grid Solution

We are looking at a fairly simple problem set here. Let’s discuss what it actually is.

As shown in the figure, whenever we are looking at one number, we would need to check eight directions to find the maximum product of that particular number. However, since we will visit all numbers, we will only need to check four different colored directions for each number, since the rest of the directions are already being checked when we visit(ed) another number.

project euler problem 11
project euler problem 11

numbersInProduct = 4
product = 0
inputSquare = readInput(filename)
for i in range(0, len(inputSquare)):
    for j in range(0, len(inputSquare)):
        tempProd = 0
        if (j < len(inputSquare) - numbersInProduct):
            tempProd = inputSquare[i, j]
            for k in (1, numbersInProduct):
                tempProd *= inputSquare[i, j + k]
            product = max(product, tempProd)

        if (i < len(inputSquare[1]) - numbersInProduct):
            tempProd = inputSquare[i, j]
            for k in range(1, numbersInProduct):
                tempProd *= inputSquare[i + k, j]
            product = max(product, tempProd)


        if ((i < len(inputSquare[0]) - numbersInProduct) && (j >= numbersInProduct)):
            tempProd = inputSquare[i, j]
            for k in range(1, numbersInProduct):
                tempProd *= inputSquare[i + k, j - k]
            product = max(product, tempProd)

        if ((j < len(inputSquare[0]) - numbersInProduct) && (i < inputSquare.GetLength(1) - numbersInProduct)):
            tempProd = inputSquare[i, j]
            for k in range(1, numbersInProduct):
                tempProd *= inputSquare[i + k, j + i]
            product = Math.Max(product, tempProd)
print(product)

Answer

The greatest product of 4 entries, is 70600674

Pin It on Pinterest