Sur la grille 20x20 ci-dessus, les quatre nombres diagonaux sont marqués en rouge. (Numéro omis) Le produit de ces nombres est 26 × 63 × 78 × 14 = 1788696.
Laquelle des grilles 20 × 20 ci-dessus est le plus grand des produits de quatre nombres consécutifs dans l'une des directions vers le haut, le bas, la gauche, la droite et la diagonale?
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2011
Pour le moment, j'ai écrit une fonction qui scanne verticalement, horizontalement et en diagonale et renvoie le produit de 4 nombres. Je ne pouvais pas penser à la meilleure façon de le faire, mais pour le moment, j'ai décidé d'utiliser le drapeau pour déterminer la direction du balayage. Les limites de fonctionnement diffèrent en fonction de la verticale, de l'horizontale et de la diagonale, mais il était difficile d'écrire les limites de fonctionnement une par une, donc j'ai renvoyé -1 lorsqu'une exception s'est produite.
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
Le reste est terminé sans aucune mention spéciale.
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
S'il fallait l'accélérer, serait-il question de diviser le résultat du calcul de n1 * n2 * n3 * n4 par n1 et de le multiplier par n5 pour la colonne n1 n2 n3 n4 n5? Même si je le fais, je sens que ce ne sera pas rapide. (Plutôt tard)
Recommended Posts