Project Euler Problem 79 Solution


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 used a statistical approach to solve this problem. Essentially, these are the steps I used:

  1. For each successful login attempt in the file, make a note of the characters and their position. For example, if the attempt is ‘319’, we would note that ‘3’ is at position 0, ‘1’ is at position 1, and ‘9’ is at position 2. These results are stored in a dictionary of lists, where the keys are the characters and the values are a list of all positions where that character is found.
  2. Next, we calculate the average position of each character. To do this we simply divide the sum of the character’s positions by the number of times the character appeared.
  3. Then, we sort the dictionary by value, so that characters with a smaller average position appear before those with a greater average position.
  4. Finally, we concatenate the sorted characters and return this as the result.