Project Euler Problem 11

Question

Problem 11:

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 the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Is it possible to use NumPy or any other library from Anaconda3 to make this code more readable?

from numba import jit

LIST =[[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]]

@jit
def main():
    MAX = -1
    TEMP_VAL = 0
    for i in range(0,20):
        for j in range(0,20):
            if i < 17:
                TEMP_VAL = LIST[i][j] * LIST[i+1][j] * LIST[i+2][j] * LIST[i+3][j]
            if TEMP_VAL > MAX:
                MAX = TEMP_VAL
        if j < 17:
            TEMP_VAL = LIST[i][j] * LIST[i][j+1] * LIST[i][j+2] * LIST[i][j+3]
            if TEMP_VAL > MAX:
                MAX = TEMP_VAL
        if i < 17 and j < 17:
            TEMP_VAL = LIST[i][j] * LIST[i+1][j+1] * LIST[i+2][j+2] * LIST[i+3][j+3]
            if TEMP_VAL > MAX:
                MAX = TEMP_VAL
        if i < 17 and j > 2:
            TEMP_VAL = LIST[i][j] * LIST[i+1][j-1] * LIST[i+2][j-2] * LIST[i+3][j-3]
            if TEMP_VAL > MAX:
                MAX = TEMP_VAL
    print(MAX)

if __name__=="__main__":
    main()

(The correct answer is 70600674)

Answer 1

If LIST were a two-dimensional numpy array, you could use LIST[i,:] to get the ith row, LIST[:,i] to get the ith column, numpy.diagonal(LIST, i) to get the diagonal i places above the main diagonal (where -17 < i and i < 17 in order to restrict to diagonals containing at least four cells), and numpy.diagonal(numpy.flipud(LIST), i) to get the left diagonal i places below the main left diagonal.

Each of the four operations in the previous paragraph returns either an array or an array view. Every set of four numbers that you wanted to look at will show up as four consecutive values in one of these arrays or array views, so you just need to look at each product of four consecutive integers within each array or array view.

Answer 2

A few remarks on your current code:

1. You should have a look at Python's official style-guide, PEP8. It recommends using lower_case for variable names.

2. range implicitly takes 0 as its first argument, so range(0, 20) and range(20) are equivalent.

3. Fore re-usability (I know, not such a big concern here) you should give your function a name that explains what it does. You should also make it return the value, instead of printing it and take the matrix as an argument.

4. There seems to be an indentation error (?). Your last three if blocks are not in the inner for loop. Because of this, j is always 19, since the inner for loop has finished, so the first two blocks are actually unreachable.