# Advent of Code 2022 - Day 19, in Kotlin - Not Enough Minerals

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 19: 'Not Enough Minerals'

Posted on

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.toInt(),
oreRobot = RobotBlueprint(1, 0, 0, 0, parts.toInt()),
clayRobot = RobotBlueprint(0, 1, 0, 0, parts.toInt()),
obsidianRobot = RobotBlueprint(0, 0, 1, 0, parts.toInt(), parts.toInt()),
geodeRobot = RobotBlueprint(0, 0, 0, 1, parts.toInt(), 0, parts.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()
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 `ProductionState`s 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!
}        // <<<----- 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.