Projet Euler 11 "Produit maximum dans la grille"

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

Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 11 "Produit maximum dans la grille" en Python
Projet Euler # 8 "Produit maximum en chaîne numérique" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler # 3 "Maximum Prime Factors" en Python
Projet Euler 37
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 38
[Note] Projet Euler en Python (problème 1-22)
Projet Euler 26
Projet Euler 8
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler # 15 "Lattice Path" en Python
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
Projet Euler # 16 "Somme des pouvoirs" en Python
Projet Euler # 9 "Numéro spécial Pitagolas" en Python
Projet Euler # 14 "Colonne de nombre de collats la plus longue" en Python
J'ai écrit Project Euler 1 en une seule ligne.
Projet Euler # 2 "Even Fibonacci Number" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python
Projet Euler # 10 "somme des nombres premiers" en Python
Projet Euler n ° 12 "Triangles hautement ajustés" en Python
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
Qu'est-ce que Project Euler 3 Acceleration?