The Inner Machinations of Walker

Project Euler Problem #87

Problem #87 concerns numbers which can be written as the sum of a perfect square, a perfect cube, and a perfect fourth power of prime numbers. The question reads:

Project Euler Problem 87: Prime power triples
The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
28 = 2^2 + 2^3 + 2^4
33 = 3^2 + 2^3 + 2^4
49 = 5^2 + 2^3 + 2^4
47 = 2^2 + 3^3 + 2^5
How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

My solution to this is probably vastly inefficient. Here is my solution:

Solution #1: Brute Force Sieve Approach

First we use the Sieve of Eratosthenes to list all primes up to the square root of 50,000,000. Then we make lists of all the perfect squares, perfect cubes, and perfect fourth powers of those primes which are less than 50,000,000. Finally, we make a list with boolean values representing whether each number from 0 to 50,000,000 can be represented and update the list for every triple of a prime square, a prime cube, and a prime fourth power. Finally, we iterate through the list to count the numbers which can be represented. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Sieve Approach to Project Euler Problem #87
 '''
 
 import time
 from math import sqrt
 
 def sieveEratosthenes(n):
     myPrimes = []
     
     primePossible = [True]*(n+1)
     primePossible[0] = False
     primePossible[1] = False
     
     for (i,possible) in enumerate(primePossible):
         if possible:
             for x in range(i*i, (n+1), i):
                 primePossible[x] = False
             myPrimes.append(i)
 
     return myPrimes
 
 def projectEulerProblemEightySeven(n):
     primes = sieveEratosthenes(int(sqrt(n)))
     squares = []
     cubes = []
     fourths = []
     cubeDone = False
     fourthDone = False
     for p in primes:
         squares.append(p*p)
         if not cubeDone:
             c = p*p*p
             if(c>n):
                 cubeDone = True
             else:
                 cubes.append(c)
         if not fourthDone:
             f = p*p*p*p
             if(f>n):
                 fourthDone = True
             else:
                 fourths.append(f)
     found = [False]*(n+1)
     for a in squares:
         for b in cubes:
             if (b+a)>n:
                 break
             for c in fourths:
                 s = a+b+c
                 if s>n:
                     break
                 else:
                     found[s] = True
     total = 0
     for x in found:
         if x:
             total+=1
     return total                
 
 start = time.time()
 print projectEulerProblemEightySeven(50000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1097343
 --- 0.985231161118 seconds ---
 
 for input of n = 50000000.
 '''

And with that, we’re done. That took nearly a second to run. I believe there is probably a faster way to do this, but this was the most efficient method that I could think of. I may return to this problem eventually.

Thanks for reading! See you tomorrow.

Project Euler Problem #86

Problem #86 concerns the surface area diagonal of rectangular prisms. The question reads:

My solution for this problem definitely falls into the category of brute force. Here is my solution:

Solution #1: Brute Force Approach

Let F(M) be the number of cuboids with this property ignoring rotations with dimensions less than or equal to M. We can observe that F(M) – F(M-1) is the number of cuboids with this property with at least one side length equal to M. Thus, it suffices to count for each possible value of M the number of triples (a,b,M) with a<=b<=M such that a cuboid with sides a, b, M has this property.

It is well known that by looking at the net of a rectangular prism, the surface area diagonal of the prism can have one of the lengths sqrt((a+b)^2+M^2), sqrt((a+M)^2+b^2), or sqrt((b+M)^2+a^2). To minimize the surface area diagonal, it is clear that the value sqrt((a+b)^2+M^2) will be the smallest, because the rate of change of x^2 increases as x increases. We can observe that sqrt((a+b)^2+M^2) <= sqrt(5*M^2). Thus, it suffices to list all square numbers up to 5*M^2 and then binary search the list for each value of (a+b)^2+M^2 to check whether the cuboid with sides a, b, M satisfies the condition. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #86
 '''
 
 import time
 from math import sqrt
 
 def projectEulerProblemEightySix(n):
     m = 0
     squares = [0]
     t = 1
     upper = 2*int(sqrt(5*n))+1
     while(t<upper):
         squares.append(t*t)
         t+=1
     current = 0
     while(current<n):
         m+=1
         cFactor = squares[m]
         for abSum in range(2,2*m+1):
             v = squares[abSum]+cFactor
             value = binarySearch(squares, v)
             if value>-1:
                 for a in range(max(abSum-m,1),abSum/2+1):
                     b = abSum - a
                     if(a<=b):
                         if b<=m:
                             current+=1
                     else:
                         break
     return m
 
 def binarySearch(myList, n):
     lower = 0
     upper = len(myList)-1
     while(lower<upper-1):
         middle = (lower+upper)/2
         v = myList[middle]
         if v>n:
             upper = middle
         elif v<n:
             lower = middle
         else:
             return middle
     if(myList[lower]==n):
         return lower
     if(myList[upper]==n):
         return upper
     return -1
 
 start = time.time()
 print projectEulerProblemEightySix(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 1818
 --- 4.28403687477 seconds ---
 
 for input of n = 1000000.
 '''

