DEV Community

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

View post
Collapse
 
r0f1 profile image
Florian Rohrer •

Fighting my way up the leaderboard.

My Python Solution

Part 1

import networkx as nx
import numpy as np

with open("input.txt") as f:
    edges = [(l[5], l[36]) for l in f]

u, v = zip(*edges)
G = nx.DiGraph()
G.add_edges_from(edges)

def get_next_fullfilled_node(seen, open_nodes):
    for n in sorted(open_nodes):
        if all(k in seen for k in G.predecessors(n)):
            return n
open_nodes = set(u)-set(v)

seen = set()
while open_nodes:
    n = get_next_fullfilled_node(seen, open_nodes)
    print(n, end="")
    seen.add(n)
    for k in G[n]:
        open_nodes.add(k)
    open_nodes -= seen

Part 2

class Worker(object):
    def __init__(self):
        self.slots = np.array([0 for _ in range(10_000)])
    def is_free(self, t):
        return self.slots[t] == 0
    def add(self, start_t, c):
        end_t = start_t+ord(c)-ord('A')+61
        self.slots[start_t:end_t] = 1
        return end_t
    def finish_time(self):
        return max(i for i, e in enumerate(self.slots) if e == 1)

def assign_to_workers(task, workers, time):
    while True:
        for w in workers:
            if w.is_free(time):
                return w.add(time, task)
        time += 1

def get_next_fullfilled_node_time(tasks_done, open_nodes, time):
    for n in sorted(open_nodes):
        ok = True
        for k in G.predecessors(n):
            if k not in tasks_done or tasks_done[k] > time:
                ok = False
                break
        if ok:
            return n
    return None

workers = [Worker() for _ in range(5)]
tasks_done = {}
open_nodes = set(u)-set(v)
time = 0
while open_nodes:
    n = get_next_fullfilled_node_time(tasks_done, open_nodes, time)
    if n is None:
        time += 1 
        continue
    for k in G[n]:
        open_nodes.add(k)
    tasks_done[n] = assign_to_workers(n, workers, time)
    open_nodes -= tasks_done.keys()
print(max(w.finish_time() for w in workers)+1)