Advent of Code 2022 - Day 19, in Kotlin - Not Enough Minerals • Todd Ginsberg

This puzzle is an exercise in finding all of the various ways to not do work. Not that I’m any good at that [note: my boss reads these]. Ahem. Anyway. Every time I added an optimization to avoid doing work, I was sure this would be the one thing that put us over the edge. And like a lot of real-world optimization efforts, lots of small improvements generally add up.

If you’d rather just view code, the GitHub Repository is here .

Puzzle Input

Ultimately, we will store our input in a Blueprint class that describes everything about the construction requirements for the given blueprint. However, since building the various robots is a somewhat repetitive process, we’re going to store data about that in a RobotBlueprint class. In addition to the oreCost, clayCost, and obsidianCost which describe the number of units of each material required to build a robot, we also have counters for how many of each robot are produced by this blueprint. Why is this an Int and not a Boolean? Because later on it will be easier to just add these numbers when we start building robots, rather than testing for true/false.

// In Day19

private data class RobotBlueprint(
    val oreRobotsBuilt: Int,
    val clayRobotsBuilt: Int,
    val obsidianRobotsBuilt: Int,
    val geodeRobotsBuilt: Int,
    val oreCost: Int,
    val clayCost: Int = 0,
    val obsidianCost: Int = 0
)

And we will use these in Blueprint, one for each type of robot we could build, along with the id of the blueprint. And as usual, we’ll add an of function to the companion object and have it parse our input. Thankfully our input is very regular, so we can split it by space and colon and grab specific columns to represent the costs.

// In Day19

private data class Blueprint(
    val id: Int,
    val oreRobot: RobotBlueprint,
    val clayRobot: RobotBlueprint,
    val obsidianRobot: RobotBlueprint,
    val geodeRobot: RobotBlueprint
) {

    companion object {
        fun of(input: String): Blueprint {
            val parts = input.split(" ", ": ")
            return Blueprint(
                id = parts[1].toInt(),
                oreRobot = RobotBlueprint(1, 0, 0, 0, parts[6].toInt()),
                clayRobot = RobotBlueprint(0, 1, 0, 0, parts[12].toInt()),
                obsidianRobot = RobotBlueprint(0, 0, 1, 0, parts[18].toInt(), parts[21].toInt()),
                geodeRobot = RobotBlueprint(0, 0, 0, 1, parts[27].toInt(), 0, parts[30].toInt()),
            )
        }
    }
}

And we’ll store all of these in a List<Blueprint> called blueprints (yeah, original, right?).

class Day19(input: List<String>) {

    private val blueprints: List<Blueprint> = input.map { Blueprint.of(it) }

}

⭐ Day 19, Part 1

The puzzle text can be found here.

Normally, I like to document things from the “bottom up”. Meaning, start with the functions we call deep down in the call tree and work back out. That way we can understand what the details are as we build up a bigger picture. But today, I think this solution might be easier to understand “top down”. Meaning, start with the function we’d call first and work down from there.

So let’s start with calculateGeodesFound, the function we’ll call to figure out how many geodes a blueprint can produce given a timeBudget.

// In Day19

private fun calculateGeodesFound(blueprint: Blueprint, timeBudget: Int): Int {
    var maxGeodes = 0
    val queue = PriorityQueue<ProductionState>().apply { add(ProductionState()) }

    while(queue.isNotEmpty()){
        val state = queue.poll()
        queue.addAll(state.calculateNextStates(blueprint, timeBudget))
        maxGeodes = maxOf(maxGeodes, state.geodes)
    }

    return maxGeodes
}

This might look a lot like code from the last few days. We set up a queue, we add a default ProductionState to it (more on this later) and start pulling work off the queue while it isn’t empty. This time, our queue is a PriorityQueue so we can schedule work to our benefit. In Part Two, we’ll want to start eliminating work that doesn’t make sense, and having the work in an order where items with a higher geode count come before items with a lower geode count will help us.

Every time we poll the queue, we take the state off the front of the queue. We ask the state to calculateNextState again given the blueprint and timeBudget. This function is responsible for telling us what work we’ll do in the future, given this state. More on that later.

