# Advent of Code 2020 - Day 18, in Kotlin - Operation Order

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 18: ''

Posted on

More fun with recursion! I was fortunate enough to have the day off work today, so I could really focus on today’s puzzle. I’m pretty happy with how this turned out.

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

Problem Input

We will take our input as a `List<String>` and keep it mostly as-is.

``````class Day18(input: List<String>) {

private val equations = input.map { it.replace(" ", "") }
}
``````

Because each number in our equation is a single digit, we can remove spaces from our `input` and make it so we can look at our `equation` character by character.

#### ⭐ Day 18, Part 1

The puzzle text can be found here.

Before we start, we need to write an extension function. Because we will be looking at our input character by character, we will run into a case where we need to convert a `Char` into a `Long`. Now, we might think that the perfectly reasonable looking `Char.toLong()` function in the Kotlin standard library would do what we want, and we would be wrong. The existing `toLong()` converts that `Char` to its underlying numerical value, which does not help us.

``````// In Extensions.kt

fun Char.asLong(): Long =
this.toString().toLong()
``````

I really would like to see something like `Char.asLong()` in the standard library. `String.toLong()` does a conversion (which we use here), I’m not sure why we can’t have a `Char` version.

Strategy

I know, I know, coming up with a plan to write code is not nearly as fun as actually writing it, but trust me, things work out better with a plan.

We’re going to implement a recursive function (a function that calls itself). We will use an `Iterator<Char>` to go through the `equation` one `Char` at a time. This will allow us to consume one character and pass along the remaining input in the `Iterator<Char>` to a recursive call without having to mark how far along the `equation` we are.

We will need to store some things: Up to two `numbers` we have run into and a single `op` (either `+` or `*`). Going through the `equation` character by character, we will run into one of four things. If we run into an operator, we store it in `op` for later. Since we’ll ever only have one of those to worry about at a time, we can just overwrite whatever is in there already. If we run into a digit, we will convert that `Char` to a `Long` and store it into our `numbers` list, for later.

Here’s where things get a bit complicated. If we run into an open parenthesis, we wan to recurse (call ourselves) with the remainder of the `equation`. This is why we use `Iterable<Char>`, because we can just pass it along as-is to the recursively-called function. In this case, that recursive function will eventually return a single answer to us, which we add to our `numbers` list for later.

If we run into a close parenthesis, we know we are at the end of some work, and can stop reading from the `equation`. To stop doing this, we `break` out of the `while` loop we are in. Normally I avoid using `break` because I personally find the sudden change in control flow to be confusing, but in this case it saves us from having to `return` in two places (which I generally don’t avoid unless I’m returning the same thing in two places in a single function, like here).

Now, the important part is that if we finish evaluating a character and realize that we have two values in the `numbers` list, we can do some work. Either we want to add them or multiply them, and store the result back into `numbers` as the single value.

If we get to the end of the `equation` naturally or have intentionally stopped reading input, we know that our answer is the single value left in the `numbers` list, so we return that.

Let’s see how this looks in code…

``````// In Day18

private fun solvePart1(equation: CharIterator): Long {
val numbers = mutableListOf<Long>()
var op = '+'
while (equation.hasNext()) {
when (val next = equation.nextChar()) {
'(' -> numbers += solvePart1(equation)
')' -> break
in setOf('+', '*') -> op = next
else -> numbers += next.asLong()
}
if (numbers.size == 2) {
val a = numbers.removeLast()
val b = numbers.removeLast()
numbers += if (op == '+') a + b else a * b
}
}
return numbers.first()
}
``````

One could probably make a case that we should use a `Stack<Long>` (or in Kotlin, an `ArrayDeque<Long>`) rather than a `MutableList<Long>` but since we will only ever have two elements in the list, I don’t mind.

If we call this `solvePart1` function with each of our `equations` as an `Interable<Char>` we will have answers to sum up.

``````// In Day18

fun solvePart1(): Long =
equations.sumOf { solvePart1(it.iterator()) }
``````
`sumOf` is a nice addition to the Kotlin standard library starting in 1.4. Thanks to @ephemient on the Kotlin Slack for the tip!

