# Advent of Code 2019 - Day 14, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 14: 'Space Stoichiometry'

Posted on

Today we’ll write a binary search algorithm and a recursive algorithm to mine ore. Space ore.

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

Problem Input

The difficult part of our parsing algorithm today is deciding on an eventual data structure. The input today is quite complicated. What I think we want is a Map where the key is the material we want to make (Fuel, Ore, something else) and the value is two things: How much of the material the recipe can make, and the recipe to make it. Ultimately this comes down to `Map<String, Pair<Long, List<Pair<Long, String>>>>`, which I realize is super ugly.

``````Map<String, Pair<Long, List<Pair<Long, String>>>>
^           ^      ^    ^    ^      ^
|           |      |    |    |      +----- Recipe component material
|           |      |    |    +------------ Amount of recipe component material needed
|           |      |    +----------------- Recipe component
|           |      +---------------------- Recipe
|           +----------------------------- Amount of target material recipe makes
+----------------------------------------- Target material
``````

So if we had this line of input: `10 ORE => 1 A, 2 B`, we would end up with `mapOf("ORE", Pair(10, listOf(Pair(1, A), Pair(2, B))))`.

And to do that, we need to do a lot of String splitting:

``````
private fun parseInput(input: List<String>): Map<String, Pair<Long, List<Pair<Long, String>>>> =
input.map { row ->
val split: List<String> = row.split(" => ")
val left: List<Pair<Long, String>> = split.first().split(",")
.map { it.trim() }
.map {
it.split(" ").let { r ->
Pair(r.first().toLong(), r.last())
}
}
val (amount, type) = split.last().split(" ")
type to Pair(amount.toLong(), left)
}.toMap()
``````

#### Day 14, Part 1

The puzzle text can be found here.

The way I chose to solve this problem is through recursion. Let’s go over the algorithm.

1. Our function returns the cost (in Ore) to create the given `amount` of `material`
2. Our base case is being asked to find Ore. In that case, we return `amount` as the cost in Ore.
3. Otherwise, we’ll need to find the `recipe` for our `material`.
4. Next, we need to calculate how much of our `material` the `recipe` creates.
5. Using that, we now know how many times to run our recipe.
6. For every element in the recipe, we recursively ask our function to create it and report the cost in Ore to us.
7. Every time we’re about to create something, we’ll keep an inventory and check for what we need in there.

So, let’s get started…

``````private fun calculateCost(material: String = "FUEL",
amount: Long = 1,
inventory: MutableMap<String, Long> = mutableMapOf()): Long =
if (material == "ORE") amount
else {
val inventoryQuantity = inventory.getOrDefault(material, 0L)
val needQuantity = if (inventoryQuantity > 0) {
// We have some in inventory, check it out of inventory and reduce our need.
inventory[material] = (inventoryQuantity - amount).coerceAtLeast(0)
amount - inventoryQuantity
} else amount

if (needQuantity > 0) {
val recipe = cost.getValue(material)
val iterations: Int = ceil(needQuantity.toDouble() / recipe.first).toInt()
val actuallyProduced = recipe.first * iterations
if (needQuantity < actuallyProduced) {
// Put excess in inventory
inventory[material] = inventory.getOrDefault(material, 0) + actuallyProduced - needQuantity
}
// Go produce each of our dependencies
recipe.second.map { calculateCost(it.second, it.first * iterations, inventory) }.sum()
} else {
0
}
}
``````

Let’s go over it. Like any recursive algorithm we’ll handle the base case, Ore. If we are asked to create Ore, we just return the `amount` requested as its cost. In any other case, we’ll need to do some work. First, we’ll check how much of the requested material we have in `inventory`. Next, we’ll calculate the `needQuantity` by subtracting whatever we found in inventory. If we found what we need entirely in inventory, we take it and return a cost of 0, because it has already been created. If we didn’t find anything in inventory, our `needQuantity` is the original `amount` requested.

If inventory didn’t cover us, we’ll need to get the `recipe` and calculate how many times we need to execute it (`iterations`). This requires us to do some conversions between `Long` and `Double` because Kotlin rounds down for integer math and we want it rounded up. So, if our recipe can make 5 units, and we need 13, we’ll need to run the recipe 3 times, not 2.

Next, we figure out how much will be `actuallyProduced` and put any excess into `inventory`. This allows other parts of the overall recipe to take it.

Finally, we calculate our cost by summing the cost (in Ore) it takes to produce each component of our `recipe`, times the number of `iterations` we need to make.

And then we can solve Part 1 by calling this function with all the default values:

``````fun solvePart1(): Long =
calculateCost()
``````

Star earned!

#### Day 14, Part 2

The puzzle text can be found here.

For this part we’re going to perform a binary search to get to our answer. We’ll continuously ask our existing function to generate differing amounts of Fuel and figure out what number gets us closest to one trillion.

First, a constant:

``````companion object {
private const val one_trillion = 1_000_000_000_000L
}
``````

Next, we’ll use `LongRange` as the basis for our binary search:

``````private fun LongRange.binarySearchBy(fn: (Long) -> Int): Long {
var low = this.first
var high = this.last
while (low <= high) {
val mid = (low + high) / 2
when (fn(mid).sign) {
-1 -> high = mid - 1
1 -> low = mid + 1
0 -> return mid // Exact match
}
}
return low - 1 // Our next best guess
}
``````

Essentially, this will get us the element in the range that is closest to the target. Most binary search algorithms either return the value or nothing, but we want a lesser tolerance and are willing to take the number in the range that is the closest to costing one trillion ore. We start by taking the full range into account (from first to last). If we still haven’t found our answer, and our range has not inverted, we’ll calculate a mid-point and test that with our function. We’ll use `.sign` for the third day in a row and then analyze the results. If we get a -1, we know the `mid` we just tested is too high, so we set the high point to one less than the `mid`. We do the opposite if we get a 1 (`mid` is too low, move the low end up). If we get a 0, we’ve hit the target exactly. In the end, we’ll return either an exact match or `low -1`, which is as close as we’ll get.

Using this, we can set up a very large range and search it with our new function:

``````fun solvePart2(): Long =
(0L..one_trillion).binarySearchBy { one_trillion.compareTo(calculateCost(amount = it)) }
``````

And with that, we’ve earned another star!