### re: AoC Day 7: The Sum of Its Parts VIEW POST

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