DEV Community

AoC Day 7: The Sum of Its Parts

Ryan Palo on December 07, 2018

Day 7! I wasn't able to complete yesterday's challenge in time, but I'm going to keep working and hopefully get caught up this weekend. Neverthel...

Read full post

Tiago Romero Garcia • Dec 7 '18

Javascript solution

I decided to create a tree to represent each Step, adding dependencies and dependents for each steap, and a sorting algorithm to sort steps about to processed (i.e. when it has no dependents).

Then, I use a BFS traversal, employing a queue to visit the steps. In the 1st part, if a step has been processed but still has dependents, I re-add it to the end queue. For the 2nd part, I don't need this because then it won't be picked up by another worker, it remains with the same worker for the rest of the duration of that step.

reader.js

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

07-common.js

class Step {
    constructor(letter) {
        this.letter = letter;
        this.dependents = [];
        this.dependencies = [];
    }    

    addDependent(dependent) {
        this.dependents.push(dependent);
        dependent.dependencies.push(this);
    }
}

const regex = /^Step\s(?<dependency>\w)\smust\sbe\sfinished\sbefore\sstep\s(?<dependent>\w)\scan\sbegin\.$/;

const getStep = (steps, id) => {
    let step;
    if (steps.has(id)) {
        step = steps.get(id);
    }
    else {
        step = new Step(id);
        steps.set(id, step);
    }
    return step;
}

const buildSteps = lines => {
    const steps = new Map();
    for (let line of lines) {
        const { dependency, dependent } = line.match(regex).groups;
        const dependencyStep = getStep(steps, dependency);
        const dependentStep = getStep(steps, dependent);
        dependencyStep.addDependent(dependentStep);
    }
    return steps;
};

const getFirstSteps = steps => {
    const firstSteps = [...steps.values()].filter(step => step.dependencies.length === 0);

    return sortSimilarSteps(firstSteps);        
};

const sortSimilarSteps = steps => {
    return steps.sort((a, b) => a.letter.charCodeAt(0) - b.letter.charCodeAt(0));
};

module.exports = {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
};

07a.js

const { readFile } = require('./reader');
const {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
} = require('./07-common');

const getStepsOrder = steps => {    
    let stepsOrder = '';
    while (steps.length > 0) {
        const step = steps.shift();
        stepsOrder += step.letter;
        for (let dependent of step.dependents) {
            const index = dependent.dependencies.indexOf(step);
            dependent.dependencies.splice(index, 1);
            if (dependent.dependencies.length === 0) {
                steps.push(dependent);
            }
        }
        sortSimilarSteps(steps);
    }
    return stepsOrder;
};

(async () => {
    const lines = await readFile('07-input.txt');

    const steps = buildSteps(lines);
    const firstSteps = getFirstSteps(steps);
    const stepsOrder = getStepsOrder(firstSteps);

    console.log(`The steps order is ${stepsOrder}`);
})();

07b.js

const { readFile } = require('./reader');
const {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
} = require('./07-common');

const WARM_UP = 60;
const WORKERS = 15;

const getStepDuration = step => WARM_UP + step.letter.charCodeAt(0) - 64;

const getStepsTime = steps => {
    const workers = Array.from({ length: WORKERS }, w => new Object({ step: null }));

    let isThereWorkLeft = steps.length > 0;
    let stepsOrder = '';
    let totalSeconds = 0;
    while (isThereWorkLeft) {
        for (let worker of workers) {
            let step = worker.step;

            // If worker is done, go over dependents and get yourself a new step
            if (step && step.elapsedSeconds === getStepDuration(step)) {
                stepsOrder += step.letter;
                for (let dependent of step.dependents) {
                    const index = dependent.dependencies.indexOf(step);
                    dependent.dependencies.splice(index, 1);
                    if (dependent.dependencies.length === 0) {
                        steps.push(dependent);
                    }
                }
                sortSimilarSteps(steps);

                worker.step = null;
                step = null;
            }

            // Assigning new step
            if (!step) {
                step = steps.shift();
                if (!step) {
                    continue;
                }
                worker.step = step;
                step.worker = worker;
                step.elapsedSeconds = 0;
            }

            if (step.elapsedSeconds < getStepDuration(step)) {
                step.elapsedSeconds++;
            }
        }
        isThereWorkLeft = !!workers.find(w => !!w.step);
        if (isThereWorkLeft) {
            totalSeconds++;
        }
    }
    return { stepsOrder, totalSeconds };
};

