Advent of Code 2020 - Day 18, in Kotlin - Operation Order • Todd Ginsberg

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>()
    var added = 0L
    while (equation.hasNext()) {
        val next = equation.nextChar()
        when {
            next == '(' -> added += solvePart2(equation)
            next == ')' -> break
            next == '*' -> {
                multiplyThese += added
                added = 0L
            }
            next.isDigit() -> added += next.asLong()
        }
    }
    return (multiplyThese + added).product()
}

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 = [2]

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

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

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

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.

Look for + instead of * (so: switch to a multiply-biased algorithm).

Instead of keeping an added var, keep a multiplied var defaulting to 1 (the multiplicative identity) instead of 0.

Instead of a multiplyThese list, have an addThese list.

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!

⭐ Day 18, Part 1

⭐ Day 18, Part 2

Further Reading