# Advent of Code 2022 - Day 11, in Kotlin - Monkey in the Middle

Kotlin solutions to parts 1 and 2 of Advent of Code 2022, Day 11: 'Monkey in the Middle'

Posted on

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.substringAfter(": ").split(", ").map { it.toLong() }.toMutableList()
val operationValue = input.substringAfterLast(" ")
val operation: (Long) -> Long = when {
operationValue == "old" -> ({ it * it })
'*' in input -> ({ it * operationValue.toLong() })
else -> ({ it + operationValue.toLong() })
}
val test = input.substringAfterLast(" ").toLong()
val trueMonkey = input.substringAfterLast(" ").toInt()
val falseMonkey = input.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`) 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`) 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` 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 `Monkey`s, 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
}
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

sortedByDescending { it.interactions }.let { it.interactions * it.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 }
}
``````

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 }