(async () => {
    const lines = await readFile('07-input.txt');

    const steps = buildSteps(lines);
    const firstSteps = getFirstSteps(steps);
    const { totalSeconds } = getStepsTime(firstSteps);

    console.log(`The steps time is ${totalSeconds}`);
})();

Viktors Jenovs • Dec 7 '18 • Edited

Today I could figure out only the first part :( Wasted quite a bit of time because example input and real input had one big difference between data structures (and I assumed wrongly ;).

Part 1

<?php
$input = require_once 'readFile.php';

function findInitSteps($array) {
  $initSteps = [];
  foreach ($array as $value) {
    $finalSteps[] = $value[1];
  }
  foreach ($array as $value) {
    if (!in_array($value[0], $finalSteps) && !in_array($value[0], $initSteps)) {
      $initSteps[] = $value[0];
    }
  }
  sort($initSteps);
  return $initSteps;
}

$steps = array_map(function($str) {
  [, $first, $last] = preg_split("/.{5}(.).{30}(.).+/", $str, NULL, PREG_SPLIT_DELIM_CAPTURE);
  return [$first, $last];
}, $input);

$initSteps = findInitSteps($steps);

$completedSteps[] = array_shift($initSteps);

function findNextStep($steps, $completed) {
  $res = [];
  $incomplete = [];

  foreach ($steps as $key => [$mustBe, $nextStep]) {
    if (in_array($mustBe, $completed) && !in_array($nextStep, $completed)) {
      $res[] = $nextStep;
    } else {
      $incomplete[] = $nextStep;
    }
  }

  $cleanRes = [];
  foreach ($res as $value) {
    if (!in_array($value, $incomplete)) {
      $cleanRes[] = $value;
    }
  }
  if (count($cleanRes)) {
    sort($cleanRes);
    return $cleanRes[0];
  }
}

do {
  $next = findNextStep($steps, $completedSteps);

  if (count($initSteps)) {
    $temp = array_filter(array_merge($initSteps, [$next]));
    sort($temp);
    $temp2 = array_shift($temp);
    if ($next != $temp2) {
      $key = array_keys($initSteps, $temp2);
      array_splice($initSteps, $key[0], 1);
      $next = $temp2;
    }
  }

  $next && $completedSteps[] = $next;
} while ($next);

echo join($completedSteps) . "\n";
?>

readFile.php

<?php
$file = fopen("input.txt", "r") or exit("Unable to open file");
// $file = fopen("input_test.txt", "r") or exit("Unable to open file");

while(!feof($file)) {
  $array[] = fgets($file);
}

fclose($file);

return array_filter($array);
?>

Russ Hammett • Dec 8 '18

Yeah, I wish the sample was more representative of the actual data. I struggled with getting this part 1 done, and was not ready for part 2, to many differences and I had already spent more time on day 7 than any other day

Florian Rohrer • Dec 7 '18

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)

Jon Bristow • Dec 7 '18 • Edited

Kotlin TinkerPop/Gremlin Solution

Part 1

I feel really bad, but I kept banging my head on graph walking, so I gave up and pulled in a graph database to handle that for me.

My first solution was just stepping through g.V().not(inE()).order().by(property("name").value()).limit(1) and then dropping each one.

However, here's what a real property graph database solution would look like:

fun answer1(g: GraphTraversalSource, input: List<Step>): String {
    populateGraphDB(input, g)
    return g.processSteps("")
}

private tailrec fun GraphTraversalSource.processSteps(chain: String): String {
    val next = V().hasLabel(stepLabel)
        .not(US.inE())
        .order().by("name")
        .properties<Char>("name")
        .value<Char>().limit(1).tryNext()
    return when {
        !next.isPresent -> chain
        else -> {
            V().has("name", next.get()).drop().iterate()
            processSteps(chain + next.get())
        }
    }
}

Notes: If you see US in the code, that's a quick kotlinization of the __ groovy dsl, which doesn't play nicely with IntelliJ.

Part 2

Ok, now that I had a method for stepping through the graph, it was much easier to add resources and have time get updated in the DB as I traversed and deleted nodes.

At least, it would have been if I remembered how to gremlin. I spent more time than I'm willing to admit relearning my group() and order() semantics. Then I spent some time trying to make sure that my traversal prioritized items that were already started, as the sample gave different answers if your workers changed steps willy-nilly.

Post-submission optimization: you can just step down the minimum time of the nodes being worked on instead of 1.

fun answer2(
    g: GraphTraversalSource,
    input: List<Step>,
    helpers: Long,
    offset: Int
): Int? {
    populateGraphDB(input, g, offset)
    return g.workOnSteps(0, helpers + 1)
}

private tailrec fun GraphTraversalSource.workOnSteps(
    time: Int,
    workers: Long
): Int {
    val noInputs = V().hasLabel(stepLabel).not(US.inE())
        .group<Char, Map<String, Int>>()
        .by(US.values<Element, Char>("name"))
        .by(
            US.properties<Element, Int>("timeLeft", "total")
                .group<Element, Map<String, Int>>()
                .by(US.label<Element>())
                .by(US.value<Property<Int>, Int>())
        ).next()
        .asSequence()
        .sortedBy<Map.Entry<Char, Map<String, Int>>, Int> { (name, p) ->
            when {
                p["total"]!! - p["timeLeft"]!! > 0 -> -1000 + name.toInt()
                else -> 1000 + name.toInt()
            }
        }.toList()
        .take(workers.toInt())

    return when {
        noInputs.isEmpty() -> time
        else -> {
            log.debug { noInputs.map { (k, v) -> k to v["timeLeft"] } }
            val timeStep = decrementOrDrop(noInputs)
            workOnSteps(time + timeStep, workers)
        }
    }
}

private fun GraphTraversalSource.decrementOrDrop(
    noInputs: List<Map.Entry<Char, Map<String, Int>>>
): Int {
    val minStep = noInputs.map { it.value["timeLeft"]!! }.min()!!
    noInputs.forEach { (label, p) ->
        when {
            (p["timeLeft"]!! > minStep) ->
                V().has("name", label)
                    .property("timeLeft", p["timeLeft"]!! - minStep)
                    .next()
            else -> V().has("name", label).drop().iterate()
        }
    }
    return minStep
}

Thomas Rayner • Dec 7 '18

This is my C# solution. I'm using Advent of Code this year to practice C# so I'm sure there's lots of opportunity for improvement, but it works! I only work on these in the half hour between getting to work and my workday starting (don't ask) and sometimes at lunch, so I might fall pretty far behind after this weekend...

Mustafa Haddara • Dec 7 '18

I quite liked this puzzle! It took me a few false starts-- I couldn't decide whether to track a step's dependencies or dependents --but ultimately I quite like the way my code turned out. Calling sort on every step seemed...wasteful...to me, but it was fast enough, so it all worked out in the end.

Here's my Julia code (boring parsing, etc. omitted but available here)

function step_ordering(input)
    step_map = parse_input(input)
    result = alpha_bfs(step_map)

    return result
end

function alpha_bfs(step_map)
    roots = find_roots(step_map)
    result = ""
    seen = Set()
    while (!isempty(roots))
        sort!(roots)
        found = popfirst!(roots)
        result *= found

        for other in values(step_map)
            delete!(other.prev, found)
            if isempty(other.prev) && !(other.name in seen)
                push!(seen, other.name)
                push!(roots, other.name)
            end
        end
    end
    return result
end

function find_roots(step_map)
    all_nodes = Set{String}()
    for node in values(step_map)
        for prev in node.prev
            push!(all_nodes, prev)
        end
    end

    return collect(setdiff(all_nodes, keys(step_map)))
end

Part 2 was also enjoyable-- I briefly considered actually spawning 5 worker threads and keeping a global clock, but then I realized I could just track how much work was being done in between tracking which nodes are now available.

function costed_alpha_bfs(step_map)
    roots = find_roots(step_map)
    result = ""
    seen = Set()
    total_time = 0
    costs = Dict{String, Int}()
    base_cost = 60
    max_workers = 5
    workers = max_workers
    while (!isempty(roots) || !isempty(costs))
        sort!(roots)
        while workers > 0 && !isempty(roots)
            found = popfirst!(roots)
            costs[found] = cost_of_node(found) + base_cost
            workers -= 1
        end

        (cost,found) = findmin(costs)
        result *= found
        total_time += cost
        workers = min(max_workers, workers+1)

        delete!(costs, found)
        for in_progress in keys(costs)
            costs[in_progress] -= cost
        end

        for other in values(step_map)
            delete!(other.prev, found)
            if isempty(other.prev) && !(other.name in seen)
                push!(seen, other.name)
                push!(roots, other.name)
            end
        end
    end

    return total_time
end

Carly Ho 🌈 • Dec 7 '18

PHP

