Advent of Code 2022 - Day 21, in Kotlin - Monkey Math • Todd Ginsberg

I really liked this puzzle, and it has given me a much needed boost of positive energy after the last few days, which I ended up spending a lot of time on. Today, we’ll build a tree structure and use it to help solve both Part One and Part Two.

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

Puzzle Input

We’ll start by defining a Monkey interface and two implementations - NumberMonkey (which just represents a number), and FormulaMonkey which represents a left side Monkey, a right side Monkey and an op (operation) to perform on those sides. I had considered making these a sealed class structure, but since these are all private to the Day21 class, and I don’t ever need to know an exhaustive list of subclasses, I just went with an interface and two implementations.

The interface itself mandates that each Monkey must have a name and must yell() (truly, the mark of a great interface). I really need you to know that I fought very hard with myself not to rename yell as YELL.

One thing I’m doing differently today, just to show you a technique I sometimes like to use, is to define an invoke operator in the companion, rather than an of function like we normally have. It does the same thing, but makes the syntax for calling it a bit nicer. In our case, we can say Monkey(someRowOfInput) and invoke will be called. Neat, huh? I like to use this when I do actually have a sealed interface/class structure so the top class (or interface) can act like a factory. The caller thinks they are just dealing with Monkey, but as you can see, a specific implementation is returned.

// In Day21

private interface Monkey {
    val name: String
    fun yell(): Long

    companion object {
        operator fun invoke(row: String): Monkey {
            val name = row.substringBefore(":")
            return if (row.length == 17) {
                FormulaMonkey(name, row.substring(6..9), row.substringAfterLast(" "), row[11])
            } else {
                NumberMonkey(name, row.substringAfter(" ").toLong())
            }
        }
    }
}

And as usual, I’ll use substring, substringBefore, substringAfter, and substringAfterLast rather than use regular expressions.

The NumberMonkey has a simple implementation. When we call yell, it returns its number.

// In Day21

private class NumberMonkey(
        override val name: String,
        val number: Long
    ) : Monkey {
        override fun yell(): Long = number
    }

On the other hand, FormulaMonkey is a bit more complicated. We take in a String for both the leftName and rightName since when we are parsing the Monkey instances from the input, we only have String names and not instances of Monkey yet. We’ll define two lateinit var to hold the left and right actual Monkey instances and use them in our calculations, ignoring the string versions.

For the FormulaMonkey, when we call yell it takes the left value and the right value and performs an op, which we will implement as an extension function on Long.

// In Day21

private class FormulaMonkey(
    override val name: String,
    val leftName: String,
    val rightName: String,
    val op: Char
) : Monkey {
    lateinit var left: Monkey
    lateinit var right: Monkey

    override fun yell(): Long =
        left.yell() op right.yell()

    private infix fun Long.op(right: Long): Long =
        when (op) {
            '+' -> this + right
            '-' -> this - right
            '*' -> this * right
            else -> this / right
        }
}

And to parse all of our input into a Set<Monkey>, we’ll define a parseInput function which rectifies the FormulaMonkey references. When the Monkey.invoke function returns an instance of NumberMonkey, we need to go link up all of the actual instances in left and right. We do that work here.

// In Day21

private fun parseInput(input: List<String>): Set<Monkey> {
    val monkeyCache: Map<String, Monkey> = input.map { Monkey(it) }.associateBy { it.name }
    monkeyCache.values.filterIsInstance<FormulaMonkey>().forEach { monkey ->
        monkey.left = monkeyCache.getValue(monkey.leftName)
        monkey.right = monkeyCache.getValue(monkey.rightName)
    }
    return monkeyCache.values.toSet()
}

Since we only need a Set<Monkey>, we can return the values of the temporary Map we have, and turn it into a set via toSet.

We’ll save these, and a reference to the root Monkey, since we’ll refer to it a couple of times.

class Day21(input: List<String>) {

    private val monkeys: Set<Monkey> = parseInput(input)
    private val root: Monkey = monkeys.first { it.name == "root" }
}

⭐ Day 21, Part 1

The puzzle text can be found here.

Because we put all of the logic into our Monkey clases, and did all of the parsing work, we have all the code we need to solve Part One, which JUST INVOLVES YELLING.

// InDay21

fun solvePart1(): Long =
    root.yell()

Star earned! Onward!

⭐ Day 21, Part 2

The puzzle text can be found here.

Before we start writing code, let’s figure out how we want to solve Part Two (always a good idea to think before coding, advice I don’t always follow).

Let’s start with the simplest setup. A root node with a single left node, a single right node. If left is 3 and right is 4, our root node value is 7. Now let’s pretend that left becomes the humn node, and we’re looking for it to equal the right node. How do we know what it needs to be?

     [left == right]
       /        \
      /          \
    (?)          (4)

We know the answer must be 4 or else the root node won’t equal out. Let’s do a more complicated example:

     [left == right]
       /        \
      /          \
    (-)          (+)
    / \          / \
   /   \        /   \
 (?)   (4)    (4)   (6)

So now what? Ultimately the right side value is 10, so the left side value also needs to be 10. We know the value of the ? node must be 14 because 14 - 4 == 10. When the root node calculates the right side, it knows it wants the left side to be 10 as well, so it passes 10 down to the (-) minus node. How does that turn into a 14? If we reverse the minus op computation to a plus, we can add the incoming 10 to the 4 and get 14 - the number we’re after!

It turns out, if we perform this same algorithm across all of the nodes in the tree, and have a new set of functions to reverse any computation that one of the FormulaMonkey instances can do, we’ll have our answer!

We’re going to add some functions to our Monkey instances in order to perform the calculations.

First up - we need to know the set of Monkey instances that make up the path from the root to the humn node. We don’t really care about the order, just which Set is involved (because there are no cycles).

// In Day 21

private interface Monkey {

    // ... existing functions and properties not shown

    fun findHumanPath(): Set<Monkey>
}

private class NumberMonkey {

    // ... existing functions and properties not shown

    override fun findHumanPath(): Set<Monkey> =
        if (name == "humn") setOf(this) else emptySet()
}

private class FormulaMonkey {

    // ... existing functions and properties not shown

    override fun findHumanPath(): Set<Monkey> {
        val leftPath = left.findHumanPath()
        val rightPath = right.findHumanPath()
        return if (leftPath.isNotEmpty()) leftPath + this
        else if (rightPath.isNotEmpty()) rightPath + this
        else emptySet()
    }
}

The general theory behind findHumanPath is this - for the NumberMonkey nodes, if you are the humn node, return yourself in a set as a Set<Monkey>, otherwise, return an emptySet. For the FormulaMonkey nodes, if the humn node is down the left side, we recursively call findHumanPath on the left side, and add ourself to the Set<Monkey> being constructed. We do identical work on the right side. If the humn node isn’t on either side, we return an emptySet.

Calling root.findHumanPath() will return us a Set<Monkey> that contains all of the Monkey instances from the root to the humn node.

Next, we’ll write a function to calculateHumanValue.

// In Day21

private interface Monkey {

    // ... existing functions and properties not shown

    fun calculateHumanValue(humanPath: Set<Monkey> = findHumanPath(), incoming: Long = 0L): Long
}

private class NumberMonkey {

    // ... existing functions and properties not shown

    override fun calculateHumanValue(humanPath: Set<Monkey>, incoming: Long): Long =
        if (name == "humn") incoming else number
}

The implementation for calculateHumanValue in NumberMonkey is straight forward - either it is the humn node, in which case we return the incoming value from the parent node (a FormulaMonkey) or we’re some other non-humn node and we return the number we would normally return in response to a yell.

Note that the default value for humanPath is the output of findHumanPath. This simplifies the work we do in FormulaMonkey later.

The implementation in FormulaMonkey is a bit more complicated:

// In Day 21

private class FormulaMonkey {

  // ... existing functions and properties not shown

  override fun calculateHumanValue(humanPath: Set<Monkey>, incoming: Long): Long =
      if (name == "root") {
          if (left in humanPath) left.calculateHumanValue(humanPath, right.yell())
          else right.calculateHumanValue(humanPath, left.yell())
      } else if (left in humanPath) {
          left.calculateHumanValue(humanPath, incoming leftAntiOp right.yell()) // Negate
      } else {
          right.calculateHumanValue(humanPath, incoming rightAntiOp left.yell()) // Negate
      }

  private infix fun Long.leftAntiOp(right: Long): Long =
      when (op) {
          '+' -> this - right
          '-' -> this + right
          '*' -> this / right
          else -> this * right
      }

  private infix fun Long.rightAntiOp(right: Long): Long =
      when (op) {
          '+' -> this - right
          '-' -> right - this
          '*' -> this / right
          else -> right / this
      }
}

When we call calculateHmanValue on the root node, we have to set up our process by finding theHumanPath so we know which side to call to get the value. When we identify the left side as the one with the humn, we tell it to ultimately return the value of the right node’s yell, and vise-versa for the right.

If we aren’t the root node, we do similar work by figuring whether the left or right side is the one with the humn node. If we find that the left side is the one with the humn, for example, we calculate the incoming value to that node by taking our incoming value and doing a negating operation with the right-side yell.

The real work is done in the leftAntiOp and rightAntiOp functions, which we’ll implement as infix functions on Long. It took me a while to figure this out and debug it, so I’m glad it finally works. :)

Once we’ve done all this, we can solve Part Two:

// In Day21

fun solvePart2(): Long =
    root.calculateHumanValue()

Star earned! See you tomorrow.

⭐ Day 21, Part 1

⭐ Day 21, Part 2

Further Reading