Advent of Code 2020 - Day 16, in Kotlin - Ticket Translation • Todd Ginsberg

Today we’ll use and learn about three very useful functions in the Kotlin standard library - any, all, and none. They’ll help us make evaluating the wide array of rules easy!

I want to mention that because we’re going to be using a lot of nested lambdas, I’m taking care to name each parameter today. So you probably won’t see it too frequently, and I hope that helps with clarity. Just because you can leave your lambda parameters as the default it, doesn’t mean that’s a great idea all the time. Naming things properly is a nice way to convey intent, and to help with your own understanding when you come back to a problem later on.

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

Problem Input

This is one of the harder inputs I can recall having to parse for Advent of Code. Rather than coming up with one big function that returns a custom class, we’ll write three functions, one to parse each section.

First, we need a regular expression to make the function that parses our rules easier to write.

companion object {
    private val ticketRuleRegex = """^([a-z ]+): (\d+)-(\d+) or (\d+)-(\d+)$""".toRegex()
}

This regular expression creates five groups - one for the rule name and four for the two pair of ranges.

We’ll use that regular expression to parse rules into a Map<String, List<IntRange>> where the key is the name of the rule and the value is a list of IntRange objects. Kotlin has first class support for ranges, and this will come in very handy.

private fun parseTicketRules(input: List<String>): Map<String,List<IntRange>> =
    input.takeWhile { it.isNotEmpty() }.map { line ->
        val (name, start1, end1, start2, end2) = ticketRuleRegex.matchEntire(line)!!.destructured
        name to listOf(
            start1.toInt() .. end1.toInt(),
            start2.toInt() .. end2.toInt()
        )
    }.toMap()

Because we get one input file containing three different sets of input, we need to be careful. In order to parse out our ticket rules, we can start reading the file, but need to stop when we hit the first empty line. To do this we can use takeWhile to read lines of input until we find an empty one. For each line we do find, we use the regular expression we just wrote to match the input, and then destructure it into its five component parts. Once we have that, we can create a Pair<String, List<IntRange>>, where the String is the rule name, and the other part is the list of ranges that satisfy this rule. We call toMap() on the result to finish parsing this section.

Next, we need to parse our own ticket:

private fun parseOurTicket(input: List<String>): List<Int> =
    input.dropWhile { it != "your ticket:" }.drop(1).first().split(",").map { it.toInt() }

Similar to above, we want to parse one single line but only after we’ve run into the line starting with “your ticket:”. We use dropWhile, which is the opposite of takeWhile - drop rows until this predicate holds, and then start taking records. We drop(1) because we don’t actually want the row that says “your ticket:”, and we take the first() row after that. Split it and map each field to an Int will give us the List<Int> representing our ticket.

Finally, we need to parse all of the nearby tickets:

private fun parseNearbyTickets(input: List<String>): List<List<Int>> =
    input.dropWhile { it != "nearby tickets:" }.drop(1).map { row ->
        row.split(",").map { it.toInt() }
    }

This uses the same concept that we just used to parse ourTicket, except instead of taking a single ticket, we parse all of them, returning a List<List<Int>>.

And now we can use these three functions to parse our input.

class Day16(input: List<String>) {

    private val ticketRules: Map<String,List<IntRange>> = parseTicketRules(input)
    private val allRuleRanges: List<IntRange> = ticketRules.values.flatten()
    private val ourTicket: List<Int> = parseOurTicket(input)
    private val nearbyTickets: List<List<Int>> = parseNearbyTickets(input)

}

We’ll also quickly make an allRuleRanges list, in order to make part 1 a bit cleaner. To do this we flatten all of the lists in the ticketRules values. The flatten function is used in this case to turn a List<List<IntRange>> into a single List<IntRange>.

⭐ Day 16, Part 1

The puzzle text can be found here.

Because we did so much work to parse our data, we can use it directly to solve part 1:


fun solvePart1(): Int =
    nearbyTickets.sumBy { ticket ->
        ticket.filter { field ->
            allRuleRanges.none { rule -> field in rule }
        }.sum()
    }

This is a nice example of sum() and sumBy(). First, we set up a loop over all of our nearbyTickets. When we call sumBy on that list, we essentially say “map these values to integers and sum them”. Inside that loop, we go through all of the fields in each ticket, and only keep the ones that do not map to any rules at all. These fields are the invalid ones. We call sum() on those invalid fields (if any, it will return zero on an empty list), and return them to the outer function for further summing.

This provides the answer to part 1.

Star Earned! Onward!

⭐ Day 16, Part 2

The puzzle text can be found here.

Let’s discuss the strategy we’ll use for Part 2 before writing any code (I know, that’s not fun, but it works out better that way).

Limit the tickets we have to look at to valid ones only.
For every field name, come up with a list of ticket column numbers that ALL pass one of the rules.
Reduce that list by:
1. Find fields that only have one possible matching column.
2. Remove that column from all other possbile matching sets.
3. Repeat this process until we don’t have any fields with multiple solutions.
Get the product of the “departure” fields on our ticket.

Let’s start by writing a function to make step 1 easier - something to tell us if a specific ticket (which is a List<Int> is valid or not):

private fun List<Int>.isValidTicket(): Boolean =
    this.all { field ->
        allRuleRanges.any { rule ->
            field in rule
        }
    }

We consider a ticket to be valid if and only if all of its fields pass any rule. We can test that a field (an Int) is one of the IntRange object by using the in operator - field in rule, where field is an Int and rule is an IntRange.

Let’s expand on that concept and write a function that uses our pre-parsed input to figure out if all of the valid tickets pass a specific rule (by name), in a specific column. So “Do all tickets pass the rule called ‘seat number’ in column 3?”.

private fun List<List<Int>>.columnPassesRule(column: Int, fieldName: String): Boolean =
    this.all { ticket ->
        ticketRules.getValue(fieldName).any { rule -> ticket[column] in rule }
    }

This should look familiar. We make sure all of our tickets (which are List<Int>) pass any range associated with a rule, by name, in the given column.

I’ll show you what the solution for Part 2 is before I explain it. Otherwise it will be too hard to visualize how things fit together.

fun solvePart2(): Long {
    val validTickets = nearbyTickets.filter { it.isValidTicket() }

    val possibleFieldRules: Map<String,MutableSet<Int>> = ticketRules.keys.map { rule ->
        rule to ourTicket.indices.filter { column ->
            validTickets.columnPassesRule(column, rule)
        }.toMutableSet()
    }.toMap()

    val foundRules = reduceRules(possibleFieldRules)

    return foundRules.entries
        .filter { it.key.startsWith("departure") }
        .map { ourTicket[it.value].toLong() }
        .reduce { a, b -> a * b }
}

Alright! Lots to go over. The first line uses our isValidTicket extension function to reduce the full list of tickets to just the validTickets.

Next, we’ll create a Map<String, MutableSet<Int>>. We’ll use this to keep track of which which columns (the values) are valid for each rule name (the key). We make the inner set a MutableSet to make the reduction phase we’re going to do next easier. To create this map, we start by looping over all of the ticketRules we have. From this we create a Pair<String, MutableSet<Int>> where the first element is the rule name and the second is the set of columns that all pass that rule. To calculate that set, we go through each possible ticket index (we base this off of ourTicket, because all the tickets have the same length). A column is valid if it passes our columnPassesRule function we just wrote.

Because at this point we have a List<Pair<...>> objects, we can turn that into a ma by calling toMap on that list. That’s a nice function from the Kotlin standard library.

Now we have all the possible rules, it’s time to reduce them to what the rules actually are. For now, we’ll just call this reduceRules function, and we’ll define it below.

Finally, we will take out the rules that start with “departure” from our foundRules map, look up the value held in the corresponding column in ourTicket and multiply all of those values together. It is super important to do a toLong conversion here. You don’t even want to know how long I spent wondering why this perfectly reasonable approach wasn’t yielding the correct answer because I had used Int here by default!

Let’s look at what reduceRules looks like now:

private fun reduceRules(possibleRules: Map<String,MutableSet<Int>>): Map<String,Int> {
    val foundRules = mutableMapOf<String,Int>()
    while(foundRules.size < possibleRules.size) {
        possibleRules.entries
            .filter { (_, possibleValues) -> possibleValues.size == 1 }
            .forEach { (rule, possibleValues) ->
                val columnNumber = possibleValues.first()
                foundRules[rule] = columnNumber
                possibleRules.values.forEach { it.remove(columnNumber) }
            }
    }
    return foundRules
}

Remember - the purpose of this function is to take the set of all possible rules and reduce it to the actual set of rules. We will do this by finding rules that only have one possible column that could satisfy it. We then take that column away from all other possibilities (because we’ve found the one rule that column completely satisfies). By doing this, we can loop through and find candidates (rules with one solution) that didn’t exist the last time around. Do this until we have all rules accounted for and our function has its answer. I suspect there’s probably a way to do this as a single expression, but I feel this is easier to follow.

First we create a MutableMap to put our results in. Next, we set up a while loop and keep looping until the foundRules matches the size of the possibleRules map (meaning we have a solution for each rule). Within that while loop we find all of the possibleRules that have one solution, and add that rule to our foundRules map AND remove it from every value in our possibleRules map. This will free us from having to consider that rule, and allow other rules to become obvious on the next time through the loop!

Running all that produces the answer to part 2 fairly quickly.

I hope you had fun today, I really enjoyed this problem. See you tomorrow!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading