Project Euler | XaviGNU

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: ~ $

Below is the solution to Project Euler problem 92. Its written in python and takes about 10 minutes to reach the solution depending on your hardware. There are some comments in the code to know what the program is doing.

#!/usr/bin/env python

number_89 = 0

for z in range(10000000, 1, -1):

        def chain(z):
                var = z
                chaindigit = 0
                while (chaindigit != 1 or chaindigit != 89):
                        # Transform the number into a string
                        list =  [int(i) for i in str(var)]
                        # Multiply each list member 
                        chain = [x * y for x, y in zip(list, list)]
                        # Add the remaining list members
                        chaindigit = sum(chain)
                        var = chaindigit
                        # Check whether it ends in 89 or 1 
                        if (chaindigit == 1 or chaindigit == 89):
                                # If it ends in 89 increment the value of number_89
                                if (chaindigit == 89):
                                        global number_89
                                        number_89 = number_89 + 1
                                break
        chain(z)

print "There are", number_89,"chain numbers that end in 89."

XaviGNU

Me and my world

Category Archives: Project Euler

Project Euler number 11

Project Euler number 92

Project Euler problem 24

Project Euler problem 29

Project Euler problem 30