Advent of Code 2020 - Day 11, in Kotlin - Seating System • Todd Ginsberg

Buckle up! We’re going to learn a few new Kotlin concepts today such as function references and type aliases! This problem was a bit involved, but I’m happy with the solution. I’m fortunate to have had today off of work, so I could focus on today’s puzzle!

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

Problem Input

Before we start, let’s talk about how we represent our data types. I want to represent the board today as an Array<CharArray>>. Because this is a bit tedious to look at and type, let’s take advantage of a Kotlin feature called type aliasing. Type aliasing lets us tell the compiler that want to refer to some type by another name. We can do this for imports as well as types we define ourselves.

So let’s create a couple of aliases to make our code look cleaner:

// In Day11.kt, outside our Day11 class:

typealias Seats = Array<CharArray>
typealias Seat = Pair<Int, Int>

So for today’s solution, anywhere we see Seats we really mean Array<CharArray>, and anywhere we see Seat we really mean Pair<Int,Int>. Neat, huh? Doing this will yield the same exact code and functionality, we just get a better view of the types. Nothing about the generated code is any different.

We will read our input in as a List<String> and convert it to an Array<CharArray> (aka Seats):

class Day11(input: List<String>) {

    private val seats: Seats = input.map { it.toCharArray() }.toTypedArray()

}

⭐ Day 11, Part 1

The puzzle text can be found here.

Alright! We can do this! Let’s talk about our algorithm first:

Given some Seats
Calculate what the next Seats will look like, according to the rules.
Compare the seats we started with in step 1 with the seats we generated in step 2.
1. If they are the same, this is the answer. Count up the number of occupied seats and return.
2. This is not our answer, go to step 1 and use the new seats we just generated to start with.

First, let’s get some extension functions and helper variables out of the way.

We’ll need to examine our neighboring seats, so let’s define a neighbors sequence, which produces offsets. So, -1, -1 is one seat to our left and one up. We’ll define this in our companion:

// In Day11

companion object {
    // @formatter:off
    private val neighbors = sequenceOf(
        -1 to -1, -1 to 0, -1 to 1,
         0 to -1,           0 to 1,
         1 to -1,  1 to 0,  1 to 1
    )
    // @formatter:on
}

I like to turn my IDE’s formatter off for this so I can keep the offsets arranged like a picture. Hopefully this helps you visualize what the offsets mean.

Next, we’ll need to determine if a given seat is valid. When looking at neighbors for a given spot, we don’t want to examine seats that don’t exist, right? We will do that by defining an operator extension function on Seats:

private operator fun Seats.contains(seat: Seat): Boolean =
    seat.first in this.indices && seat.second in this.first().indices

This allows us to say if( seat in seats ). It works by the fact that indices in both cases are IntRange objects, and we can see if our height and width fit in the arrays we use to build our board (Seats).

We will also need to apply our neighbor offsets to a given seat quite frequently, so let’s make that look cleaner by defining an operator on our Seat:

private operator fun Seat.plus(that: Seat): Seat =
    Seat(this.first + that.first, this.second + that.second)

This really just adds to Pair<Int,Int> together, and this is the second time we’ve written one of these. I probably should add this to a general extensions file the next time we need it!

And for the last of the extension functions, given some Seats, we need to know how many are occupied:

private fun Seats.occupied(): Int =
    this.sumBy { it.count { row -> row == '#' } }

This is a nice use of sumBy and count.

Alright. Now that we’ve got that out of the way, let’s figure out how many neighboring seats are occupied.

private fun countImmediateNeighbors(seats: Seats, seat: Seat): Int =
    neighbors
        .map { it + seat }
        .filter { it in seats }
        .count { seats[it.first][it.second] == '#' }

We start with our neighbors offset sequence, and for each one of them we apply it to the seat we are calculating neighbors for. We use filter to only keep the seats that are actually on the board (alternatively, we could have written this as .filterNot { it !in seats }, but I find that hard to reason about). Finally, we count up the number of those seats we’ve just generated that are occupied (#).

Now that we can count neighbors of a given seat, we can use that function to generate a whole new set of Seats. Now, for part 1, there’s nothing tricky about implementing this code. But I know what Part 2 has in store for us, so we’re going to write some code here that looks more complicated than it needs to. But it isn’t, because it will make part 2 a lot easier.

private fun Seats.next(tolerance: Int, countFunction: (Seats, Seat) -> Int): Seats =
    this.mapIndexed { x, row ->
        row.mapIndexed { y, spot ->
            val occupied = countFunction(this, Seat(x, y))
            when {
                spot == 'L' && occupied == 0 -> '#'
                spot == '#' && occupied >= tolerance -> 'L'
                else -> spot
            }
        }.toCharArray()
    }.toTypedArray()

Let’s go through this. We’re defining an extension function on Seats called next, which will apply the transform rules and return us a new Seats object. And the tricky part, this function takes two arguments:

The tolerance for neighbors (4, for part 1)
A reference to a function that itself takes two arguments: some Seats, and a single Seat, and that function returns an Int.

Why do we do that when we don’t have to? Because in Part 2 we change how neighbors are calculated. Yes, we could just write a next2() function that looks almost exactly like this function except for how the neighbors are calculated. But since Kotlin supports Higher-order functions, we’re going to take advantage of that. A Higher-order function is a function that either takes another function as an argument (like we see here), or returns a function. In our case, we can solve both Parts 1 and 2 with our next function by giving it a different implementation of countFunction! And what’s neat is that we just call countFunction directly, we treat it like any other function because functions in Kotlin are top level concerns.

To implement next, we loop through the rows and columns of the Seats the next function is called on. For each seat, we count how many neighbors it has (occupied), and apply the rules using a when expression. If the spot is empty and is an L, we occupy it by setting it to #. Likewise, if we find an occupied seat with too many neighbors, we empty it by setting it to L. Anything else does not change. We call toCharArray and toTypedArray in order to turn this into a Seats object (which is really an Array<CharArray>, remember?).

We’re almost done. One final function to write. Remember the algorithm we discussed above? We finally know enough to implement that:

private fun findStableMap(tolerance: Int, countFunction: (Seats, Seat) -> Int): Int =
    generateSequence(seats) { it.next(tolerance, countFunction) }
        .zipWithNext()
        .first { it.first.contentDeepEquals(it.second) }
        .first
        .occupied()

The findStableMap function also takes in a tolerance and a countFunction because it will eventually pass those to the next function we just got done writing. We set up a sequence by seeding generateSequence with the first set of seats (our input). Each time through, the sequence will call next(tolerance, countFunction) on the most recently generated set of Seats. Our good friend zipWithNext is here once again, to pair up successively generated Seats objects. We take the first Pair<Seats,Seats> where both the first and second set of Seats equal each other. We’re using contentDeepEquals to do that, which will compare all of the arrays in our Seats to one another. Because we have a Pair<Seats,Seats> at this point, we take the first one, and call our occupied extension function on it.

And now, FINALLY, we can solve part 1:

fun solvePart1(): Int =
    findStableMap(4, this::countImmediateNeighbors)

We call findStableMap with our tolerance of 4, and a method reference to our countImmediateNeighbors function. That this::<methodName> syntax tells Kotlin to pass that given function by reference. I wish I could have written countImmediateNeighbors as an extension function on Seats, but we can’t pass extension functions that are members of our class this way, and I didn’t feel the trade-off was worth it.

Executing this will generate our answer to Part 1!

Star earned, onward!

⭐ Day 11, Part 2

The puzzle text can be found here.

Because we did a lot of work in Part 1, this part should be a derivation of the work we’ve already done. Basically, the only difference is how we find the neighbors of a given seat.

Let’s get the tricky part out of the way first - a function to find that, given a seat, finds the closest neighboring seat along a vector (as opposed to an immediate neighbor, like in part 1).

private fun findSeatOnVector(seats: Seats, seat: Seat, vector: Seat): Char? =
    generateSequence(seat + vector) { it + vector }
        .map { if (it in seats) seats[it.first][it.second] else null }
        .first { it == null || it != '.' }

I know that is a lot of types, but we can do this. This function takes in our Seats, the seat we are looking at, and a vector, which is an offset like in part 1. We’ll start by generating a sequence of new hypothetical seats: apply the offset vector to the last seat we checked each time the sequence needs a new value. For each new seat it generates, we check that it is a valid seat, and if so, map to its value (either ., L, or #), otherwise we map to null to indicate that we have run off the board. This function finishes by returning either null or the first non-floor character it finds.

Now that we have a function that finds the closest seat along a vector, we can use it to calculate the number of neighbors for a given seat:

private fun countFarNeighbors(seats: Seats, seat: Seat): Int =
    neighbors
        .mapNotNull { findSeatOnVector(seats, seat, it) }
        .count { it == '#' }

This function takes our seats array and a seat we are interested in finding the neighbors for. To do this, we use our neighbors sequence to generate offsets from our current position. We take those offsets and call the findSeatOnVector function we just wrote. We return by counting up the number of neighboring seats that are occupied.

And if we pass that function, along with our new neighbor tolerance of 5 to our findStableMap function, we’ve solved part 2!

fun solvePart2(): Int =
    findStableMap(5, this::countFarNeighbors)

I really enjoyed solving both parts of the puzzle today, and I hope you did too and that you learned something.

See you tomorrow!

⭐ Day 11, Part 1

⭐ Day 11, Part 2

Further Reading