Skip to Content

Advent of Code 2017 - Day 9, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 9: 'Stream Processing'

Posted on

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

OK, get ready.

A large stream blocks your path. According to the locals, it’s not safe to cross the stream at the moment because it’s full of garbage. You look down at the stream; rather than water, you discover that it’s a stream of characters.

You sit for a while and record part of the stream (your puzzle input). The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas: either another group or garbage. Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. Your puzzle input represents a single, large group which itself contains many smaller ones.

Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.

In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

You don’t see any characters that deviate from these rules. Outside garbage, you only find well-formed groups, and garbage always terminates according to the rules above.

Here are some self-contained pieces of garbage:

<>, empty garbage.
<random characters>, garbage containing random characters.
<<<<>, because the extra < are ignored.
<{!>}>, because the first > is canceled.
<!!>, because the second ! is canceled, allowing the > to terminate the garbage.
<!!!>>, because the second ! and the first > are canceled.
<{o"i!a,<{i<a>, which ends at the first >.

Here are some examples of whole streams and the number of groups they contain:

{}, 1 group.
{{{}}}, 3 groups.
{{},{}}, also 3 groups.
{{{},{},{{}}}}, 6 groups.
{<{},{},{{}}>}, 1 group (which itself contains garbage).
{<a>,<a>,<a>,<a>}, 1 group.
{{&lt;a>},{&lt;a>},{&lt;a>},{&lt;a>}}, 5 groups.
{{&lt;!>},{<!>},{<!>},{<a>}}, 2 groups (since all but the last > are canceled).

Your goal is to find the total score for all groups in your input. Each group is assigned a score which is one more than the score of the group that immediately contains it. (The outermost group gets a score of 1.)

{}, score of 1.
{{{}}}, score of 1 + 2 + 3 = 6.
{{},{}}, score of 1 + 2 + 2 = 5.
{{{},{},{{}}}}, score of 1 + 2 + 3 + 3 + 3 + 4 = 16.
{<a>,<a>,<a>,<a>}, score of 1.
{{&lt;ab>},{&lt;ab>},{&lt;ab>},{&lt;ab>}}, score of 1 + 2 + 2 + 2 + 2 = 9.
{{&lt;!!>},{&lt;!!>},{&lt;!!>},{&lt;!!>}}, score of 1 + 2 + 2 + 2 + 2 = 9.
{{&lt;a!>},{&lt;a!>},{&lt;a!>},{&lt;ab>}}, score of 1 + 2 = 3.

What is the total score for all groups in your input?

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

Now, you’re ready to remove the garbage.

To prove you’ve removed it, you need to count all of the characters within the garbage. The leading and trailing < and > don’t count, nor do any canceled characters or the ! doing the canceling.

<>, 0 characters.
<random characters>, 17 characters.
<<<<>, 3 characters.
<{!>}>, 2 characters.
<!!>, 0 characters.
<!!!>>, 0 characters.
<{o"i!a,<{i<a>, 10 characters.

How many non-canceled characters are within the garbage in your puzzle input?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 9.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Take Me To The River, by Talking Heads.