45 lines
986 B
Python
Executable File
45 lines
986 B
Python
Executable File
#!/usr/bin/env python
|
|
|
|
import re
|
|
|
|
RE_LINE = re.compile('^Step (.*) must be finished before step (.*) can begin.')
|
|
tree = dict()
|
|
|
|
def read_input():
|
|
with open('input.txt', 'r') as f:
|
|
for line in f:
|
|
yield line
|
|
|
|
def add_dependency(a, b):
|
|
if a not in tree:
|
|
tree[a] = {
|
|
'node': a,
|
|
'parent': '',
|
|
'child': '',
|
|
}
|
|
if b not in tree:
|
|
tree[b] = {
|
|
'node': b,
|
|
'parent': '',
|
|
'child': '',
|
|
}
|
|
tree[a]['child'] += b
|
|
tree[b]['parent'] += a
|
|
|
|
for l in read_input():
|
|
m = RE_LINE.match(l)
|
|
if m is None:
|
|
raise Exception('unpaseable line')
|
|
add_dependency(m.group(1), m.group(2))
|
|
|
|
result = []
|
|
while len(tree):
|
|
root = min([ n['node'] for n in tree.values() if len(n['parent']) == 0])
|
|
for c in tree[root]['child']:
|
|
tree[c]['parent'] = tree[c]['parent'].replace(root, "")
|
|
del tree[root]
|
|
result.append(root)
|
|
|
|
|
|
print(''.join(result))
|