http://projecteuler.net/problem=79
As I was researching the web for approaches to solving this problem, I found Kristian’s MathBlog article quite useful (as usual), and so I took up his suggestion to try implementing a topological sorting algorithm, which I found described in Wikipedia.
I had some problems just using the pseudocode described in Wikipedia, mostly because Python won’t let you iterate over a set if you change the set during the iteration, so I had to figure out some workarounds.
#euler 79
f = open('keylog.txt', 'r')
attempts = []
for line in f:
attempts.append(line.replace('\n',''))
candidates = [] #possible numbers in passcode
for i in attempts:
for j in i:
if not j in candidates:
candidates.append(j)
# let's take attempts, and turn it into a set of directed edges
# each edge is a tuple (a, b) where a precedes b
edges = set()
for i in attempts:
e1 = (i[0],i[1])
e2 = (i[1],i[2])
edges.add(e1)
edges.add(e2)
#let's implement the Kahn topological sorting algo (see Wikipedia)
def findNoEdge(candidates, edges): # returns list of candidates with no incoming edge
output = []
for a in candidates:
test = True
for b in edges:
if b[1] == a:
test = False
break
if test:
output.append(a)
return output
L = [] #empty list of sorted elements
S = findNoEdge(candidates, edges)
def removeNode(n, S, L, edges):
S.remove(n)
L.append(n)
edgesToRemove = []
for i in edges: # i is a tuple of node a pointing to node b
if i[0] == n:
edgesToRemove.append(i)
for j in edgesToRemove:
edges.remove(j)
for j in edgesToRemove:
temp = findNoEdge(j, edges) #this is a list of nodes that have no incoming edges
for k in temp:
if not k in L:
S.append(k)
return S, L, edges
keepGoing = True
while keepGoing:
a = len(S)
sCopy = S[:]
for counter in range(a):
S, L, edges = removeNode(sCopy[counter], S, L, edges)
if len(S) == 0:
print "".join(str(x) for x in L)
break
