Project Euler 79: Analyze a user's login attempts and determine the secret numeric passcode.

Problem Description

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

Analysis

See Solution.

Project Euler 79 Solution

Runs < 10 minutes in Human mind.
There are four question to answer before a solution can be determined.
1. How many discrete digits are in the code?
2. What are those digits?
3. What order are those digits in?
4. Do the digits repeat?

By analysing the file we can quickly answer 1 and 2: There are eight digits in the code from the set {0,1,2,3,6,7,8,9}. We know this because {4,5} are missing and in order to answer the question we would have to know that.
Question 4 is answered by default because if they did repeat we would never know how long the code would be. So they don’t!
So the only real challenge is to answer question 3, which is the typical transitive relation:
If Mary is taller than Jan and Johnny is taller than Mary, but Pee-Wee, blah, blah, blah…
So we don’t really need a computer just a set of examples, for which we have plenty, to make our decision.

Given that the samples are in the order of the original 8 digit code, we look at the most frequent last digit and maximize the number of digits that come before it:
{1,2,3,6,7,8,9} come before 0. 0 is the last digit (samples: 680, 710, 290, 380).
{1,2,3,6,7,8} come before 9. 9 is the second to the last digit (samples: 689, 729, 318).
{1,2,3,6,7} come before 8. 8 is the third to the last number (samples: 168, 728, 318).
{1,3,6,7} come before 2. So, 2 is next. (samples: 762, 162, 362)
{1,3,7} come before 6. 6 is next (samples: 316, 762).
{3,7} come before 1. 1 is next (sample: 731)
and 7 comes before 3. 7 is the first number (again, sample: 731)

Afterthoughts

No afterthoughts yet.