Greatest product along diagonal of a 20 by 20 grid

[king_koder]

I wrote the following function in Python3 for finding the largest product of numbers along the diagonal(top-left to right-bottom).

def GreatestOnDiagonal(data):
    '''Returns greatest product possible by multiplying 4 numbers in the diagonal
'''
    grtProduct=1
    for item in data:
        for n in item:
            product=1
  

            for r in range(0,4):
                try:
                    d=data.index(item)+r
                    e=item.index(n)+r
                    product*=data[d][e]

                except IndexError:
                    break
            #
        if product>grtProduct:grtProduct=product
    return grtProduct

The parameter passed here,data, is a list of numbers from the grid in http://projecteuler.net/index.php?section=problems&id=11 . Each line is a list nested into the main list, data.

What I've tried to do here is-
Take 08 ,for example, which lies first on the grid. The position of 08 is 0 in the 0th list of the 'data' list. So the number along the diagonal would be the term 1 of the 1st list of the data list. Then the third number would be on the position 2 of the 2nd......... and so on. Right?

This seems to work fine for the numbers at the beginning, but at the end what the function has basically done is generate the row, which obviously would result in an error. Can someone guide me through this?? Thanks.

[slate]

list.index(x)
Return the index in the list of the first item whose value is x. It is an error if there is no such item.

The expression: data.index(item) does not return always the items index. If you have many equal items, then the first will be returned.

I recommend the following:

def GreatestOnDiagonal(data):
    '''Returns greatest product possible by multiplying 4 numbers in the diagonal
'''
    grtProduct=1
    for d,item in enumerate(data):
        for e,n in enumerate(item):
            product=1
            for r in range(0,4):
                try:
                    product*=data[d+r][e+r]

                except IndexError:
                    break
            #
        if product>grtProduct:grtProduct=product
    return grtProduct

[king_koder]

Hello slate,
I replaced my code with yours but the program shows the same result. I inserted a print(data[d+r][e+r]) after the product*=data[d+r][e+r] line, but it shows the same result as before.

[pyTony]

Move slate's line 15 to else part of try except. Maybe that fixes the issue of maximum (untested)

[king_koder]

@tonyjv- That still doesn't solve the problem:(

[slate]

Maybe the following clarifies the problem.

s='''
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
'''
data=[[cell for cell in line.split()] for line in s.split("\n") if line]
def GreatestOnDiagonal(data):
    '''Returns greatest product possible by multiplying 4 numbers in the diagonal
'''
    grtProduct=1
    for d,item in enumerate(data):
        for e,n in enumerate(item):
            product=1
            out=list()
            for r in range(0,4):
                try:
                    product*=int(data[d+r][e+r])
                    out.append(data[d+r][e+r])
                except IndexError:
                    break
            else:#executed when loop exits without break
                print(",".join(out)) # prints the diagonal lines
                if product>grtProduct:grtProduct=product
    return grtProduct

print(GreatestOnDiagonal(data))

[pyTony]

I meant this:

s='''
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
'''
data=[[cell for cell in line.split()] for line in s.split("\n") if line]
def GreatestOnDiagonal(data):
    '''Returns greatest product possible by multiplying 4 numbers in the diagonal
'''
    grtProduct=1
    for d,item in enumerate(data):
        for e,n in enumerate(item):
            product=1
            out=list()
            for r in range(0,4):
                try:
                    product*=int(data[d+r][e+r]) # this is wrong place for int, should be int allready
                except IndexError:
                    break
                else: # executed when try gives no error 
                    out.append(data[d+r][e+r])
            else:
                # only four numbers products, not the breaks,
                # which are shorter and never max with positive numbers
                if product>grtProduct:
                    grtProduct=product
                    print out # new max (debug)
    return grtProduct

print(GreatestOnDiagonal(data))

[slate]

# this is wrong place for int, should be int allready # executed when try gives no error

You are right. But cannot solve every problem in one strike :).
Thewhole solution to this euler problem is significant shorter. Spoiler

[Gribouillis]

You are right. But cannot solve every problem in one strike :). The whole solution to this euler problem is significant shorter. Spoiler

I have an even shorter whole solution

from functools import reduce
from operator import mul
s='''
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
'''
data=[[int(cell) for cell in line.split()] for line in s.split("\n") if line]

def gen_tuples(x):
    four = list(range(4))
    for i in range(16):
        for j in range(16):
            yield (x[i][j+k] for k in four)
            yield (x[i+k][j] for k in four)
            yield (x[i+k][j+k] for k in four)

print(max(reduce(mul, t) for t in gen_tuples(data)))
""" my output -->
51267216
"""

[pyTony]

Neater than mine probably, but your result does not agree:

import pretty
numbers_grid = """
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"""
numbers_grid=[map(int, line.split()) for line in numbers_grid.splitlines() if line]

def product(numbers):
    res = 1
    for number in numbers:
        res *= number
    return res

diag1 = (tuple(numbers_grid[i+k][j+k] for k in range(4))
                    for i in range(16)
              for j in range(16))

diag2 = (tuple(numbers_grid[i+k][j-k] for k in range(4))
                    for i in range(16)
              for j in range(3,20))

answer = max(max(product(row[start:start+4])
                 for start in range(20-4)
                 for row in numbers_grid),
             max(product(row[start:start+4])
                 for start in range(20-4)
                 for row in zip(*numbers_grid)),
             max((product(d),d) for d in diag1),
             max((product(d),d) for d in diag2))

print 'Answer is', answer
""" Result:
Answer is (70600674, (89, 94, 97, 87))
"""

[slate]

Perfection (in design) is achieved not when there is nothing more to add, but rather when there is nothing more to take away.

-- Antoine de Saint-Exupéry

[slate]

I have an even shorter whole solution

from functools import reduce
from operator import mul
s='''
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
'''
data=[[int(cell) for cell in line.split()] for line in s.split("\n") if line]

def gen_tuples(x):
    four = list(range(4))
    for i in range(16):
        for j in range(16):
            yield (x[i][j+k] for k in four)
            yield (x[i+k][j] for k in four)
            yield (x[i+k][j+k] for k in four)

print(max(reduce(mul, t) for t in gen_tuples(data)))
""" my output -->
51267216
"""

Except you forgot one direction ... :)

[Gribouillis]

Neater than mine probably, but your result does not agree:

""" Result:
Answer is (70600674, (89, 94, 97, 87))
"""

We don't have the same answer because I didn't take the rising diagonals. To take them into account, add yield (x[i+3-k][j+k] for k in four) at line 34 in my solution.

[king_koder]

else: # executed when try gives no error

Thanks,finally got the right answer after I used the modification you suggested. However I'm still not fully sure I understand ho your code actually works. When try gives an error, except is executed, right? So, why is the else necessary??

Also, what purpose does the other else in your(tonyjv)'s code serve?

[pyTony]

If we have exception from one line only that should be in try. Those lines from which we are not catching exception after try did not cause exception, should go to else part of try statement. The else part of for which is executed only if break is not executed(analoguous to the try explained before only break instead of exception) I think I put comment there that I use the else for maximum because do not consider shorter than four sequence sums. In exceptional case the sum of two numbers coud be maximum but I understood rules so.

[king_koder]

Thanks, that really helped clear my confusion!!