Skip to Content

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!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2019, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 14
  4. Advent of Code - Come join in and do these challenges yourself!