Question

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.

Commentary

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.

Haskell

import Data.List (nub)

crack :: [String] -> String
crack [] = []
crack xs = first : crack rest where
    heads = map head xs
    reject = nub $ map (!! 1) $ filter ((> 1) . length) xs
    first = head $ nub $ filter (`notElem` reject) heads
    rest = filter ((> 0) . length) $ map (\ys'@(y:ys) -> if y == first then ys else ys') xs

main :: IO ()
main = do
    str <- readFile "/home/zach/code/euler/079/keylog.txt"
    let attempts = lines str
    putStrLn $ crack attempts

$ ghc -O2 -o passcode-derivation passcode-derivation.hs
$ time ./passcode-derivation
real   0m0.002s
user   0m0.002s
sys    0m0.000s

Python

#!/usr/bin/env python
import os
from itertools import *
from collections import defaultdict

def main():
    attempts = [line.strip() for line in open(os.path.join(os.path.dirname(__file__), 'keylog.txt')).readlines()]
    appearances = defaultdict(list)
    for attempt in attempts:
        for i, n in enumerate(attempt):
            appearances[n].append(i)

    average_positions = {}
    for k,v in list(appearances.items()):
        average_positions[k] = float(sum(v))/float(len(v))

    a = [k for k,v in sorted(list(average_positions.items()), key=lambda a: a[1])]
    print(''.join(str(x) for x in a))

if __name__ == "__main__":
    main()

$ time python3 password-crack.py
real   0m0.020s
user   0m0.020s
sys    0m0.000s