# Advent of Code 2020 - Day 11, in Kotlin - Seating System

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 11: 'Seating System'

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.
- If they are the same, this is the answer. Count up the number of occupied seats and return.
- 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!

#### Further Reading

- Index of All Solutions - All posts and solutions for 2020, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 11
- Advent of Code - Come join in and do these challenges yourself!