Project Euler: Problem 79

The statement of problem 79 from Project Euler has been reproduced in its entirety below.

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.

I did not find this problem difficult in terms of either math or programming, but I really enjoyed it because the solution illustrates how a small amount of information about something valuable and secret, a passcode, can compromise its integrity. Although knowing the shortest possible passcode does not grant an attacker an entry, it increases the probability that an attack is successful. Unfortunately, many average users choose the shortest passcode satisfying all of the requirements imposed at the time of creation (e.g. Password1).

As usual, I have implemented my solution in Python.

We first need to read the contents of the text file keylog.txt. We then need to extract the set of passcode samples from the contents of the text file. We also need the set of the digits that appear in the passcode samples; this provides a lower bound on the length of the passcode.

L1 = [] #Initialize a list to hold all integer instances
L2 = [] #Initialize a list to hod all tuple instances

file_path = "C:\Users\Matt\Downloads\keylog.txt"
f = open(file_path, 'r') #Create a file object in read-mode

for line in f: #loop through the lines of the text file
    digits = map(int, line[0:3]) #Create a list of the integers in the sample
    L1.extend(digits) #Append the digits to the list L1
    L2.append(tuple(digits)) #Create a tuple out of digits and append to L2

f.close() #Close the file object

S1 = set(L1) #Use the set object to eliminate duplicates
S2 = set(L2)

We initialize two empty lists L1 and L2. To read the text file, we create a file object f. Since a file object is iterable, we can loop over the lines of f. Python reads the lines of the text file, not surprisingly, as strings. Since we are interested in integers, we use the function map with arguments int and. The int function will return an error when called if the entire line is passed as an argument due to the trailing newline character ‘\n’, so we only pass the first three characters of the string block. For example, the line ‘123’ will yield [1, 2, 3]. We store the result in the variable digits. We append the three digits that appear in a given sample to the running list L1 using the extend method of lists. We choose to represent each sample as a 3-tuple of integers using the function tuple. Since we don’t want to append the elements of the tuple to the list L2, but rather the tuple itself, we use the append method of lists. After we have completed the loop, we are done with the file object f and can close it. To eliminate duplicate digits and tuples, we use the set data structure.

 

d = {1 : set(),
     0 : set(),
     3 : set(),
     2 : set(),
     7 : set(),
     6 : set(),
     9 : set(),
     8 : set()}

for x in S2:
    d[x[0]].add(x[1])
    d[x[0]].add(x[2])
    d[x[1]].add(x[2])

We initialize a dictionary d whose keys are the integers represented as integers and whose values are empty sets. The sets will store all of the digits that appear after a given a key. We iterate over the elements of the set S2. We look up the dictionary value of the first element of the tuple and add the second and third elements of the tuple to the set. We then look up the value of the second element of the tuple and add the third element of the tuple to the set. When the loop completes, the values of each key will contain all the digits that we know appear after the key based on the 50 samples.

Since there are eight unique digits in the “keylog” sample, the shortest possible passcode must have length greater than or equal to 8. No digits appear after 0, so we place it as the last character of the passcode. 0 appears only after 9, so we place 9 as the second-to-last character. Continuing in the fashion, we obtain the candidate passcode

\displaystyle s_{1}s_{2}\cdots s_{8}=\text{73162890}

We cannot change any of the characters s_{i} without eliminating a digit, thereby invalidating one of the samples. We cannot add characters while preserving the order without increasing the length. Hence, 73162890 is the shortest possible passcode from which the samples could have come.

Advertisements
This entry was posted in Problem Solving, Python and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s