011. 网格中的最大乘积(largest product in a grid)

在下面这个20×20的网格中,对角线上相邻的四个元素已经用红色标记出来了,这四个数的乘积为26 × 63 × 78 × 14 = 1788696:

IMG

求在这个网格中,同一方向(上、下、左、右以及对角线)相邻四个元素最大乘积。

分析:此题似乎没有什么讨巧的简便算法,先将数据存入到一个嵌套列表当中,然后依次遍历每个元素,求它每个方向上相邻四个元素(如果有的话,需要条件判断)的乘积,存入到结果列表中,然后求最大值。

with open('euler/ep11.txt','r') as f:
    data = [map(int, s.split()) for s in f.readlines()]

def grid_largest_prod(data):
    import numpy as np
    length = len(data)
    res = np.zeros((length,length))
    right = down = down_right = left_down = 0
    for i in range(length):
        for j in range(length):
            right_exist = all([x<length for x in [i,i+1,i+2,i+3]])
            down_exist = all([x<length for x in [j,j+1,j+2,j+3]])
            left_exist = all([x>=0 for x in [i,i-1,i-2,i-3]])
            if right_exist:
                right = data[i][j]*data[i+1][j]*data[i+2][j]*data[i+3][j]
            if down_exist:
                down = data[i][j]*data[i][j+1]*data[i][j+2]*data[i][j+3]
            if right_exist and down_exist:
                down_right = data[i][j]*data[i+1][j+2]*data[i+2][j+2]*data[i+3][j+3]
            if left_exist and down_exist:
                left_down = data[i][j]*data[i-1][j+1]*data[i-2][j+2]*data[i-3][j+3]
            res[i][j] = max(right,down,down_right,left_down)
    max_res = np.max(res)
    return max_res

print(grid_largest_prod(data))