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

View post

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
}