// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (11 votes, average: 4.91 out of 5)
Loading...

Project Euler Solutions

Project Euler 79 Solution

Project Euler 79 Solution

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.
Project Euler 79 Solution last updated

Discussion

2 Responses to “Project Euler 79 Solution”

  1. “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 I know I’m about 10.5 years late here, but what if you had 012 and 210 as successful attempts. In this case there wouldn’t be any 3 digit solutions, but 2012 would work fine.

    Posted by Desox | January 4, 2020, 9:18 AM
  2. Nicely done!

    Posted by M | July 23, 2009, 1:25 PM

Post a comment