Maximum product in grid

Assignment 1:

In the 20 x 20 grid far below, four numbers along a diagonal line have been marked in red. The
product of these numbers is 26 x 63 x 78 x 14 = 1788696. Write a program to answer the
question: what is the greatest product of “z” adjacent numbers in the same direction (up, down,
left, right or diagonally) in the grid?

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
Your program must accept the parameter “z” from command line along with the name of the grid
file. It must output the positions of the numbers in the greatest product, the actual numbers and
the product. For example, to indicate the above four red numbers, your program must print the
following:
Maximum 4-product in file “grid.txt”
Row 7 col 9: 26
Row 8 col 10: 63
Row 9 col 11: 78
Row 10 col 12: 14
Product: 1788696
Note that the grid may be smaller or larger than 20×20 but must always be a square grid. If your
program detects something other than a square grid, it should output an error message. Also
note that the user may request a “z” larger than the grid, in which case your program should
also output an error message.
Submit your source code (.py file) for your implementation through email.

 Solution:

 assignment2.py

classfindMaxProduct(object):

#set default values to the class variables

def __init__(self, z=4, filename=”grid.txt”):

self.z = z

self.filename = filename

self.grid = []

self.row = []

self.col = []

self.product = 0

#get the inputs Z and filename

defgetInput(self):

self.filename = input(“Enter the file name along with the format(eg: grid.txt) : “)

self.z = int(input(“Enter the value of Z : “))

self.readFile()

ifself.z>len(self.grid) :

print(“Error! Value of Z is greater than the grid size.”)

quit()

elifself.z<= 0 :

print(“Value of Z should be a positive integer!”)

quit()

#read the input file and check if it has a valid grid

defreadFile(self):

try:

f = open(self.filename,”r”)

exceptFileNotFoundError:

print(“File “, self.filename,” doesn’t exist”)

quit()

else:

#read the file line by line

#f = open(self.filename,”r”)

for line in f:

if(len(line) > 0):

numbers = line.split(” “)

self.grid.append(numbers)

grid = []

#convert the grid of strings to an integer grid

for row in self.grid:

row = [int(col) for col in row]

grid.append(row)

self.grid = grid

for row in self.grid:

iflen(row) != len(self.grid[0]) :

print(“Error! uneven rows detected.”)

quit()

if (len(self.grid) != len(self.grid[0])) :

print(“Error! Input is not a square grid.”,len(self.grid), len(self.grid[0]))

f.close()

# find the maximum product calculating going vertically, horizontally and diagonally

deffindMaxProduct(self):

z = self.z

for x in range(len(self.grid) – z + 1):

for y in range(len(self.grid) – z + 1):

self.hor(x,y)

self.ver(x,y)

self.diag(x,y)

#check for the product horizontally

defhor(self,x,y):

z = self.z

product = 1

rowi = [] #store row index

coli = [] #store column index

for row in range(x,x+z):

product = product * self.grid

[row]

[y]

rowi.append(row)

coli.append(y)

if(product >self.product):

self.product = product

self.row = rowi

self.col = coli

#check for the product vertically

defver(self,x,y):

z = self.z

product = 1

rowi = [] #store row index

coli = [] #store column index

for col in range(y,y+z):

product = product * self.grid[x][col]

rowi.append(x)

coli.append(col)

if(product >self.product):

self.product = product

self.row = rowi

self.col = coli

#check for the product diagonally

defdiag(self,x,y):

z = self.z

product = 1

rowi = [] #store row index

coli = [] #store column index

col = y

for row in range(x,x+z):

product = product * self.grid

[row]

[col]

rowi.append(row)

coli.append(col)

col = col+1

if(product >self.product):

self.product = product

self.row = rowi

self.col = coli

#print the maximum product along with the product numbers

def print(self):

print(“Maximum”, self.z,”-product in file \””, self.filename, “\””)

for x in range(len(self.row)):

print(“Row”, self.row[x]+1, “col”, self.col[x]+1, “:”, self.grid[self.row[x]][self.col[x]])

print(“Product:”, self.product)

#create an object to access the members of the class

a = findMaxProduct()

a.getInput()

a.findMaxProduct()

a.print()