Advent of Code 2017 - Day 9, in Kotlin • Todd Ginsberg

On Day 9, we will use regular expressions and recursion to solve our problems. Even though the challenge description is quite long, our code sure won’t be! If you’d rather jump straight to the code, it’s right here .

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a String called input.

⭐ Day 9, Part 1

The puzzle text can be found here.

Remember how I said above that we are going to use regular expressions? Let’s define some helper expressions, and do a first pass and parsing our input.

private val cancel = "!.".toRegex()
private val garbage = "<.*?>".toRegex()
private val nonGroup = "[^{}]".toRegex()

Instead of manually detecting !, we can use the cancel regular expression to filter that out. That one is defined as “find me a ! and any character after it”.

Because we don’t want to worry about the garbage (delimited by < and >), we can write something to find that as well. The garbage regular expression says “find me a <, followed by anything, and then a >. This garbage regular expression is a bit different though, it uses what’s called a reluctant qualifier to match characters in the middle. This just means that instead of trying to make the match as large as possible, the match will be as small as possible. We need a reluctant qualifier when parsing garbage because Otherwise, this: <abc>{}<def> will only match once (as the whole String), instead of twice.

And finally, we’ll define a regex called nonGroup which will eliminate any non-group ({ and }) characters because we don’t really care about them.

To properly use these, we’ll apply them in the order I described or things won’t be accurate. We apply these by calling the replace method on String, which will replace any match with the provided String. Since we don’t want to replace it with anything, we give it an empty String.

private val cleanInput = input.replace(cancel, "")

fun solvePart1(): Int =
    scoreGroups(cleanInput.replace(garbage, "").replace(nonGroup, "").toList())

Why not make cleanInput have no garbage or group brackets? Because I’ve read ahead, so let’s just go with it.

Now to define our recursive scoreGroups function. The input we are giving it at this point will have all the canceled tokens removed, all of the garbage removed, and all of the non group tokens removed. So we will end up with input that might look like this: {{}{}}, just curly brackets.

Let’s stop and think about what we need to do here. Every time we run into an open bracket ({), we’ve found a new group. Thanks to the regularity of our input, we don’t have to guard against out-of-order brackets or junk inputs. So when we start a group, we’ll figure out how “deep” we are, add that to our running score, and then start the process over with the remainder of the string. Similarly, if we run into a close bracket (}), we can decrease our depth by 1 and continue on. And of course, our terminal condition (which every recursive function needs) is the empty list, in which we just return the accumulated score. This is the same algorithm you would apply to traversing a tree if you think about it. Viewing the set of open and close brackets as a list of tree structures is what helped me come up with this solution.

private tailrec fun scoreGroups(stream: List<Char>, score: Int = 0, depth: Int = 1): Int =
    when {
        stream.isEmpty() -> score
        stream.first() == '}' -> scoreGroups(stream.drop(1), score, depth - 1)
        else -> scoreGroups(stream.drop(1), score + depth, depth + 1)
    }

See? A couple of lines of code solves all that cleanly and performs quickly. I marked this as tailrec but I didn’t need it for my input and could have left it off (the stack never got very deep).

Star earned, let’s see what’s in store for us in part two!

⭐ Day 9, Part 2

The puzzle text can be found here.

Oh! We already have everything we need to do this! Like before, we’ll start by removing canceled tokens. Because we have our garbage regular expression we can use it to solve this part as well. Instead of removing the garbage, we find it all and count up the cumulative length (minus 2 for each, for the ends).

fun solvePart2(): Int =
    garbage.findAll(cleanInput).sumBy { it.value.length - 2 }

That was easy, and it earned us a star!

I hope you’ve learned something and as always, feedback is welcome!

9 days and we’ve earned 18 stars with 2^5 left to go!

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading