Project Euler 11 "Maximum product in grid"

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

Project Euler 11 "Maximum product in grid"
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler 37
Functional programming in Python Project Euler 1
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
[Note] Project Euler in Python (Problem 1-22)
Project Euler 26
Project Euler 8
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Functional programming in Python Project Euler 2
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler # 15 "Lattice Path" in Python
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 12 "High Divisibility Triangular Number" in Python
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?