Skip to content

Instantly share code, notes, and snippets.

@the-eater
Created March 20, 2019 13:52
Show Gist options
  • Save the-eater/7ac9ac4366123e84455e6d37c608069e to your computer and use it in GitHub Desktop.
Save the-eater/7ac9ac4366123e84455e6d37c608069e to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
import sys
from pprint import pprint
class Serial:
def __init__(self, *args):
self.list = list(*args)
def extend(self, *args):
self.list.extend(*args)
def append(self, *args):
self.list.append(*args)
def __len__(self):
return len(self.list)
def __iter__(self):
return self.list.__iter__()
def __getitem__(self, item):
return self.list[item]
def map(self, func):
return self.__class__(list(map(func, self.list)))
def __repr__(self):
return '(' + ' '.join(map(str, self.list)) + ')'
class Parallel(Serial):
def __repr__(self):
return '(' + ' | '.join(map(str, self.list)) + ')'
def resolve_layers(from_layer, fulfilled, dependencies, parents, current=None):
current = current if current is not None else set()
prev_layer = from_layer
layers = []
tree = Serial()
while len(prev_layer) > 0:
next_layer, next_tree = add_layer(prev_layer, fulfilled, dependencies, parents, current)
if len(next_tree) > 0:
tree.append(Parallel(next_tree))
if len(next_layer) == 0:
break
fulfilled |= next_layer
layers.append(next_layer)
prev_layer = next_layer
return fulfilled, layers, flatten(tree)
def flatten(input):
return input.map(flatten_self)
def flatten_self(input):
if not isinstance(input, Serial) and not isinstance(input, Parallel):
return input
if len(input) == 1:
return input[0]
return input
def add_layer(last_layer, fulfilled, dependencies, parents, current=None):
current = current if current is not None else set()
layer = set()
order = Parallel()
new_fulfilled_items = set()
for item in last_layer:
if item not in parents:
# Current item is a stub
continue
# Check for new dependencies that might have come free
children = parents[item]
for child in children:
# Check if all dependencies are fulfilled
if dependencies[child] <= fulfilled and child not in fulfilled and child not in current:
layer.add(child)
for item in layer:
curr_tree = Serial(item)
new_fulfilled, layers, tree = resolve_layers(last_layer | set(item), fulfilled | set(item),
dependencies,
parents, current | layer)
new_fulfilled_items |= new_fulfilled
if len(tree) > 0:
curr_tree.extend(tree)
order.append(curr_tree)
layer |= new_fulfilled_items
return layer, flatten(order)
dependencies = dict()
parents = dict()
entities = set()
tree = dict()
for line in sys.stdin:
items = line.strip().split(' ')
entity = items[0].strip()
if entity == '':
continue
entities.add(entity)
if len(items) == 1:
continue
dep = items[1].strip()
if dep == '':
continue
entities.add(dep)
# Make a symmetric dictionary of what depends on what
# And what needs what
if dep not in dependencies:
dependencies[dep] = set()
dependencies[dep].add(entity)
if entity not in parents:
parents[entity] = set()
parents[entity].add(dep)
# Get all items without dependencies
top = dependencies.keys() ^ entities
TOP_KEY = ''
parents[TOP_KEY] = set(top)
start = set()
start.add(TOP_KEY)
for item in parents[TOP_KEY]:
dependencies[item] = set(start)
fulfilled, layers, tree = resolve_layers(set(start), set(start), dependencies, parents)
tree = flatten_self(tree)
print(' '.join(map(str, tree)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment