Project Euler number 11

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&#91;1&#93;&#91;1&#93; >= 3) and (member[1][1] <= 16)):
                # column numbers from numbers not on edges
                newmax = List&#91;member&#91;1&#93;&#91;0&#93;-3&#93;&#91;member&#91;1&#93;&#91;1&#93;&#93;*List&#91;member&#91;1&#93;&#91;0&#93;-2&#93;&#91;member&#91;1&#93;&#91;1&#93;&#93;*List&#91;member&#91;1&#93;&#91;0&#93;-1&#93;&#91;member&#91;1&#93;&#91;1&#93;&#93;*List&#91;member&#91;1&#93;&#91;0&#93;&#93;&#91;member&#91;1&#93;&#91;1&#93;&#93;
                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: ~ $

Leave a Reply