Advent of Code 2020 - Day 7, in Kotlin - Handy Haversacks • Todd Ginsberg

Day 7 brings us our first real look at recursion! We’ll use recursion to solve both parts of today’s puzzle, and use some nice functions from the Kotlin standard library to make parsing our data easier.

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

Problem Input

Today’s parser is going to be a little bit more involved than we’ve had in 2020 so far. We’ll take our input in as a List<String> and turn it in to a Set<Bag>, where Bag is a data class that contains three facts: 1) the “parent” bag (the outer bag), 2) How many child bags it can have (the “cost”), and 3) The name of the child bag (the inner bag).

class Day07(input: List<String>) {

    private val relationships: Set<BagRule> = parseInput(input)

    private data class BagRule(val parent: String, val cost: Int, val child: String)

}

If we had a massive set of bags and relationships, we’d probably want to parse this into a graph (which I did originally but refactored to this representation). I’ve opted to model the data this way because I feel it is easier to understand, and it is less code.

To parse the List<String> into a Set<Bag>, we’re going to write a new function.

private fun parseInput(input: List<String>): Set<BagRule> =
    input.filterNot { it.contains("no other") }.flatMap { row ->
        val parts = row.replace(unusedText, "").split(whitespace)
        val parent = parts.take(2).joinToString(" ")
        parts.drop(2).windowed(3, 3, false).map { child ->
            BagRule(
                parent, 
                child.first().toInt(), 
                child.drop(1).joinToString(" ")
            )
        }
    }.toSet()

companion object {
    private val unusedText = """bags|bag|contain|,|\.""".toRegex()
    private val whitespace = """\s+""".toRegex()
}

I know that looks like a lot, so let’s go over it. First, we don’t really care about the input that describes the bags that don’t hold other bags. We simply won’t represent those kinds or relationships in our model, so we can filter them out. Rather than burden ourselves with a tricky Regular Expression with multiple nested capture groups, we’ll simplify our input by removing the parts that don’t describe a relationship.

That replace(unusedText, "") part, followed by split(whitespace) turns our input from this:

"light red bags contain 1 bright white bag, 2 muted yellow bags."

To this:

listOf(light, red, 1, bright, white, 2, muted, yellow)

If you look at it, the first two elements are the name of the parent bag. And then each successive three elements are the cost and the child bag name!

So we will take(2) from our parts and call that the parent name. Then, we look at the rest of the elements by dropping the 2 we just took, and using the windowed function to break the input up into List<String> with 3 elements each!

The windowed function is in the Kotlin standard library, and is used to generate sub-lists from a list. In this case we’re telling it we want some lists that are 3 elements long, to skip 3 elements of the input every time through (no overlap), and to not bother giving us partial lists because we might end up with empty strings at the end of our parsed input that we don’t care about.

Now that we have a list (child), we can turn that and the parent into a Bag. Collapse that List<Bag> into a Set<Bag> and we have our parsed input!

⭐ Day 7, Part 1

The puzzle text can be found here.

Because we did so much work setting up our data already, the solution to Part 1 is going to be a single recursive function that calculates the complete set of bags involved, given a single bag (the “shiny gold” bag). A recursive function is a function that calls itself. These are handy when you can break a problem down into smaller versions of a larger problem. Because we’re going to be looking through our relationship set for different bags, we can solve this recursively:

// In Day07

private fun findParents(bag: String = "shiny gold"): Set<String> =
    relationships
        .filter { it.child == bag }
        .flatMap { findParents(it.parent) }.toSet() + bag

We could also have solved this iteratively with a while loop or a queue or something like that, but I think the recursive version looks more elegant, and is easier to understand. So what does our function do? First, we tell it what bag we want to find, defaulting to the shiny gold bag. Then we look through the entire set of relationships for those that have the bag we are looking for as its child. Next, we recursively call findParents again for the parents of those bags we’ve picked out of the relationships set. We will get back a List<List<Bag>>, so we’ll have to flatMap our result so we get a single List<Bag>, and then call toSet() on that to turn it into a set. This action will collapse any duplicates into a single instance (in case we have two bags that are parents, such as in the example). Finally, we add the bag we were tasked with finding to the set and return.

Since the value returned has the bag we started with in it, and we were told to find how many bags that bag contains, we have to subtract 1 in order to account for that.

fun solvePart1(): Int =
    findParents().size - 1

Star earned, onward!

⭐ Day 7, Part 2

The puzzle text can be found here.

Part 2 is solved similarly to Part 1 because we’re going to write another recursive function. Our data is already in a good format, so we can dig right in:

// In Day07

private fun baggageCost(bag: String = "shiny gold"): Int =
    relationships
        .filter { it.parent == bag }
        .sumBy { it.cost * baggageCost(it.child) } + 1

First, we’re asked to find the cost of a single bag, defaulting again to the “shiny gold” bag. Next, we’ll do what we did before, find all of the relationships whose parent is the bag we are looking for. Once we have those, we can sum up the costs of their child bags according to the algorithm in the puzzle. The “cost” of the child bag multiplied by how many bags each child contains. We calculate that number by recursively calling baggageCost with the child bag, to find its total cost. Finally, we add 1 to the end to account for the bag we’re looking for. To picture why that 1 matters so much, think about the cost of a single bag with no children. The filter won’t find anything, so the sum will be zero, but the bag itself costs 1, so we have to add that. The numbers we’re adding need to come from somewhere, and that is our base case.

fun solvePart2(): Int =
    baggageCost() - 1

And like Part 1, we’ve accounted for the outermost bag and we’re told not to, so we have to subtract 1 to get the proper answer.

Star earned! See you tomorrow!

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading