Advent of Code 2020 - Day 19, in Kotlin - Monster Messages • Todd Ginsberg

I was very tempted to solve today’s puzzle entirely with regular expressions, and I started down that path before part 2 showed up. Instead of having wildly different solutions to each part of the puzzle, we have one solution that works for both.

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

Problem Input

Today we will take in our input as a List<String>. If we look at the rules in the input, there are only two types of actual rules: Either we are matching a character exactly (which I will call an “Atom”), or we need to refer to another rule to get our answer (which I will call a “RuleReference”). So lets go ahead and define an interface and two implementations for that:

// In Day19

interface Rule
class Atom(val symbol: Char) : Rule
class RuleReference(val id: Int) : Rule

As you can see, the Atom carries the symbol it matches, and the RuleReference carries the id of the rule it refers to. I didn’t make these data classes because we don’t need the extras that come with them, but it probably won’t hurt things to define them that way. Similarly, I didn’t feel that it was worth defining a sealed class because we only have two types and they are constrained to this problem.

When we parse our rules we want to capture the fact that some rules need to have an AND semantic (“All of these things must match in order”) and some rules need to have an OR semantic (“Either one of these two sets of rules must match”). To do that we will define each rule as a List of Lists of Rules (List<List<Rule>>) where the innermost List<Rule> represents a list of rules that all must match. And the outer List<List>> is the OR part - only one of these must match.

Ultimately, we will hold all of the rules in a MutableMap<Int, List<List<Rule>>> where the Int key is the rule id, and the value is the rule structure I just described. If you find this all unpalatable, you can either leave the types off for the most part, or define a typealias.

private fun parseRules(input: List<String>): MutableMap<Int, List<List<Rule>>> =
    input.takeWhile{ it.isNotBlank() }.map { line ->
        val (id, rhs) = line.split(": ")
        val sides = rhs.split(" | ")
        id.toInt() to sides.map { side ->
            side.split(' ').map { part ->
                if (part.startsWith('"')) Atom(part[1])
                else RuleReference(part.toInt())
            }
        }
    }.toMap().toMutableMap()

When we parse our rules, we go through the input until we hit a blank line that separates the rules from the messages. For each line we have, we split the line into two parts on the “: " in each line, giving us the rule id and the remaining right hand side of the rule (rhs). We then split the rhs on the " | " String, if there is one. Finally, we create a Pair where the first part is our id cast to an Int, and the value is a List<Rule>. To calculate that value, we split on space and map each part. If the part starts with a quote, we know this is an Atom, otherwise it has to be some kind of RuleReference.

Calling toMap() on our resulting List<Pair<...>> turns it into a Map, and calling toMutableMap() on that, makes it so we can change the rules later. We will need that in part 2.

The only data parsing left is to pick the messages out from the input by skipping until we find a blank line, dropping that, and taking the remainder of the input as-is.

So this is what Day19 ends up looking like:


class Day19(input: List<String>) {

    private val rules: MutableMap<Int, List<List<Rule>>> = parseRules(input)
    private val messages: List<String> = input.dropWhile { it.isNotBlank() }.drop(1)

}

⭐ Day 19, Part 1

The puzzle text can be found here.

Originally when I solved Part 1, I wrote something to string all of our RuleReference and Atom classes together into a big Regular Expression, and it worked fine. In some languages, that approach would work fine for Part 2 as well, but not in Kotlin (or Java). Therefore, in order to solve both parts of the puzzle with one algorithm, we’re going to have to write our own parser.

Because we want to match rules on specific messages (which are String instances), we will make an extension function on String, and read from the rules variable we have already declared.

Our new function will return a list of lengths of strings that ended up matching the rules, given a ruleId and a position along the message (defaulting to zero).

private fun String.ruleMatch(ruleId: Int, position: Int = 0): List<Int> =
    rules.getValue(ruleId).flatMap { listOfRules -> // OR Rule
        var positions = listOf(position)
        listOfRules.forEach { rule ->  // AND Rule
            positions = positions.mapNotNull { idx ->
                when {
                    rule is Atom && getOrNull(idx) == rule.symbol ->
                        listOf(idx + 1) // End condition
                    rule is RuleReference ->
                        ruleMatch(rule.id, idx)
                    else ->
                        null
                }
            }.flatten()
        }
        positions
    }

You should have seen this before I cleaned it up. :) Essentially, we are given a ruleId, so we pick that out of the rules map. What we get back is a list of possible rules, and one of them must match for a message to be valid. We set up a loop over this list of list of rules, and start evaluating them. Since this is a recursive algorithm, we ultimately need to answer the question: “Do these references ultimately track back to an Atom that matches at this exact spot”. To do that, we seed our positions with the position we are examining. This will be the basis for our checks, but we’ll add more to it for the AND rules. For every position, we test our current rule. If we are looking at an Atom AND the symbol matches the point in the message we are looking at, we consider that a match. This is the end condition for our recursive call, so we return list(idx+1) to our caller, meaning “there is a match, here is the next index”. If the rule we have is a RuleReference, we call ourselves with the new rule id, and the idx we are examining. Eventually that will lead to an Atom. Otherwise, we’re looking at an Atom that does not match the current position in the message, and we don’t want to continue recursing, so we return null back to our mapNotNull loop.

After we are done evaluating a single rule, we have a list of positions that we matched Atoms on. Because the next rule being evaluated is an AND (meaning: it evaluates the next position in the message for the next set of possible Atoms), we want to replace the positions with the ones we just found. This will set up the next rule with possible starting points to match.

When that loop ends, we know we have some positions that matched at least one of the possible sets of rules, and can return it to the caller.

We can evaluate all of our messages against the rules with this function:

private fun countRuleMatches(): Int =
    messages.count { message ->
        message.ruleMatch(0).any { it == message.length }
    }

Meaning: go through each message and count how many of them pass Rule 0. Our ruleMatch function returns a list of lengths that matched, so we consider a rule to match if and only if the message length and the rule match length are the same. Otherwise we have either not matched enough, or we have matched too much.

Calling this solves part 1!

fun solvePart1(): Int = countRuleMatches()

⭐ Day 19, Part 2

The puzzle text can be found here.

Because all of the code we wrote for Part 1 will solve Part 2, we only have to modify the input to add the new rules mentioned in the puzzle:

fun solvePart2(): Int {
    rules[8] = listOf(
        listOf(RuleReference(42)),
        listOf(RuleReference(42), RuleReference(8))
    )
    rules[11] = listOf(
        listOf(RuleReference(42), RuleReference(31)),
        listOf(RuleReference(42), RuleReference(11), RuleReference(31))
    )
    return countRuleMatches()
}

This block of code rewrites rules 8 and 11 to match the puzzle specifications. Running this will solve Part 2!

See you tomorrow!

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading