DEV Community


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

jbristow profile image
Jon Bristow • 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)
    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"))
  <Element, Int>("timeLeft", "total")
                .group<Element, Map<String, Int>>()
                .by(US.value<Property<Int>, Int>())
        .sortedBy<Map.Entry<Char, Map<String, Int>>, Int> { (name, p) ->
            when {
                p["total"]!! - p["timeLeft"]!! > 0 -> -1000 + name.toInt()
                else -> 1000 + name.toInt()

    return when {
        noInputs.isEmpty() -> time
        else -> {
            log.debug { { (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 = { it.value["timeLeft"]!! }.min()!!
    noInputs.forEach { (label, p) ->
        when {
            (p["timeLeft"]!! > minStep) ->
                V().has("name", label)
                    .property("timeLeft", p["timeLeft"]!! - minStep)
            else -> V().has("name", label).drop().iterate()
    return minStep