Let’s look at ProductionState, the class we’re using in our queue. The first thing to notice is that it implements Comparable<ProductionState>, and orders the objects such that ProductionStates with more geodes come after states with fewer geodes. The next thing to notice is the properties - one for time, and for each mineral the amount of that mineral on hand, and the number of robots producing that mineral every turn.

// In Day19

private data class ProductionState(
    val time: Int = 1,
    val ore: Int = 1,
    val oreRobots: Int = 1,
    val clay: Int = 0,
    val clayRobots: Int = 0,
    val obsidian: Int = 0,
    val obsidianRobots: Int = 0,
    val geodes: Int = 0,
    val geodeRobots: Int = 0
): Comparable<ProductionState> {

    override fun compareTo(other: ProductionState): Int = other.geodes.compareTo(geodes)

    fun calculateNextStates(blueprint: Blueprint, timeBudget: Int): List<ProductionState> {
        val nextStates = mutableListOf<ProductionState>()
        if (time < timeBudget) {
            if (blueprint.maxOre > oreRobots && ore > 0) {
                nextStates += blueprint.oreRobot.scheduleBuild(this)
            }
            if (blueprint.maxClay > clayRobots && ore > 0) {
                nextStates += blueprint.clayRobot.scheduleBuild(this)
            }
            if (blueprint.maxObsidian > obsidianRobots && ore > 0 && clay > 0) {
                nextStates += blueprint.obsidianRobot.scheduleBuild(this)
            }
            if (ore > 0 && obsidian > 0) {
                nextStates += blueprint.geodeRobot.scheduleBuild(this)
            }
        }
        return nextStates.filter { it.time <= timeBudget }
    }
}

Let’s focus on the calculateNextStates function. What’s the theory here? For a given state, we will schedule the creation of every type of robot in the future. Suppose we are at time 1. We will figure out how far in the future we will have to wait for each type of robot to be built, and then schedule that work as another ProductionState object. For example, if we determine that we have enough ore on hand to build a clay robot in the next turn, we schedule that work for 1 turn from now. If we determine that (hypothetically) we could build an obsidian robot but we have to wait 3 turns, then we schedule that work for 3 turns from now. This saves us a lot of intermediate steps.

So keeping that in mind, let’s continue our analysis of calculateNextSteps. The first optimization we make is to not bother creating more work if we’re out of time. We also add an important optimization - don’t bother trying to build something if there aren’t any materials for it at all. No sense building geode robots if you don’t have any obsidian, right? The last optimization is probably the most important - once we have enough robots to produce enough of a certain type of material to build every type of robot, stop building more of those robots. For example, if the maximum number of clay something costs is 3, it never makes sense to have more than 3 clay robots. It will produce more than we can consume in a single turn. And since we can only build one thing a turn, we’ll never exhaust that supply.

So let’s add those properties to Blueprint to help us:

// In Day19.Blueprint

val maxOre: Int =
    maxOf(oreRobot.oreCost, clayRobot.oreCost, obsidianRobot.oreCost, geodeRobot.oreCost)

val maxClay: Int =
    maxOf(oreRobot.clayCost, clayRobot.clayCost, obsidianRobot.clayCost, geodeRobot.clayCost)

val maxObsidian: Int =
    maxOf(oreRobot.obsidianCost, clayRobot.obsidianCost, obsidianRobot.obsidianCost, geodeRobot.obsidianCost)

Now that we know when to build a robot, we need to figure out how to schedule it and what the future state of ProductionState will look like at that point in time.

Back to RobotBlueprint, let’s add a function called timeUntilBuild that tells us how many turns we need to wait around until we can build the type of robot we call the function on.

// In Day19.RobotBlueprint

private fun timeUntilBuild(productionState: ProductionState): Int =
    maxOf(
        if (oreCost <= productionState.ore) 0 else ceil((oreCost - productionState.ore) / productionState.oreRobots.toFloat()).toInt(),
        if (clayCost <= productionState.clay) 0 else ceil((clayCost - productionState.clay) / productionState.clayRobots.toFloat()).toInt(),
        if (obsidianCost <= productionState.obsidian) 0 else ceil((obsidianCost - productionState.obsidian) / productionState.obsidianRobots.toFloat()).toInt()
    ) + 1