And with that, we’re done. That took nearly 5 seconds to run. I’d like to come back to this problem at some point to search for a more efficient solution. Binary Search continues to be very useful for improving the efficiency of my code.

Thanks for reading! See you tomorrow.

Project Euler Problem #85

Problem #85 concerns finding the number of rectangles with sides along a lattice grid. The question reads:

This problem is very well known among those who participate in math competitions. Here is my solution:

Solution #1: Combinatorial Approach

We can observe that in a grid with m horizontal lines and n vertical lines, any rectangle with sides along the grid lines must have sides that coincide with 2 of the horizontal lines and 2 of the vertical lines. Thus, the number of rectangles is (m choose 2) * (n choose 2). Thus, it suffices to find the product of two values of (n choose 2) which is closest to two million. We can do this by listing all triangular numbers up to n and then checking which products are closest. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Combinatorial Approach to Project Euler Problem #85
 '''
 
 import time
 
 def projectEulerProblemEightyFive(n):
     triangles = []
     c = 1
     v = 1
     while(v<=n):
         triangles.append(v)
         c+=1
         v+=c
     l = len(triangles)
     
     closestFound = -1
     smallestDiff = n
     for a in range(l):
         for b in range(a,l):
             c = triangles[a]
             d = triangles[b]
             v = abs(c*d-n)
             if(v<smallestDiff):
                 smallestDiff = v
                 closestFound = (a+1)*(b+1)
     return closestFound
 
 start = time.time()
 print projectEulerProblemEightyFive(2000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 2772
 --- 0.207247018814 seconds ---
 
 for input of n = 2000000.
 '''

And with that, we’re done. Looking back on this solution, I realize that I forgot to deal with the case where the closest grid has 2 lines in one direction and n lines in another direction so that n choose 2 is barely greater than the input. I am too lazy to make this change to make the solution universal at the moment. I may come back to this problem eventually to search for a more optimal solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #84

Problem #84 concerns simulations of the game Monopoly. The question reads:

I apologize for not embedding this problem in WordPress. I felt it would be much simpler if I just added a screenshot due to the long list of instructions. Regardless, this is one of the more intimidating early questions of Project Euler. My solution still has some bugs, and I had to guess and check my way to the answer for this problem. Here’s my solution:

Solution #1: Experimental Approach

We simply simulate a large number of moves around the Monopoly board and record the number of times each square is landed on. Then we sort the squares based on their frequency and list the most frequent squares. The annoying part is simulating the game. Here is an implementation of this solution in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Simulation Approach to Project Euler Problem #84
 '''
 
 import time
 import random
 
 def randomRoll():
     a = random.randint(1,5)
     b = random.randint(1,5)
     if(a==b):
         return [a+b,True]
     else:
         return [a+b,False]
 
 def chance(p):
     n = random.randint(0,10)
     if(n==0):
         return 0
     if(n==1):
         return 10
     if(n==2):
         return 11
     if(n==3):
         return 24
     if(n==4):
         return 39
     if(n==5):
         return 5
     if(n==6 or n==7):
         return ((p-1)-(p-1)%10 + 15)%40
     if(n==8):
         if(12<=p<28):
             return 28
         return 12
     return (p-3)%40
 
 def uniqueString(n):
     if(n<10):
         return "0"+str(n)
     return str(n)
 
 def projectEulerProblemEightyFour(n):
     communityCards = 1
     board = ["G","G","CC","G","G","G","G","CH","G","G","J","G","G","G","G","G","G","CC","G","G","G","G","CH","G","G","G","G","G","G","G","G2J","G","G","CC","G","G","CH","G","G","G"]
     position = 0
     first = False
     second = False
     third = False
     totals = [0]*40
     for c in range(n):
         move = randomRoll()
         position = (position+move[0])%40
         third = second
         second = first
         first = move[1]
         if first and second and third:
             position = 10
         else:
             v = board[position]
             if v=="CC":
                 a = random.randint(1,5)
                 if(a==1):
                     while(v=="CC"):
                         position = chance(position)
                         v = board[position]
                         if(v=="CC"):
                             a = random.randint(1,5)
                             if(a!=1):
                                 break
             elif v == "CH":
                 a = random.randint(1,9)
                 if(a==1):
                     if communityCards == 0:
                         position = 0
                     else:
                         position = 10
                     communityCards = (communityCards+1)%2
             elif v == "G2J":
                 position = 10
         totals[position]+=1
     
     indexList = []
     for x in range(40):
         indexList.append(x)
     final = sorted(indexList, key = lambda x: totals[x])[::-1]
     return uniqueString(final[0])+uniqueString(final[1])+uniqueString(final[2])
 
 start = time.time()
 print projectEulerProblemEightyFour(10**6)
 
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 101615
 --- 2.08807682991 seconds ---
 
 for input of n = 10**6. (It prints this ~80% of the time)
 
 Actual answer is 101524.
 
 There must be some small error in my simulation that caused this result to
 be so consistent. The way I solved this was by listing the 10 most frequent
 squares from my simulation and then guessing and checking until I got it.
 '''

As noted in the comments in my code, this program does not give the correct answer. While it is impossible to get a consistent experimental answer due to the random nature of Monopoly games, the most common answer should still coincide with the expected answer for a correct simulation. Thus, there is some unknown error in my simulation that I am too lazy to find at this point. To get the answer, I listed the 10 most common squares with my program and guess and checked until I found the right triple. I definitely want to come back to this problem to find an actual solution at some point.

Thanks for reading! See you tomorrow.

Project Euler Problem #83

Problem #83 is a more complex version of Problems #81 and #82. The question reads:

Project Euler Problem 83: Path sum: four ways
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131 673 234 103 018
201 096 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 037 331

Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

Unlike my solution for Problem #82, I could not find a way to simply alter my solution for Problem #81 to solve this problem. Thus, my solution for this problem is quite bad, and I am unsure whether it will always be able to find the minimum path. Here’s my solution:

Solution #1: Arbitrary Checking Approach

We can observe that even when all four directions are allowed, the minimum path cannot pass through more than n*(n+1)/2 cells (in the case where the path passes through every other complete row or column). Thus, the minimum path sum to every cell can be initially estimated as the path which moves along the top row until it reaches the column in question and then moves down the column. Then, the minimum path for each cell can be updated n*(n+1)/2 times to account for every other possible minimum path. After this is done, the minimum path to the bottom right corner should be correct. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #83
 '''
 
 import time
 
 f = open("PE83Grid.txt","r")
 
 if(f.mode == "r"):
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(map(int,x.split(",")))
 else:
     raise ValueError("Cannot read from file")
 
 def projectEulerProblemEightyThree(realContents):
     row = len(realContents)
     col = len(realContents[0])
     new = []
     rowTotal = 0
     for r in range(row):
         myRow = []
         colTotal = rowTotal
         a = realContents[r]
         rowTotal+=a[0]
         for x in a:
             colTotal+=x
             myRow.append(colTotal)
         new.append(myRow)
     
     for _ in range((row+col)):
         for r in range(row):
             for c in range(col):
                 minPos = new[r][c]
                 v = realContents[r][c]
                 if(r>0):
                     minPos = min(minPos,v+new[r-1][c])
                 if(r<row-1):
                     minPos = min(minPos,v+new[r+1][c])
                 if(c>0):
                     minPos = min(minPos,v+new[r][c-1])
                 if(c<col-1):
                     minPos = min(minPos,v+new[r][c+1])
                 new[r][c] = minPos
     return new[row-1][col-1]
 
 start = time.time()
 print projectEulerProblemEightyThree(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 425185
 --- 0.708230018616 seconds ---
 
 for input of given grid.
 '''

