"""
problem79.py

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 collections import defaultdict, deque
from itertools import dropwhile

def to_digits(num):
    return map(int, str(num))

def to_num(digits):
    return int(''.join(map(str, digits)))

# Use 'breadth-first tree search', inspired by Peter Norvig's version in AIMA.
def solve(codes):
    # Store all relations specified in the codes in a dict. Each digit
    # is mapped to those digits appearing after it.
    after = defaultdict(set)
    for code in codes:
        a, b, c = to_digits(code)
        after[a].add(b)
        after[a].add(c)
        after[b].add(c)

    # We will use lists to represent nodes in the tree, each of which is
    # a candidate solution. So, initialise the frontier to the possible
    # starting values.
    frontier = deque([x] for x in after)
    while frontier:
        node = frontier.popleft()
        if goal_state(node, after):
            return node
        # Use the 'after' dict to find the values, x, reachable from the end of
        # the current node. Child nodes are then node + [x].
        frontier.extend(node + [x] for x in after[node[-1]])

def goal_state(node, after):
    """Check whether, for all the relations specified in the 'after' dict,
    the node satisfies them."""
    # For each key, x, in the 'after' dict, the values, y, in after[x] must
    # exist after the first occurrence of x in the node.
    return all(y in dropwhile(lambda dgt: dgt != x, node)
               for x in after
               for y in after[x])

def problem79():
    with open("data/keylog.txt", "r") as f:
        codes = [int(x) for x in f.readlines()]
    solution = solve(codes)
    return to_num(solution)

Add problem79.py