Project Euler problem 79: deducing a passcode

Question

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 -> list of keys
def loadKeys(keyFile):
    keys = []
    with open(keyFile,'r') as f:
        for line in f:
            keys.append(line.replace('\n',''))
    return keys

def main():
    keys = loadKeys('problem79keylog.txt')
    # correct answer = 73162890
    print(passcodeDerivation(keys))

if __name__ == "__main__":
    main()

Answer 1

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.

Answer 2

Here are a few things that I notice:

• You’re documenting your functions with block comments instead of with docstrings, which are the preferred method for documenting Python functions.

  Those docstrings should also give me some idea of what arguments these functions expect, and what they will return. Right now it’s not obvious.

• You’re not using the variable naming schemes set out in PEP 8 – in particular, functions and variables should be lowercase_with_underscores, not camelCase.

• There are quite a few single-letter variable names in this code. Generally I prefer to avoid those except in the most trivial of cases – there’s usually a more descriptive name, which makes the code easier to read, and easier to search for that variable.

• In passcodeDerivation(), rather than using while len(keys) > 0:, you can use implicit truthiness – empty lists are False, non-empty lists are True – and tidy this up as while keys:.

  You can do the same thing further down: consider

  keys = [k for k in newkeys if k]
  

• In the loadKeys() function, it would be better to use line.strip() over line.replace('\n','') – this will be more resilient to different line endings on different platforms.