{"id":978,"date":"2015-05-06T05:20:27","date_gmt":"2015-05-06T09:20:27","guid":{"rendered":"http:\/\/www.xavignu.com\/?p=978"},"modified":"2016-04-14T11:39:32","modified_gmt":"2016-04-14T15:39:32","slug":"project-euler-number-11","status":"publish","type":"post","link":"https:\/\/www.xavignu.com\/?p=978","title":{"rendered":"Project Euler number 11"},"content":{"rendered":"

Below is my solution to Poject Euler number eleven<\/a>. 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.<\/p>\n

[python]
\n#!\/usr\/bin\/env python<\/p>\n

import time<\/p>\n

start = time.time()
\nf = open(“grid.txt”, “r”)
\ni = 0
\nj = 0
\nnewList = []
\nList = []<\/p>\n

# Create and array 20×20 converting members to int
\nfor line in f:
\n List.append(line.split())
\n List[i] = map(int, List[i])
\n i = i + 1<\/p>\n

# Create an ordered array starting by highest number and writing also position
\ni = 0
\nj = 0
\nfor i in range(len(List[i])):
\n for j in range(len(List[i])):
\n newList.append([List[i][j],[i,j]])
\nsortedList = sorted(newList)
\n# backorderdList is an array containing an ordered number with its positions in array second entry.
\nbackorderedList = sortedList[::-1]<\/p>\n

max = 0
\nfor member in backorderedList:
\n if ((member[1][0] == 0) and (member[1][1] == 0)):
\n # Multiply upper corner first four lines
\n for x in range(4):
\n # Line multiplication
\n newmax = List[x][0]*List[x][1]*List[x][2]*List[x][3]
\n if (newmax > max):
\n max = newmax
\n # Column multiplication
\n newmax = List[0][x]*List[1][x]*List[2][x]*List[3][x]
\n if (newmax > max):
\n max = newmax<\/p>\n

elif ((member[1][0] == 0) and (member[1][1] == 16)):
\n # Multiply upper right corner
\n for x in range(4):
\n # Line multiplication
\n newmax = List[x][16]*List[x][17]*List[x][18]*List[x][19]
\n if (newmax > max):
\n max = newmax
\n # Column multiplication
\n newmax = List[0][x+16]*List[1][x+16]*List[2][x+16]*List[3][x+16]
\n if (newmax > max):
\n max = newmax<\/p>\n

elif ((member[1][0] == 16) and (member[1][1] == 0)):
\n # Multiply lower left corner
\n for x in range(4):
\n # Line multiplication
\n newmax = List[x+16][0]*List[x+16][1]*List[x+16][2]*List[x+16][3]
\n if (newmax > max):
\n max = newmax
\n # Column multiplication
\n newmax = List[16][x]*List[17][x]*List[18][x]*List[19][x]
\n if (newmax > max):
\n print max<\/p>\n

elif ((member[1][0] == 16) and (member[1][1] == 16)):
\n # Multiply lower right corner
\n for x in range(4):
\n # Line multiplication
\n newmax = List[x+16][16]*List[x+16][17]*List[x+16][18]*List[x+16][19]
\n if (newmax > max):
\n max = newmax
\n # Column multiplication
\n newmax = List[16][x+16]*List[17][x+16]*List[18][x+16]*List[19][x+16]
\n if (newmax > max):
\n max = newmax<\/p>\n

elif ((member[1][0] >= 3) and (member[1][0] <= 16) and (member[1][1] >= 3) and (member[1][1] <= 16)):\n # column numbers from numbers not on edges\n 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]]\n if (newmax > max):
\n max = newmax
\n 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]]
\n if (newmax > max):
\n max = newmax
\n # line numbers
\n 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]]
\n if (newmax > max):
\n max = newmax
\n 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]]
\n if (newmax > max):
\n max = newmax
\n # diagonal numbers
\n 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]]
\n if (newmax > max):
\n max = newmax
\n 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]]
\n if (newmax > max):
\n max = newmax
\n 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]]
\n if (newmax > max):
\n max = newmax
\n 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]]
\n if (newmax > max):
\n max = newmax<\/p>\n

print “Max is: %d.” % (max)
\nelapsed = (time.time() – start)
\nprint “Elapsed time: %s seconds.” % (elapsed)<\/p>\n

f.close()
\n[\/python]<\/p>\n

Took the execution time idea from here<\/a>.<\/p>\n

Execution:
\n[shell]
\nuser@server1: ~ $ python euler_11.py ; uname -a
\nMax is: 70600674.
\nElapsed time: 0.0441608428955 seconds.
\nLinux server1 2.6.32-042stab106.4 #1 SMP Fri Mar 27 15:19:28 MSK 2015 x86_64 GNU\/Linux
\nuser@server1: ~ $
\n[\/shell]<\/p>\n","protected":false},"excerpt":{"rendered":"

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. [python] #!\/usr\/bin\/env python import time […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[62,63],"tags":[67],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_shortlink":"https:\/\/wp.me\/pTQgt-fM","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/posts\/978"}],"collection":[{"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=978"}],"version-history":[{"count":6,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/posts\/978\/revisions"}],"predecessor-version":[{"id":1183,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=\/wp\/v2\/posts\/978\/revisions\/1183"}],"wp:attachment":[{"href":"https:\/\/www.xavignu.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=978"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=978"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xavignu.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=978"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}