And with that, we’re done! To speed up my code, I only updated the minimum paths 2*n times instead of n*(n+1)/2 times. Thus, this code will not find the minimum path for any grid, but for grids with normally shaped minimum paths, it should find the minimum path. Even with this risky optimization, my solution took over half a second to run. I definitely want to return to this question eventually to look for a more efficient solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #82

Problem #82 is a more complex version of Problem #81. The question reads:

Project Euler Problem 82: Path sum: three ways
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131 673 234 103 018
201 096 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 037 331

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

As mentioned above, this problem is very similar to Problem 81. The only difference is that in this case, the path can start anywhere on the left edge and it can move up. These changes do not require the solution to be significantly different, so my solution for this problem is similar to my solution for Problem 81. Here’s my solution:

Solution #1: Dynamic Approach

We simply go from left to right across the grid, finding the minimum path sum to each cell one column at a time. The first column can be found by simply storing the first column of the given grid. Each successive column can be calculated by iterating through the previous column and finding the minimum path sum from each cell in the previous column to each cell in the next column. By this method, the minimum path to each column can be generated dynamically. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #82
 '''
 
 import time
 
 f = open("PE82Grid.txt","r")
 
 if(f.mode == "r"):
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(map(int,x.split(",")))
 else:
     raise ValueError("Cannot read from file")
 
 def projectEulerProblemEightyTwo(myGrid):
     newGrid = []
     rows = len(myGrid)
     cols = len(myGrid[0])
     for x in range(rows):
         newGrid.append([myGrid[x][0]])
     for y in range(1,cols):
         theColumn = []
         for x in range(rows):
             theColumn.append(myGrid[x][y])
         forwardPartials = [0]
         t = 0
         for x in theColumn:
             t+=x
             forwardPartials.append(t)
         backwardPartials = [t]
         for x in range(rows-1,-1,-1):
             t-=theColumn[x]
             backwardPartials.append(t)
         newColumn = []
         for z in range(rows):
             minFound = newGrid[z][y-1]+myGrid[z][y]
             for a in range(rows):
                 if(a<z):
                     total = myGrid[z][y] + forwardPartials[z]-forwardPartials[a] + newGrid[a][y-1]
                 elif(a>z):
                     total = myGrid[z][y] + forwardPartials[a+1] - forwardPartials[z+1] + newGrid[a][y-1]
                 else:
                     total = minFound
                 if(total<minFound):
                     minFound = total
             newColumn.append(minFound)
         for x in range(rows):
             newGrid[x].append(newColumn[x])
     minFound = newGrid[0][cols-1]
     for a in range(1,rows):
         v = newGrid[a][cols-1]
         if(v<minFound):
             minFound = v
     return minFound
 
 start = time.time()
 print projectEulerProblemEightyTwo(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints

 260324
 --- 0.0795319080353 seconds ---
 
 for input of given grid.
 '''

And with that, we’re done. This solution still managed to run in under a tenth of a second, but it still took over an order of magnitude longer than the solution for Problem #81. I may come back to this problem to look for a more efficient implementation.

Thanks for reading! See you tomorrow.

Project Euler Problem #81

Problem #81 concerns finding the minimum weighted path along the rows and columns of a grid. The question reads:

Project Euler Problem 81: Path sum: two ways
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

131 673 234 103 018
201 096 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 037 331

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

This is another great example of the powers of dynamic programming. Here is my solution:

Solution #1: Dynamic Programming Approach

We can simply observe that the minimum path sum from the top left corner to any given cell is the value of the cell plus the minimum of the path sum to the cell above it and the path sum to the cell to the left of it. Branching off from the top left corner and using this observation, the minimum path sum to each cell can be generated dynamically. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Dynamic Approach to Project Euler Problem #81
 '''
 
 import time
 
 f = open("PE81Grid.txt","r")
 
 if(f.mode == "r"):
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(map(int,x.split(",")))
 else:
     raise ValueError("Cannot read from file")
 
 def projectEulerProblemEightyOne(myGrid):
     firstRow = []
     total = 0
     for x in myGrid[0]:
         total+=x
         firstRow.append(total)
     newGrid = [firstRow]
     for c in range(1,len(myGrid)):
         newRow = [myGrid[c][0]+newGrid[c-1][0]]
         for x in range(1,len(myGrid[c])):
             v = myGrid[c][x]+min(newGrid[c-1][x],newRow[x-1])
             newRow.append(v)
         newGrid.append(newRow)
     return newGrid[len(myGrid)-1][len(myGrid[0])-1]
 
 start = time.time()
 print projectEulerProblemEightyOne(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 427337
 --- 0.00197601318359 seconds ---
 
 for input of given grid.
 '''

