Category Archives: Project Euler

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

Project Euler number 92

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."

Project Euler problem 30

Below is the solution to problem 30 from Project Euler. It’s written in Python, a programming language I’m trying to learn.

#!/usr/bin/env python 
# Project Euler problem 30

narc_sum = 0
for number in range(100, 200000):
        # Transform the number into a string
        string = str(number)
        # Transform the string into a list
        lst = list(string)
        sum = 0 
        for i in range(len(lst)):
                # Add the members of the list to the fifth power
                sum = sum + (int(lst[i])**5)
        if (number == sum):
                # Add all numbers and store in narc_sum value
                narc_sum = narc_sum + number
                print "Sum is ",narc_sum