Of the 20x20 grid above, the four diagonal numbers are marked in red. (Numbers omitted) The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the largest product of four consecutive numbers in any of the above 20 × 20 grids, up, down, left, right, and diagonally?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011
For the time being, I wrote a function that scans vertically, horizontally and diagonally and returns the product of 4 numbers. I couldn't think of the best way to do it, but for the time being, I decided to use the flag to determine the scanning direction. The operating limits differ depending on whether it is vertical, horizontal, or diagonal, but it was troublesome to write the operating limits one by one, so I returned -1 when an exception occurred.
def f(ls,m,n,flag):
ret = 1
try:
for i in range(0,4):
if flag == 'hori':
ret *= ls[m][n+i]
elif flag == 'ver':
ret *= ls[m+i][n]
elif flag == 'rdia':
ret *= ls[m+i][n+i]
else:
ret *= ls[m+i][n-i]
except:
ret = -1
return ret
The rest is finished without any special mention.
def text2list(text,ln="\n",s=' '):
L = text.split(ln)
ls = [ e.split(s) for e in L if len(e.split(s))>0 ]
if len(ls[0]):
ls.pop(0)
if len(ls[-1]):
ls.pop(-1)
ret = [ map(lambda x: int(x), e) for e in ls ]
return ret
def main():
text = '''
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
'''
ls = text2list(text)
flag_list = ['hori', 'ver', 'rdia','ldia']
seq = range(0,20)
ans = {'max':0,'m':0,'n':0,'flag':''}
for m in seq:
for n in seq:
for flag in flag_list:
ret = f(ls,m,n,flag)
if ret > ans['max']:
ans = {'max':ret,'m':m,'n':n,'flag':flag}
print max
If we were to speed it up, would it be about dividing the calculation result of n1 * n2 * n3 * n4 by n1 and multiplying it by n5 for the column n1 n2 n3 n4 n5? Even if I do it, I feel that it will not be quick. (Rather late)
Recommended Posts