DEV Community

Discussion on: AoC Day 7: The Sum of Its Parts

Collapse
 
bjarnemagnussen profile image
Bjarne Magnussen

The last part was difficult for me! Took me some time to figure out the small details to take care of.

For now here is my Python code. I am sure it can be simplified by a lot and made much more easy to read. Hopefully I will find time to do it later.

I am building a tree to solve this problem.

import copy

with open('input') as f:
    data = f.readlines()


class Node:
    def __init__(self, name, parents, children):
        self.name = name
        self.parents = parents
        self.parents_copy = parents
        self.children = children

    def __repr__(self):
        parents = [p.name for p in self.parents] if self.parents else None
        children = [c.name for c in self.children] if self.children else None
        return 'Node(name={}, parents={}, children={})'.format(
            self.name, parents, children)

    def add_parent(self, parent):
        if self.parents:
            self.parents.append(parent)
        else:
            self.parents = [parent]
        self.parents_copy = self.parents[:]

    def remove_parent(self, parent):
        if self.parents_copy:
            self.parents_copy.remove(parent)

    def add_child(self, child):
        if self.children:
            self.children.append(child)
        else:
            self.children = [child]

    def is_root(self):
        return self.parents_copy == []


nodes = {}

for d in data:
    node = nodes.get(d[5], Node(d[5], [], []))
    child = nodes.get(d[36], Node(d[36], [], []))
    node.add_child(child)
    child.add_parent(node)
    nodes[d[5]] = node
    nodes[d[36]] = child

nodes_bak = copy.deepcopy(nodes)

# Part 1:
# Traverse the tree:
path = []
job_times = {}
while len(nodes):
    # Find roots:
    roots = [n for n in nodes.values() if n.parents_copy == []]
    first_root = min(roots, key=lambda n: n.name)
    # Execute first_node and remove it as parent from its children:
    for c in first_root.children:
        c.remove_parent(first_root)
    # Remove node from global nodes list:
    del nodes[first_root.name]
    path.append(first_root.name)

print('Part 1:')
print(''.join(path))

# Part 2:
# Traverse the tree:
nodes = nodes_bak
path = []
worker_times = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0}
job_times = {}
while len(nodes):
    # Find roots:
    roots = [n for n in nodes.values() if n.parents_copy == []]
    # Select first_root by earliest time to add:
    min_time = float('inf')
    first_root = roots[0]
    for r in roots:
        # Time for all parents to have finished
        if len(r.parents) >= 2:
            max_parent_time = max(job_times.get(p.name, 0) for p in r.parents)
        elif len(r.parents) == 1:
            max_parent_time = job_times.get(r.parents[0].name, 0)
        else:
            max_parent_time = 0
        if max_parent_time <= min_time:
            if max_parent_time == min_time:
                first_root = min(first_root, r, key=lambda n: n.name)
            else:
                first_root = r
                min_time = max_parent_time
    # Select the worker that finishes earliest:
    earliest_worker = min(worker_times, key=worker_times.get)
    worker_times[earliest_worker] = (
        max(min_time, worker_times[earliest_worker])
        + ord(first_root.name) - 4  # Converts ASCII to decimal with time adjustment
    )
    # Adding total time it took for job to finish:
    job_times[first_root.name] = worker_times[earliest_worker]
    # Execute first_node and remove it as parent from its children:
    for c in first_root.children:
        c.remove_parent(first_root)
    # Remove node from global nodes list:
    del nodes[first_root.name]

print('Part 2:')
print(max(worker_times.values()))