We have to examine each of the materials to properly calculate the “how many turns from now” question. We look at the amount of material the robot costs, how much material we have on hand, and how many we produce per turn. When we divide, we need to take care to take the ceiling of the division calculation (if we need 5, and produce 2 per turn, we need to wait 3 turns, not 2). As me how I know this.

And now that we have all that, we can get to the actual scheduleBuild function. This takes in a ProductionState and returns a new ProductionState that represents the state of the factory at some exact point in the future when we build a specific type of robot.

// In Day19.RobotBlueprint

fun scheduleBuild(state: ProductionState): ProductionState {
    val timeRequired = timeUntilBuild(state)
    return state.copy(
        time = state.time + timeRequired,
        ore = (state.ore - oreCost) + (timeRequired * state.oreRobots),
        oreRobots = state.oreRobots + oreRobotsBuilt,
        clay = (state.clay - clayCost) + (timeRequired * state.clayRobots),
        clayRobots = state.clayRobots + clayRobotsBuilt,
        obsidian = (state.obsidian - obsidianCost) + (timeRequired * state.obsidianRobots),
        obsidianRobots = state.obsidianRobots + obsidianRobotsBuilt,
        geodes = state.geodes + (timeRequired * state.geodeRobots),
        geodeRobots = state.geodeRobots + geodeRobotsBuilt
    )
}

That might look messy, but that’s about as clean as I could get it. Basically, we have to figure out how much timeRequired there is to perform the build (using the function we just wrote), and then use that to accrue all of the materials. For example, if we have to wait two turns, we need to build up our materials for two turns. We also need to add 1 to the number of robots we’re building at that point in the future. This is why geodeRobotsBuilt and friends are Int and not Boolean - it makes this part easier.

All that’s left to do is call calculateGeodesFound for each blueprint and multiply by its id.

// In Day19

fun solvePart1(): Int =
    blueprints.sumOf { it.id * calculateGeodesFound(it, 24) }

Star earned! Onward!

⭐ Day 19, Part 2

The puzzle text can be found here.

Go ahead and run the Part One code for Part Two by increasing the timeBudget to 32. I’ll wait. I’m willing to bet you ran out of memory just like I did.

This calls for more optimizations. Remember how we decided way way way up above to order the work such that states with more geodes comes before work with fewer geodes? Let’s see if we can start removing some of the work from the queue. When we have a state, and are looking to produce the next possible states based on that, it makes no sense to even try if the current state can’t ever produce more geodes than some other state already has. For example, if our maxGeodes is 10, and we have a state whose maximum potential is only 9 geodes, why bother creating next states for it?

Let’s add a canOutproduceBest function to ProductionState:

// In Day19.ProductionState

fun canOutproduceBest(bestSoFar: Int, timeBudget: Int): Boolean {
    val timeLeft = timeBudget - time
    val potentialProduction = (0 until timeLeft).sumOf { it + geodeRobots }
    return geodes + potentialProduction > bestSoFar
}

The canOutproduceBest function calculates the timeLeft in the run, and assumes optimistically that we built a geode robot once per turn. This is the absolute max potential of this state, even if it won’t happen for all (or even any) future states based on this one. This doesn’t sound like much but it eliminates millions of possible states from evaluation. So we assume that a state canOutproduceBest if it has even the potential to produce more geodes than we’ve already actually produced via some other state.

Adding a call to canOutproduceBest before deciding to calculateNextStates makes our calculateGeodesFound function look like this now:

// In Day19

private fun calculateGeodesFound(blueprint: Blueprint, timeBudget: Int): Int {
    var maxGeodes = 0
    val queue = PriorityQueue<ProductionState>().apply { add(ProductionState()) }

    while(queue.isNotEmpty()){
        val state = queue.poll()
        if (state.canOutproduceBest(maxGeodes, timeBudget)) {       // <<<----- NEW!
            queue.addAll(state.calculateNextStates(blueprint, timeBudget))
        }        // <<<----- NEW!
        maxGeodes = maxOf(maxGeodes, state.geodes)
    }

    return maxGeodes
}

Now it will run fast enough. This time we only care about the first three blueprints so we take the first 3, calculateGeodesFound for each one, and then reduce those numbers via Int::times.

// In Day19

fun solvePart2(): Int =
    blueprints.take(3).map { calculateGeodesFound(it, 32) }.reduce(Int::times)

Star earned! See you tomorrow.

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading