Below is my solution to Poject Euler number eleven. I created back ordered array with the number and its positions on a 2D 20×20 array. The 4 corners 4×4 array products only the vertical and horizontal products where calculated since the diagonal products are calculated previously with the 16×16 array.
#!/usr/bin/env python
import time
start = time.time()
f = open("grid.txt", "r")
i = 0
j = 0
newList = []
List = []
# Create and array 20x20 converting members to int
for line in f:
List.append(line.split())
List[i] = map(int, List[i])
i = i + 1
# Create an ordered array starting by highest number and writing also position
i = 0
j = 0
for i in range(len(List[i])):
for j in range(len(List[i])):
newList.append([List[i][j],[i,j]])
sortedList = sorted(newList)
# backorderdList is an array containing an ordered number with its positions in array second entry.
backorderedList = sortedList[::-1]
max = 0
for member in backorderedList:
if ((member[1][0] == 0) and (member[1][1] == 0)):
# Multiply upper corner first four lines
for x in range(4):
# Line multiplication
newmax = List[x][0]*List[x][1]*List[x][2]*List[x][3]
if (newmax > max):
max = newmax
# Column multiplication
newmax = List[0][x]*List[1][x]*List[2][x]*List[3][x]
if (newmax > max):
max = newmax
elif ((member[1][0] == 0) and (member[1][1] == 16)):
# Multiply upper right corner
for x in range(4):
# Line multiplication
newmax = List[x][16]*List[x][17]*List[x][18]*List[x][19]
if (newmax > max):
max = newmax
# Column multiplication
newmax = List[0][x+16]*List[1][x+16]*List[2][x+16]*List[3][x+16]
if (newmax > max):
max = newmax
elif ((member[1][0] == 16) and (member[1][1] == 0)):
# Multiply lower left corner
for x in range(4):
# Line multiplication
newmax = List[x+16][0]*List[x+16][1]*List[x+16][2]*List[x+16][3]
if (newmax > max):
max = newmax
# Column multiplication
newmax = List[16][x]*List[17][x]*List[18][x]*List[19][x]
if (newmax > max):
print max
elif ((member[1][0] == 16) and (member[1][1] == 16)):
# Multiply lower right corner
for x in range(4):
# Line multiplication
newmax = List[x+16][16]*List[x+16][17]*List[x+16][18]*List[x+16][19]
if (newmax > max):
max = newmax
# Column multiplication
newmax = List[16][x+16]*List[17][x+16]*List[18][x+16]*List[19][x+16]
if (newmax > max):
max = newmax
elif ((member[1][0] >= 3) and (member[1][0] <= 16) and (member[1][1] >= 3) and (member[1][1] <= 16)):
# column numbers from numbers not on edges
newmax = List[member[1][0]-3][member[1][1]]*List[member[1][0]-2][member[1][1]]*List[member[1][0]-1][member[1][1]]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
newmax = List[member[1][0]+3][member[1][1]]*List[member[1][0]+2][member[1][1]]*List[member[1][0]+1][member[1][1]]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
# line numbers
newmax = List[member[1][0]][member[1][1]-3]*List[member[1][0]][member[1][1]-2]*List[member[1][0]][member[1][1]-1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
newmax = List[member[1][0]][member[1][1]+3]*List[member[1][0]][member[1][1]+2]*List[member[1][0]][member[1][1]+1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
# diagonal numbers
newmax = List[member[1][0]-3][member[1][1]-3]*List[member[1][0]-2][member[1][1]-2]*List[member[1][0]-1][member[1][1]-1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
newmax = List[member[1][0]+3][member[1][1]+3]*List[member[1][0]+2][member[1][1]+2]*List[member[1][0]+1][member[1][1]+1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
newmax = List[member[1][0]-3][member[1][1]+3]*List[member[1][0]-2][member[1][1]+2]*List[member[1][0]-1][member[1][1]+1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
newmax = List[member[1][0]+3][member[1][1]-3]*List[member[1][0]+2][member[1][1]-2]*List[member[1][0]+1][member[1][1]-1]*List[member[1][0]][member[1][1]]
if (newmax > max):
max = newmax
print "Max is: %d." % (max)
elapsed = (time.time() - start)
print "Elapsed time: %s seconds." % (elapsed)
f.close()
Took the execution time idea from here.
Execution:
user@server1: ~ $ python euler_11.py ; uname -a Max is: 70600674. Elapsed time: 0.0441608428955 seconds. Linux server1 2.6.32-042stab106.4 #1 SMP Fri Mar 27 15:19:28 MSK 2015 x86_64 GNU/Linux user@server1: ~ $