Project Euler #11 in python

Question

我正在尝试做项目欧拉#11 (http://projecteuler.net/problem=11)，但我一直错误地得到51267216作为我的答案，我不知道为什么。现在我首先将网格格式化为2d数组，然后遍历所有数字，不包括外面的3。然后我迭代8个不同的方向并对它们进行测试。如果它比当前最大的大，那么我将其存储为"top"，欢迎任何帮助。

import pprint
def neg(l):
    for a in l:
        if a<0:
            return True
    return False
tg="""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"""
grid=tg.split("n")
for a in range(0, len(grid)):
    i=grid[a]
    i=i.split(" ")
    for b in range(0, len(i)):
        i[b]=int(i[b])
    grid[a]=i
top=0
for y in range(0, 19):
    for x in range(0, 19):
        for b in range(-1, 2):
            for c in range(-1, 2):
                if b+c!=0:
                    try:
                        factors=[grid[x][y],grid[x+b][y+c],grid[x+(b*2)][y+(c*2)],grid[x+(b*3)][y+(c*3)]]
                        if not neg(factors):
                            cur=grid[x][y]*grid[x+b][y+c]*grid[x+(b*2)][y+(c*2)]*grid[x+(b*3)][y+(c*3)]
                            if cur>top:
                                top=cur
                    except IndexError:
                        pass

print(top)

Answer 1

你有两个主要问题，第一:

except IndexError:

不会捕获所有无效的四元组，因为Python列表允许负索引(list[-k]是list[len(list)-k])，所以您还可以检查围绕网格末端的四元组。

,

if b+c!=0:

根本不考虑一个方向——最大积所在的方向。查找排除(0,0)的正确条件

第三(是的，我知道我上面说了两个，但这可能不是主要的)，

for b in range(-1, 2):
    for c in range(-1, 2):

检查同一方向两次，一次为(b,c)，一次为(-b,-c)。

Answer 2

这个太长了，但是它会在0.003秒内回复

import time
start_time = time.time()
num = "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"
def product(num):
    rightup = 0
    right = 0
    rightdown = 0
    down = 0
    if not (17 <= i <= 19 or 37 <= i <= 39 or 57 <= i <= 59 or 77 <= i <= 79 
            or 97 <= i <= 99 or 117 <= i <= 119 or 137 <= i <= 139 or 157 <= i <= 159 
            or 177 <= i <= 179 or 197 <= i <= 199 or 217 <= i <= 219 or 237 <= i <= 239 
            or 257 <= i <= 259 or 277 <= i <= 279 or 297 <= i <= 299 or 317 <= i <= 319 
            or 337 <= i <= 339 or 357 <= i <= 359 or 377 <= i <= 379 or 397 <= i <= 399):
        if i <= 339:
            rightdown = my_list[i] * my_list[i + 21] * my_list[i + 42] * my_list[i + 63]
        right = my_list[i] * my_list[i+1] * my_list[i+2] * my_list[i+3]
        if i >= 60:
            rightup = my_list[i] * my_list[i-19] * my_list[i-38] * my_list[i-57]
    greatest_product = 0
    if i <= 339:
        down = my_list[i] * my_list[i+20] * my_list[i+40] * my_list[i+60]
    greatest_product = greatest_product
    return max(rightdown,right,rightup,down)
my_list = []
andis = 0
while andis < len(num):
    number = num[andis] + num[andis + 1]
    andis += 3
    my_list.append(int(number))
m = 0
for i in range(0,400):
    if product(i) > m:
        m = product(i)
print("the biggest priduct is: ",m)
print("this code took {} seconds".format(time.time()-start_time))