ohhhhh my god this one took me a really long time for a variety of goofy reasons, mostly not understanding how things were supposed to work correctly

Part 1:

<?php
$input = file_get_contents($argv[1]);
$instructions = explode("\n", trim($input));
$steplist = str_split('ABCDEFGHIJKLMNOPQRSTUVWXYZ');
$steps = array();
$after = array();
foreach ($steplist as $s) {
  $after[$s] = array();
}
foreach ($instructions as $inst) {
  preg_match('/Step ([A-Z]) must be finished before step ([A-Z]) can begin./', $inst, $stepnames);
  array_push($after[$stepnames[2]], $stepnames[1]);
}

foreach($steplist as $i=>$step) {
  if (count($after[$step]) == 0) {
    array_push($steps, $step);
    unset($after[$step]);
    while (count($after)) {
      $next_candidates = array_filter($after, function($v, $k) {
        global $steps;
        if (array_intersect($v, $steps) == $v) {
          return true;
        }
        return false;
      }, ARRAY_FILTER_USE_BOTH);
      ksort($next_candidates);
      if ($next_candidates) {
        $next = array_keys($next_candidates)[0];
        array_push($steps, $next);
        unset($after[$next]);
      } else {
        break;
      }
    }
    break;
  }
}

echo join("", $steps);

die(1);

Part 2:

<?php
$input = file_get_contents($argv[1]);
$instructions = explode("\n", trim($input));
$steplist = str_split('ABCDEFGHIJKLMNOPQRSTUVWXYZ');
$times = array_combine($steplist, array_map(function($x) {
    return $x+61;
}, array_flip($steplist)));
$steps = array();
$after = array();
foreach ($steplist as $s) {
  $after[$s] = array();
}
foreach ($instructions as $inst) {
  preg_match('/Step ([A-Z]) must be finished before step ([A-Z]) can begin./', $inst, $stepnames);
  array_push($after[$stepnames[2]], $stepnames[1]);
}

$completed = array();
$workers = array_fill(0, 5, array(
    'step' => null,
    'start_time' => 0
));
$time = 0;
$next_candidates = array_filter($after, function($v, $k) {
    if (count($v) == 0) {
        return true;
    }
    return false;
}, ARRAY_FILTER_USE_BOTH);

ksort($next_candidates);

if ($next_candidates) {
    foreach(array_keys($next_candidates) as $n) {
        foreach ($workers as $i=>$worker) {
            if (!$worker['step']) {
                echo "assigning ".$n." to worker ".($i+1)." to start at ".$time."\n";
                $workers[$i]['step'] = $n;
                $workers[$i]['start_time'] = $time;
                unset($after[$n]);
                break;
            }
        }
    }
}
while (count($completed) < count($steplist)) {
    $availableWorkers = 0;
    foreach($workers as $i=>$w) {
        if ($w['step'] && $times[$w['step']]+$w['start_time']-1 == $time) {
            array_push($completed, $w['step']);
            echo "Step ".$w['step']." completed by worker ".($i+1)." at ".$time." seconds\n";
            $workers[$i]['step'] = null;
            $availableWorkers++;
            echo join("", $completed)."\n";
        }
    }
    $time++;
    if (count($completed) == count($steplist)) {
        break;
    }
    if (count($completed) > 0 && $availableWorkers > 0) {
        $next_candidates = array_filter($after, function($v, $k) {
            global $completed;
            if (array_intersect($v, $completed) == $v) {
                return true;
            }
            return false;
        }, ARRAY_FILTER_USE_BOTH);
        ksort($next_candidates);
        if ($next_candidates) {
            foreach(array_keys($next_candidates) as $n) {
                foreach ($workers as $i=>$worker) {
                    if (!$worker['step']) {
                        echo "assigning ".$n." to worker ".($i+1)." to start at ".$time."\n";
                        $workers[$i]['step'] = $n;
                        $workers[$i]['start_time'] = $time;
                        unset($after[$n]);
                        break;
                    }
                }
            }
        }
    }
}
echo $time;

die(1);

Bjarne Magnussen • Dec 7 '18

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()))

Neil Gall • Dec 8 '18

I was convinced at first I could sort the steps like this:

if there's a path from a to b, a < b
if there's a path from b to a, a > b
else compare a.name, b.name

It worked on the test data, but not on the full problem. I was really frustrated for a while, and had to google it, coming up with Kahn's algorithm

I went through an imperative, mutation-heavy version first but my Kotlin for part 1 ended up like this:

typealias Name = String
data class Instruction(val before: Name, val after: Name)

