Project Euler problem 79: deducing a passcode

For one place that I interviewed at (for a Python developer position) I worked with one of the devs on two Project Euler problems, one being problem 79. We talked through different approaches and came up with solutions together, but we coded separately. He seemed impressed that we were able to get through two problems. After the interview, he asked me to clean up the code and submit it, which you can see below. He never got back to me after I sent him the code. I'd like to know what's wrong with my code and not make the same mistakes again.

Problem 79:

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.

```
# problem79.py
# Project Euler
# Nicolas Hahn

# list of keys -> passcode string
# at each iteration through list,
def passcodeDerivation(keys):
answer = ''
while len(keys) > 0:
firsts = []
rests = []
for key in keys:
# split first digits, rest of the key into two lists
f, r = key[0], key[1:]
if f not in firsts:
firsts += f
rests += r
for f in firsts:
# if f has never been seen except as the first digit of a key
# it must be the next one in the passcode
if f not in rests:
newkeys = []
# take out digit we just found from all keys
for key in keys:
newkeys.append(key.replace(f,''))
# remove empty keys
keys = [k for k in newkeys if k != '']
answer += f
break
return answer

# filename ->

The thing wrong isn't so much the code as the algorithm. Your approach to finding the next first digit is inefficient. What is the right way to approach this problem?

This is actually one of the few Euler problems that I've been able to do on paper. Let's start with just establishing the constraints. We know what digits have to go before other digits and thankfully there aren't any repeats. We can turn the input text into a graph, where a directed edge indicates that a digit has to precede another digit. Behold, the power of pictures:

Just looking at the graph makes the answer obvious: 73162890. Why is it obvious and what work did we do in our head to determine this answer? We sorted the graph. Specifically, we performed a topological sort by following the edges. The algorithm is very straightforward assuming no cycles:

L <- Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n is not marked then
        for each node m with an edge from n to m do
            visit(m)
        mark n
        add n to the head of L

Since we're dealing with digits, we can keep our edges as just an array of sets:

class DigitGraph(object):
    def __init__(self):
        self.digits = set()
        self.edges = [set() for _ in xrange(10)]

    def add_edge(self, i, j): 
        self.digits.add(i)
        self.digits.add(j)
        self.edges[i].add(j)

And then topo-sort can be written by directly translating the algorithm. I'll leave the rest as an exercise. I time it at about 2x faster.

StackExchange Code Review Q#107573, answer score: 13