Advent of Code 2022 - Day 11, in Kotlin - Monkey in the Middle • Todd Ginsberg

Aha! The old “do something simple 20 times and now spend the rest of your life waiting for it to happen 10,000 times” trick that Advent of Code is notorious for! This was an interesting problem and I count myself lucky that I was able to get Part Two figured out fairly quickly (quickly for me anyway, I’m not the strongest mathematician doing these puzzles). I hope this write-up is clear and describes both the solution and reasoning for it.

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

Puzzle Input

We’ll take our input today as a List<String> and further parse it from there. The first order of business is to create an inner called Monkey to store all of the data about a single monkey, and to eventually inspect all of the items once per turn. This clearly isn’t reusable in any context (watch me be wrong about this) so we’ll make it an inner class of our Day11 class.

Going through the input file, we need:

A MutableList<Long> to represent all of the items each monkey is playing with.
An operation, which we will model as a function reference. This takes and returns a Long and models the mathematical operation done to each item.
A test, which we will also store as a Long. This is the number the result of the operation must be a multiple of.
And the ids of the two monkeys that get the results of the test as trueMonkey and falseMonkey.

We will also declare a Long property to represent the number of interactions each monkey as done. We’ll make that a var so we can change it, and not take it in as part of the constructor because its value is always 0.

// In Day11

private class Monkey(
    val items: MutableList<Long>,
    val operation: (Long) -> Long,
    val test: Long,
    val trueMonkey: Int,
    val falseMonkey: Int
) {

    var interactions: Long = 0

    companion object {
        fun of(input: List<String>): Monkey {
            val items = input[1].substringAfter(": ").split(", ").map { it.toLong() }.toMutableList()
            val operationValue = input[2].substringAfterLast(" ")
            val operation: (Long) -> Long = when {
                operationValue == "old" -> ({ it * it })
                '*' in input[2] -> ({ it * operationValue.toLong() })
                else -> ({ it + operationValue.toLong() })
            }
            val test = input[3].substringAfterLast(" ").toLong()
            val trueMonkey = input[4].substringAfterLast(" ").toInt()
            val falseMonkey = input[5].substringAfterLast(" ").toInt()
            return Monkey(
                items,
                operation,
                test,
                trueMonkey,
                falseMonkey
            )
        }
    }
}

When turning some regular input into a class, one pattern I like to follow is to declare a function called of in the companion object of my class. That way, in this case, we can say Monkey.of(someInputRows) and get a Monkey back. I just think calling that function looks nice and clean.

The implementation, however, has a lot going on, so I’ll go through it one section at a time. Rather than use regular expressions to parse each line of input, I’ve stuck with the substring functions. I’m not a huge fan of using regular expressions when input is in a format that doesn’t strictly require them.

The first thing to note is that we skip over the first line of input (input[0]) which contains the id of the Monkey. Since the monkeys are in order in the input file, and we store them all in a list, we don’t need them to know their own identity so we can skip that part. So the first real work in here is to parse out the item numbers. We can do this by getting a substring after “: " (note the space) and then splitting on “, " (again, note the space). We map each resulting String to a Long and then convert the resulting List<Int> to a MutableList<Int> via toMutableList().

We look at the third row of input (input[2]) and parse out the operationValue. This is stored as a String and will either be a number or the word “old”. With that, we create our operation function by examining the operationValue, or the presence of the multiply operator in the input[2] row. Anything else is addition. In each case, we return a function that performs the intended operation, converting operationValue to Long where necessary. We’ll call these functions later as part of our solution.

The test, trueMonkey and falseMonkey values are all parsed out of their respective rows using substringAfterLast and converted from String to their appropriate types.

Finally, we use all of this to return a new instance of Monkey.

I know that was a lot of work, and I wouldn’t blame you for just hard coding this. In my input, there are only eight monkeys.

Once we’ve written all that, we can create Monkey instances by calling Monkey.of() with a List<String> containing the data needed. One nice way to do this is to take our input and chunk it into groups of 7 lines, which represents all of the data for one Monkey (and a blank line at the end we can ignore). Calling Monkey.of() with the chunk of lines gives us a single Monkey, so we’ll map our input and get a List<Monkey>.

class Day11(input: List<String>) {

    private val monkeys: List<Monkey> = input.chunked(7).map { Monkey.of(it) }
}

⭐ Day 11, Part 1

The puzzle text can be found here.

The first order of business in Part One is to implement a function in our Monkey class to execute one round of work for one single Monkey. In order to pass items from the Monkey we call this function on to other Monkeys, we take in the full List<Monkey> we just finished parsing. We also take in a function called changeToWorryLevel which takes a Long and returns a Long. Why? Because in Part Two we change the calculation from dividing by 3 to… something else.

// In Day11.Monkey

fun inspectItems(monkeys: List<Monkey>, changeToWorryLevel: (Long) -> Long) {
    items.forEach { item ->
        val worry = changeToWorryLevel(operation(item))
        val target = if (worry % test == 0L) trueMonkey else falseMonkey
        monkeys[target].items.add(worry)
    }
    interactions += items.size
    items.clear()
}

The inspectItems function loops through all of the items and calls our operation function on a given item. This value is run through the changeToWorryLevel function (again, in Part One, this will be a divide by 3). This gives us the new worry level. We see if worry is equally divisible by test by using the modulo ("%") operator. If the value returned is 0, then worry is evenly divided by test and the trueMonkey gets the worry. Otherwise the falseMonkey does. We’ll look up the target monkey and add the value directly to the end of their items list. Normally, I’d probably encapsulate that call a bit better, but this is a puzzle solution we’ll run once, and not a library, we can leave it this way.

After all of the items have been sent to other monkeys, we need to count how many we just dealt with and add it to our interactions counter. It is important to remember to clear out the items list as we’ve handed these off to other monkeys and we don’t have to deal with them any longer.

Now that we can have a single monkey inspectItems, we need to implement the function rounds to make all of the monkeys do this some numRounds number of times. We also need to remember to take in our changeToWorryLevel function to pass along.

// In Day11

private fun rounds(numRounds: Int, changeToWorryLevel: (Long) -> Long) {
    repeat(numRounds) {
        monkeys.forEach { it.inspectItems(monkeys, changeToWorryLevel) }
    }
}

This function works by using Kotlin’s repeat which executes the given lambda the given number of times (numRounds in our case).

In order to fully calculate our answer we’ll need to know the total amount of Monkey Business being done. So we’ll implement business() as an extension function on List<Monkey>. This function sorts all of the Monkey objects by the total number of interactions they’ve had from highest to lowest, and then multiples the highest two numbers together.

// In Day11

private fun List<Monkey>.business(): Long =
    sortedByDescending { it.interactions }.let { it[0].interactions * it[1].interactions }

All that’s left is string all this together. We call our rounds function, letting it know we’d like 20 rounds to be played, and passing in a lambda for how to modify the worry level (divide it by 3). Once the rounds have played, we can calculate and return the Monkey business level for our answer.

// In Day11

fun solvePart1(): Long {
    rounds(20) { it / 3 }
    return monkeys.business()
}

Star earned! Onward!

⭐ Day 11, Part 2

The puzzle text can be found here.

If we remove the worry-level division and run what we had in Part One 10,000 times I’m sure of two things - the calculations would overflow a Long forcing us to use BigInteger, and doing that would cause the to take a really long time to finish. How long? I have no idea, I didn’t try it. But drawing from my experience with Advent of Code puzzles, I can spot a futile effort when I see one.

So let’s think about a way we can get worry to stop overflowing our Long values, while still being able to be used in the test calculation.

Let’s suppose for some Monkey, our test is 2. And let’s pretend that the worry level goes up by 1 each time.

This means we get calculations like this, as worry increases:

Worry = 0, Test = 2 --> 0 % 2 == 0
Worry = 1, Test = 2 --> 1 % 2 == 1
Worry = 2, Test = 2 --> 2 % 2 == 0
Worry = 3, Test = 2 --> 3 % 2 == 1

That’s interesting! The fact that we are doing a modulo with test means that no matter how high the worry gets, our test will be either 0 or 1. If worry is 4, we get 0, and if worry is 871298713986045183719343, we get 1. This is the key to keeping our worry low - taking the modulo of worry by… something. What though?

Let’s expand our example form before to have two test values (adding another Monkey). This time, its value will be 3:

Worry = 0, Test = 2 --> 0 % 2 == 0 | Test = 3 --> 0 % 3 == 0
Worry = 1, Test = 2 --> 1 % 2 == 1 | Test = 3 --> 1 % 3 == 1
Worry = 2, Test = 2 --> 2 % 2 == 0 | Test = 3 --> 2 % 3 == 2
Worry = 3, Test = 2 --> 3 % 2 == 1 | Test = 3 --> 3 % 3 == 0
Worry = 4, Test = 2 --> 4 % 2 == 0 | Test = 3 --> 4 % 3 == 1
Worry = 5, Test = 2 --> 5 % 2 == 1 | Test = 3 --> 5 % 3 == 2
Worry = 6, Test = 2 --> 6 % 2 == 0 | Test = 3 --> 6 % 3 == 0   <===== LOOP!

Another interesting finding! Now the “period” of the calculation is 6. Meaning, every time the worry value increases by 6, the first test calculation using 2 loops back to 0, and the second test calculation using 3 loops back to 0. It is not entirely coincidental that the product of our two test values (2 and 3) is 6.

What does this mean? It means we can reduce the worry by taking its modulo of the product of all the test values and doing so will cause the tests to return the correct result and route the item to the correct monkey. This is what stops us from overflowing a Long - the worry will be reduced and we’ll never overflow it.

With that knowledge, solving Part Two is almost the same as solving Part One except to calculate the product of all the test values (which we’ll store in testProduct). We can calculate this by doing a map and reduce over the monkeys list, and multiplying the test values.

Now you see why we pass in a lambda for the changeToWorryLevel calculation. In our case for Part Two, for each item we take the modulo testProduct of it (as described above).

// Day11

fun solvePart2(): Long {
    val testProduct: Long = monkeys.map { it.test }.reduce(Long::times)
    rounds(10_000) { it % testProduct }
    return monkeys.business()
}

Star earned! See you tomorrow.

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading