Discussion on: 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[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))
}