Star earned! Onward!

#### ⭐ Day 18, Part 2

The puzzle text can be found here.

Before we go into how we’ll solve Part 2, let’s write ourselves a useful extension function. Because we will be storing numbers in a list and multiplying them all, let’s add an extension to make that easier.

``````fun Iterable<Long>.product(): Long =
this.reduce { a, b -> a * b }
``````

We’ve done this a couple of times already during Advent of Code 2020, so hopefully we can use it again in the future. I’m reluctant to write an `Int` version before we need it, but it is mostly a copy and paste job if we decide to do that in the future.

Strategy Time!

Part 2 will end up looking pretty similar to Part 1, in that we will still have a recursive function that operates on an `Iterable<Char>` and hands off parenthetical work to a recursive call. The major difference is that we have different things to store. We will have list of numbers that we know we will have to multiply together at the end (`multiplyThese`), and another number to represent the running total of the additions we make `added`. We also don’t need to store the `op` in this case, because we know what work to do without having to remember it for later. For that reason, we can assume that this alrogithm is addition-biased (we assume we want to add rather than explicitly multiplying).

Finding an open parenthesis works the same way as part 1 - call a recursive version of ourselves with the remainder of the `equation`. When that returns, we will add it to our running sum. And running into a close parenthesis works the same as part 1, we stop reading input and get ready to return.

The major difference is what happens when we discover a multiply sign. At that point, we know that we need to take anything we’ve added up along the way, and store it in our `multiplyThese` list for later. We need to take care to clear the `added` total here, or we’ll just end up accumulating when we don’t want that.

Next, if we detect that we’re looking at a digit, we convert it to a `Long` and add it to our `added` running total.

Finally, if we hit the end of the `equation` naturally, or have broken out of the `while` loop, we need to return an answer. That answer will be everything in our `multiplyThese` list including our `added` value. We know that can’t be zero or none of the equations from part 1 will work out when the signs have a different order (that and my input had no zeros).

Let’s look at how that is implemented…

``````// In Day18

private fun solvePart2(equation: CharIterator): Long {
val multiplyThese = mutableListOf<Long>()
while (equation.hasNext()) {
val next = equation.nextChar()
when {
next == '(' -> added += solvePart2(equation)
next == ')' -> break
next == '*' -> {
}
}
}
}
``````

How does this work? Let’s reduce this to a simple example: `2 * 3 + 4`. In part 1, that answer should be `10`, but in part 2 it will be `14`. I picked an example without recursion to make life easier, but I encourage you to get out a piece of paper and work through your own example with parenthesis involved to see how that part works.

Step 1: Input is `2`, so we add that to `added`.
After this step: `added` = 2 and `multiplyThese` = []

Step 2: Input is a `*`, so we move `added` to `multiplyThese`.
After this step: `added = 0` and `multiplyThese` = 

Step 3: Input is a `3`, so we add that to `added`.
After this step: `added` = 3 and `multiplyThese` = .

Step 4: Input is a `+`, which we can ignore.
After this step: `added` = 3 and `multiplyThese` = .

Step 5: Input is a `4`, so we add that to `added`.
After this step: `added` = 7 and `multiplyThese` = .

Step 6: We’ve run out of input, so we add `added` to the end of the `multiplyThese` list, making `multiplyThese` = [2, 7].

Taking the product of the `multiplyList` (2 * 7) gives us the proper answer, 14.

If you want to use this approach to implement “normal math rules”, you can do that by flipping everything around.

1. Look for `+` instead of `*` (so: switch to a multiply-biased algorithm).
2. Instead of keeping an `added` var, keep a `multiplied` var defaulting to `1` (the multiplicative identity) instead of `0`.
3. Instead of a `multiplyThese` list, have an `addThese` list.
4. Switch any `product` to `sum` and any `+=` to `*=`

And just like Part 1, we can use our `sumToLongBy` function to solve each equation and sum the answers together to solve part 2:

``````// In Day18

fun solvePart2(): Long =
equations.sumOf { solvePart2(it.iterator()) }
``````

Star earned! See you tomorrow!