Problem #11, like Problem #8, is one of the many Project Euler problems that requires the user to analyze a large amount of data. Here is its statement:
Project Euler Problem 11: Largest product in a grid In the 20 x 20 grid below, four numbers along a diagonal line have been marked in red. (bold in my blog post) 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 The product of these numbers is 26 x 63 x 78 x 14 = 1788696. What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 x 20 grid?
As in Problem #8, the real challenge here is finding a way to store that massive grid so that we can analyze it through traditional methods. Here was my solution:
Solution #1: Read From File and Brute Force Approach
Like in Problem #8, I thought the best way to approach this question would be by copy pasting the massive block of text into a file (I called the file “PE11Grid”) and then using a Python script to read from the file and analyze the data. Once I read from the file, I essentially used a brute force approach, testing every product of four adjacent numbers and storing a running maximum product. Clearly this method can be optimized by using a “running product” system where new numbers are multiplied with the running product and old values are divided out, but I didn’t want to deal with casework involving the presence of “00” cells.
Here is an implementation of this brute force method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #11
'''
import time
f = open("PE11Grid.txt","r")
if f.mode=="r":
contents = f.readlines()
realContents=[]
for x in contents:
realContents.append(map(int,x.split()))
else:
raise ValueError("Cannot read from file")
def projectEulerProblemEleven(grid,l):
rows = len(grid)
cols = len(grid[0])
maxProduct = -1
for r in range(rows):
for c in range(cols-l):
total = 1
for x in range(l):
total*=grid[r][c+x]
if(total>maxProduct):
maxProduct = total
for r in range(rows-l):
for c in range(cols):
total = 1
for x in range(l):
total*=grid[r+x][c]
if(total>maxProduct):
maxProduct = total
for r in range(rows-l):
for c in range(cols-l):
total = 1
for x in range(l):
total*=grid[r+x][c+x]
if(total>maxProduct):
maxProduct = total
for r in range(rows-l):
for c in range(l-1,cols):
total = 1
for x in range(l):
total*=grid[r+x][c-x]
if(total>maxProduct):
maxProduct = total
return maxProduct
start = time.time()
print projectEulerProblemEleven(realContents,4)
print("--- %s seconds ---" % (time.time()-start))
'''
Prints
70600674
--- 0.000658988952637 seconds ---
for input of given grid
'''
Once again, these types of problems are only helpful in the sense that they teach you how to read from large amounts of data. The first few tend to have fairly standard solutions.
That is all. Thanks for reading!
The Inner Machinations of Walker 