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.
The Inner Machinations of Walker 