And with that, we’re done. An 80×80 grid can be searched in just over a millisecond in Python 2.7 with Dynamic Programming.

Thanks for reading! See you tomorrow.

Project Euler Problem #80

Problem #80 concerns the digits of the decimal expansions of irrational square roots. The question reads:

Project Euler Problem 80: Square root digital expansion
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

My solution to this problem is very bad as it cannot be generalized easily to larger inputs. Here is my solution:

Solution #1: Arbitrary Precision Approach

We simply use the Python decimal library to find arbitrarily precise values of the decimal expansions of the irrational square roots of the numbers less than 100. Then we add up the first 100 digits of each expansion. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #80
 '''
 
 import time
 from decimal import *
 from math import sqrt
 
 getcontext().prec = 200
 
 def sumDigitSquareRoot(n,x):
     a = Decimal(n).sqrt()
     s = str(a)
     t = 0
     for y in range(x+1):
         if(s[y]!="."):
             t+=int(s[y])
     return t
 
 def isSquare(n):
     a = int(sqrt(n))
     return a*a==n
 
 def projectEulerProblemEighty(n,e):
     total = 0
     for c in range(2,n+1):
         if not isSquare(c):
             total+=sumDigitSquareRoot(c, e)
     return total
 
 start = time.time()
 print projectEulerProblemEighty(100, 100)
 print ("--- %s seconds ---" % (time.time() - start))
 
 '''
 Prints
 
 40886
 --- 0.00751686096191 seconds ---
 
 for input of n = 100, e = 100.
 '''

And with that, we’re done. I used 200 digits of precision to find the precise first 100 digits of each square root. It is very likely that for larger inputs, a higher level of precision would be necessary, but I am unsure how this level of precision could be written explicitly based on the input size. I may come back to this problem to look for a less arbitrary solution.

Thanks for reading! See you tomorrow.

Project Euler Problem #79

Problem #79 concerns finding the shortest string with given substrings. The question reads:

Project Euler Problem 79: Passcode derivation
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

My solution uses a greedy algorithm approach. Here is my solution:

Solution #1: Greedy Algorithm Approach

We simply iterate through the different substrings and store all the minimum length strings at each step. For each new substring, we do casework based on which characters in the substring are present in each minimum length string. A list of all concatenated strings is generated and only the shortest strings are kept for the next substring. Finally, once all substrings have been concatenated, the shortest possible string is generated. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #79
 '''
 
 import time
 f = open("PE79PasscodeAttempts.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     for x in contents:
         realContents.append(str(x))
 else:
     raise ValueError("Cannot read from file")
 
 finalContents = []
 for x in realContents:
     finalContents.append(x[0:3])
 
 def concatenateStrings(a,b):
     c = b[0]
     d = b[1]
     e = b[2]
     try:
         f = a.index(c)
     except:
         f = -1
     try:
         g = a.index(d,f+1)
     except:
         g = -1
     try:
         h = a.index(e,max(g+1,f+1))
     except:
         h = -1
     possible = []
     l = len(a)
     if(f==-1 and g == -1 and h == -1):
         for i1 in range(l+1):
             for i2 in range(i1,l+1):
                 for i3 in range(i2,l+1):
                     s = a[0:i1]+c
                     s+=(a[i1:i2]+d)
                     s+=(a[i2:i3]+e+a[i3:])
                     possible.append(s)
         return possible
     if(g==-1 and h == -1):
         for i1 in range(f+1,l+1):
             for i2 in range(i1,l+1):
                 s = a[0:i1]+d
                 s+=a[i1:i2]+e+a[i2:]
                 possible.append(s)
         return possible
     if(f==-1 and h==-1):
         for i1 in range(g+1,l+1):
             for i2 in range(i1,l+1):
                 s = a[0:i1]+c
                 s+=a[i1:i2]+e+a[i2:]
                 possible.append(s)
         return possible
     if(f==-1 and g==-1):
         for i1 in range(g+1,l+1):
             for i2 in range(i1,l+1):
                 s = a[0:i1]+c
                 s+=a[i1:i2]+d+a[i2:]
                 possible.append(s)
         return possible
     if(f==-1):
         for i1 in range(g):
             s = a[0:i1]+c+a[i1:]
             possible.append(s)
         return possible
     if(g==-1):
         for i1 in range(f+1,h):
             s = a[0:i1]+d+a[i1:]
             possible.append(s)
         return possible
     if(h==-1):
         for i1 in range(g+1,l+1):
             s = a[0:i1]+c+a[i1:]
             possible.append(s)
         return possible
     return [a]
 
 def projectEulerProblemSeventyNine(myList):
     if(len(myList)==1):
         return myList[0]
     if(len(myList) == 2):
         a = concatenateStrings(myList[0], myList[1])
         minFound = len(a[0])
         for x in a:
             if(len(x)<minFound):
                 minFound = len(x)
         return minFound
     allMini = [myList[0]]
     l = len(myList)
     for x in range(1,l):
         newMini = []
         minLength = -1
         curValue = myList[x]
         for y in allMini:
             z = concatenateStrings(y, curValue)
             for b in z:
                 if(minLength==-1 or len(b)<minLength):
                     minLength = len(b)
                     newMini = [b]
                 elif(len(b)==minLength):
                     if b not in newMini:
                         newMini.append(b)
         allMini = newMini
     return allMini[0]
 
 start = time.time()
 print projectEulerProblemSeventyNine(finalContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 73162890
 --- 0.000269889831543 seconds ---
 
 for input = given list of password attempts.
 '''

And with that, we’re done! Sorry if my solution was hard to understand. Hopefully my code clarified it a bit. I am curious to know efficient this function is for larger inputs. I am also curious about whether this function will always generate the correct answer. I have yet to prove that the greedy algorithm will always generate the optimal string.

Thanks for reading! See you tomorrow.

Project Euler Problem #78

Problem #78 is yet another problem which involves partitions. The question reads:

Project Euler Problem 78: Coin partitions
Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O
Find the least value of n for which p(n) is divisible by one million.

We will proceed with the same dynamic approach that was used in Problem #31, Problem #76, and Problem #77. As noted in my posts for each of those problems, my solution is heavily inspired by Project Euler’s documentation for Problem #31. That being said, my solution is still far too inefficient for this version of the partition problem as it takes over 3 minutes to run. Here is my solution:

Solution #1: Brute Force Dynamic Approach

As in the other questions that involve partitions, we add recursive layers representing larger summands after counting the partitions of every number with the smaller summands. In this variant of the problem, we have to guess and check what the smallest number with a multiple of 1,000,000 partitions is. Because it is not easy to recursively go from F(n) to F(n+1), we will guess and check by repeatedly multiplying the guess by 3. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #78
 '''
 
 import time
 
 def subProblem(n,x):
     numbers = []
     for y in range(1,n+1):
         numbers.append(y)
     ways = [0]*(n+1)
     ways[0] = 1
     for i in range(len(numbers)):
         for j in range(numbers[i], n+1):
             ways[j] = (ways[j] + ways[j-numbers[i]])%x
     for y in range(n+1):
         if (ways[y])%x == 0:
             return y
     return -1
 
 def projectEulerProblemSeventyEight(n):
     c = 10
     while True:
         a = subProblem(c,n)
         if(a!=-1):
             return a
         c*=3
         
 start = time.time()
 print projectEulerProblemSeventyEight(1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 55374
 --- 222.313875198 seconds ---
 
 for input of n = 1000000.
 '''

And with that, we’re done. Yikes! That took over 3 minutes to run. I definitely need to look for a faster way to do this. The main problem is that because the recursive layers build off of each other as larger summands are added and a new summand is added for every new input, it is hard to do the entire problem recursively. We can store the remainder when every subproblem is computed mod 1,000,000 to make the solution more efficient, but this barely improved the efficiency. As of right now, I am unsure how to optimize this solution.

Thanks for reading! See you tomorrow.