Project Euler is a compilation of programming exercises with a strong mathematical orientation. You can read my review of the site on this post. Here, I will show how to solve problem 79 using Python’s sets. If you aren’t familiar with sets, hopefully this will help you. If you’re a complete beginner, I would recommend this course to start learning Python. Let’s begin!
Problem 79
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.
From Project Euler (you might need to register first to access it)
The keylog consists of 50 different 3-digit logins: 319, 680, 180, etc.
Solving logic
We could check all the possible passcodes of increasing length and verify if it can successfully produce all of the 50 logins, but this approach wouldn’t be efficient and it would be likely difficult to program.
As an alternative, we can analyze the order of the logins’ digits. We know they appear in order. This will give us information about the order they appear in in the passcode. It will also give us information about what digits are present in the passcode and its length. We will see how by analyzing this simple information, we can deduce the passcode.
Implementation
We start by processing the logins of the txt file into a list:
with open('p079_keylog.txt', 'r') as f:
logins = f.read().splitlines()
Then we can delete the redundant logins that don’t add any extra information by converting the list to a set and then converting it to a list again:
logins = list(set(logins))
Sets are implemented in Python in such a way that all of its elements are unique. Adding a repeated element to a set has no effect. This is a property that we will take advantage of in this problem.
Now, we will group the digits of the logins according with their placement (1st digit, 2nd digit and 3th digit of the login):
first_digits = set()
second_digits = set()
third_digits = set()
for login in logins:
first_digits.add(login[0])
second_digits.add(login[1])
third_digits.add(login[2])
We get the following sets, see that each digit appears only once:
first_digits: {'1', '8', '7', '6', '2', '3'}
second_digits: {'9', '1', '8', '6', '2', '3'}
third_digits: {'9', '0', '1', '8', '6', '2'}
We can get all different digits with the union (|) operator:
>>> first_digits | second_digits | third_digits
{'9', '6', '7', '8', '1', '3', '0', '2'}
After verifying that no digit appears more than once on each different login (for instance ‘1_1′ or ’22_’), we can deduce the following:
- The shortest passcode is as long as there are different digits (8 digits).
- The first digit of the passcode is 7, for it’s the only digit that occurs only in first_digits.
- The last digit of the code is 0, for it’s the only digit that occurs only in third_digits.
Then we know the passcode is: 7xxxxxx0 where each x is any of the digits: {‘9’, ‘6’, ‘8’, ‘1’, ‘3’, ‘2’}.
We can determine the order of the remaining digits by looking at the relative order of the digits in each login. For instance, from login ‘319’, we know that digit ‘3’ comes before ‘1’ in the passcode. We will do such an analysis for all the remaining digits for all logins using the function digits_before:
def digits_before(x, logins):
"""
x: any digit 0 - 9 (char)
logins: a list of 3 digit logins
Returns a set of all digits that come before digit "x" in logins.
"""
before_digit_x = set()
for login in logins:
if x in login:
for digit in login:
if digit == x:
break
else:
before_digit_x.add(digit)
return before_digit_x
Applying this function to all the digits {‘9’, ‘6’, ‘8’, ‘1’, ‘3’, ‘2’}, we get:
Digits before 9 : {'3', '6', '1', '2', '8', '7'}
Digits before 6 : {'7', '1', '3'}
Digits before 8 : {'3', '6', '1', '2', '7'}
Digits before 1 : {'7', '3'}
Digits before 3 : {'7'}
Digits before 2 : {'6', '7', '1', '3'}
And this gives us all of the remaining information to determine the passcode. We can for instance see that ‘3’ is the 2nd digit because only ‘7’ comes before it and that ‘9’ is the one before the last one (which we said is ‘0’), because all of the other digits come before it in the logins.
I will leave that last part so as to not give away the answer. Be sure to check out Project Euler, it’s a great way of learning coding (and maths)!