fun allNames(input: List<Instruction>): Set<Name> =
    (input.map { it.before } + input.map { it.after }).toSet()

fun initials(input: List<Instruction>): Set<Name> =
    allNames(input) - (input.map { it.after }.toSet())

fun from(n: Name): (Instruction) -> Boolean = { i -> i.before == n }
fun to(n: Name): (Instruction) -> Boolean = { i -> i.after == n }

fun topologicalOrder(input: List<Instruction>): List<Name> {
    tailrec fun sort(graph: List<Instruction>, stack: List<Name>, result: List<Name>): List<Name> =
        if (stack.isEmpty())
            result
        else {
            val step = stack.first()
            val (edges, graph_) = graph.partition(from(step))
            val next = edges.filter { e -> graph_.none(to(e.after)) }.map { e -> e.after }
            val stack_ = (stack.drop(1) + next).sorted()
            sort(graph_, stack_, result + step)            
        }

    return sort(input, initials(input).toList(), listOf())
}

Once I got there, I found part 2 to be a fairly straightforward extension to parallelise the work and keep track of remaining time. One trick was to make the Work ordering put in-progress work first, so on each iterations the workers pulled active steps from the stack first.

typealias Time = Int
data class Work(val name: Name, val remaining: Time): Comparable<Work> {
    companion object {
        fun time(name: Name): Time = name[0] - 'A' + 61
    }

    constructor(name: Name): this(name, time(name))

    fun doWork(time: Time): Work = Work(name, remaining - time)

    fun inProgress(): Boolean = remaining < time(name)
    fun done(): Boolean = remaining <= 0

    fun tag(): String = "${if (inProgress()) 0 else 1}${name}"

    override fun compareTo(other: Work): Int = tag().compareTo(other.tag())
}

data class Result(val steps: List<Name>, val time: Time) {
    fun add(done: List<Work>, progress: Time) = Result(steps + done.map { w -> w.name }, time + progress)
}

fun parallelTopologicalOrder(input: List<Instruction>, workers: Int): Result {
    tailrec fun sort(graph: List<Instruction>, stack: List<Work>, result: Result): Result =
        if (stack.isEmpty())
            result
        else {
            val active = stack.take(workers)
            val progress = active.minBy { w -> w.remaining }?.remaining ?: throw IllegalStateException()
            val advance = active.map { w -> w.doWork(progress) }
            val done = advance.filter(Work::done)

            val (edges, graph_) = done.fold(Pair(setOf<Instruction>(), graph)) { (e, g), step -> 
                val (e_, g_) = g.partition(from(step.name))
                Pair(e + e_, g_)
            }
            val next = edges.filter { e -> graph_.none(to(e.after)) }.map { e -> Work(e.after) }
            val stack_ = (stack.drop(workers) + advance.filterNot(Work::done) + next).sorted()
            val result_ = result.add(done, progress)

            sort(graph_, stack_, result_)
        }

    val initialWork = initials(input).map(::Work)
    return sort(input, initialWork, Result(listOf(), 0))
}

Ryan Palo • Dec 9 '18

Got my Rust solution done! After banging my head on it all yesterday, I'm glad I took a break and came back fresh. It seemed to go pretty smoothly the second try at it.

Part 1

/// Day 7: Sum of Its Parts
/// 
/// Unravel the order of instructions with dependencies

use std::collections::{HashMap, HashSet};
use std::cmp;

// Part 1: In what order should the steps be completed?

struct DependencyGraph {
    instructions: HashMap<char, Vec<char>>,
}

impl DependencyGraph {
    pub fn new() -> Self {
        Self { instructions: HashMap::new() }
    }

    pub fn from_instructions(text: &str) -> Self {
        let mut deps = DependencyGraph::new();
        for line in text.lines() {
            let parent = line.chars().take(6).last().unwrap();
            let child = line.chars().take(37).last().unwrap();
            deps.add_dependency(parent, child);
        }
        deps
    }

    pub fn add_dependency(&mut self, parent: char, child: char) {
        self.instructions.entry(parent).or_insert(vec![]);
        let child_deps = self.instructions.entry(child).or_insert(vec![]);
        child_deps.push(parent);
    }

    pub fn linearize(&self) -> Vec<char> {
        let mut results: Vec<char> = vec![];
        let mut pending: HashSet<char> = self.instructions.keys().cloned().collect();
        while pending.len() > 0 {
            let mut satisfied: Vec<char> = self.instructions.iter()
                .filter(|(c, deps)| {
                    pending.contains(c) &&
                    deps.iter().all(|dep| !pending.contains(dep))
                })
                .map(|(c, deps)| c.clone())
                .collect();
            satisfied.sort();
            results.push(satisfied[0]);
            pending.remove(&satisfied[0]);
        }
        results
    }
}

/// Given lines of dependencies, processes those dependencies into a linear
/// ordered string of instructions.
pub fn order_steps(text: &str) -> String {
    let deps = DependencyGraph::from_instructions(text);
    deps.linearize().into_iter().collect()
}

Part 2

In part 2, I'm pretty sure we just re-invented the event loop? This mega-function could probably be boiled down to helper functions, but I'm OK with this for now.

// Part 2: How long will it take to complete all the steps?

impl DependencyGraph {

    /// Calculate how long it would take if each step has a duration and
    /// you have some elves helping you
    pub fn assisted_assembly_duration(&self, workers: usize, base_delay: usize) -> usize {
        let mut pending: HashSet<char> = self.instructions.keys().cloned().collect();
        let mut active: HashMap<char, usize> = HashMap::new();
        let mut clock: usize = 0;

        while pending.len() + active.len() > 0{
            // check for completed steps
            let completed: Vec<char> = active.iter()
                .filter(|(_c, finish)| clock >= **finish)
                .map(|(c, _finish)| c).cloned().collect();
            for letter in completed {
                active.remove(&letter);
            }

            // Get any tasks available to be worked on
            let mut satisfied: Vec<char> = self.instructions.iter()
                .filter(|(c, deps)| {
                    pending.contains(c) &&
                    deps.iter()
                    .all(|dep| !pending.contains(dep) && !active.contains_key(dep))
                })
                .map(|(c, deps)| c.clone())
                .collect();
            satisfied.sort();

            // Give any free workers a task
            let tasks_to_assign = cmp::min(workers - active.len(), satisfied.len());
            for letter in satisfied.iter().take(tasks_to_assign) {
                // This job will get done duration + base_delay seconds from now
                active.insert(*letter, 
                    DependencyGraph::duration_for(*letter) + base_delay + clock);
                pending.remove(letter);
            }

            clock += 1;
        }

        // Un-tick the clock, since the clock ticks at the end.
        clock - 1
    }

    /// Calculates how long a letter will take to process
    /// 
    /// The duration of each letter is increased by one as the letters
    /// increase, starting at A = 1
    /// Assumes (correctly) that all letters are capital
    fn duration_for(letter: char) -> usize {
        (letter as usize) - ('A' as usize) + 1
    }
}

/// Find out how long to run a set of tasks with helpers
pub fn assisted_duration(text: &str, workers: usize, base_delay: usize) -> usize {
    let deps = DependencyGraph::from_instructions(text);
    deps.assisted_assembly_duration(workers, base_delay)
}

Ali Spittel • Dec 9 '18

Solved super late but:

shared:

def clean_input(data):
    relationships = defaultdict(set)
    for line in data:
        _, parent, child = re.findall(r'[A-Z]', line)
        relationships[child].add(parent)
        if parent not in relationships:
            relationships[parent] = set()
    return relationships

with open ('input.txt', 'r') as f:
    relationships = clean_input(f)

def find_order(relationships):
    done = []
    while len(done) < len(relationships):
        ready = []
        for node in relationships:
            if node not in done and relationships[node].issubset(done):
                ready.append(node)
        done.append(sorted(ready)[0])
    return done

print(''.join(find_order(relationships)))


def letter_to_number(letter):
    return ascii_uppercase.index(letter) + 61


def find_time(relationships):
    total = 0
    done = []
    N_WORKERS = 5
    enqueued = [None] * N_WORKERS

    while len(done) < len(relationships):
        print(enqueued)
        for i, value in enumerate(enqueued):
            if value:
                letter, time = value
                if time == 1:
                    done.append(letter)
                    enqueued[i] = None
                else:
                    enqueued[i][1] -= 1
        for node in relationships:
            letters_enqueued = [i[0] for i in enqueued if i]
            if node not in done and node not in letters_enqueued and relationships[node].issubset(done) and None in enqueued:
                enqueued[enqueued.index(None)] = [node, letter_to_number(node)]
        total += 1
    return total - 1

print(find_time(relationships))

Matt Morgis • Dec 12 '18 • Edited

Used d3.js to visualize part 1

Ryan Palo • Dec 12 '18

Awesome again!