# Advent of Code 2021 - Day 4, in Kotlin - Giant Squid

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 4: 'Giant Squid'

Posted on

Let’s get ready to play bingo with a Giant Squid! I like bingo because it feels like you’re doing something but as this puzzle shows, it’s mostly deterministic. I say mostly because in real life if you aren’t paying attention you might miss marking a spot when you should. This is a good Saturday morning puzzle, and I had fun doing it.

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

Problem Input

One thing I love about Kotlin is that I can make complicated types easier to look at via `typealias`. Let’s define a `typealias` for our `BingoBoard` as our first order of business.

``````// In Day04.kt

typealias BingoBoard = List<List<Int>>
``````

Each row of a bingo board is represented by a `List<Int>`, and we’ll have a `List` of those. Note that we could have gone with `Array<IntArray>` as well, but I think lists work fine here as well. We aren’t doing anything other than reading from this data structure, so pick whichever one feels more natural to you.

Because we can’t win this version of bingo with a diagonal line, in theory we could have defined `BingoBoard` as `Set<List<Int>>` because the order of the rows does not matter. But I felt that `List<List<Int>>` just made more sense.

Now we can define our daily class, taking the `input` as a `List<String>`. We’ll also define a few properties that we’ll need along the way.

``````// In Day04.kt

class Day04(input: List<String>) {

private val draws: List<Int> = input.first().split(",").map { it.toInt() }
private val boards: Set<BingoBoard> = parseInput(input)

}
``````

We’ll set aside our `draws`, which is the list of numbers that will be drawn in order. To do that, we’ll parse the first line of input by splitting on the comma character and mapping each of the resulting `String` to an `Int`. Since we’ll be doing math with these values later, we might as well have them as `Int`s.

Next, we’ll parse the rest of our input into a `Set<BingoBoard>`s:

``````// In Day04

private fun parseInput(input: List<String>): Set<BingoBoard> =
input
.asSequence()
.drop(1)
.filter { it.isNotEmpty() }
.chunked(5)
.map { parseSingleBoard(it) }
.toSet()

private fun parseSingleBoard(input: List<String>): BingoBoard =
input.map { row ->
row.split(" ").filter { it.isNotEmpty() }.map { it.toInt() }
}
``````

We’ll convert our input to a `sequence` here because there are a lot of steps and that’s a lot of temporary lists to create and throw away. For a small application like this isn’t probably not a big deal, but it’s worth getting in the habit of considering when to convert to a `sequence`. We’ll `drop` the first row because it represents draws and not boards. Because the input has some empty lines, we’ll want to throw those away so we don’t have to deal with them. In order to get our boards into `List<String>` of length 5, we can use the `chunked` function out of the Kotlin standard library. The `chunked` function takes our input and breaks it into chunks of 5, which will represent a whole board. Once we have that, we can treat that as a single board and parse it, collapsing the whole group of the parsed boards into a `Set`.

To parse an individual board, we’ll need to go row-by-row and split the rows based on spaces. Because there is the possibility of having more than one space, we could have `split` based on a regular expression, but I found that confusing and just decided to `split` on space and then throw away anything that wasn’t a space. Once we have our values, we can convert them to `Int`s.

Now we have a daily class, with a typealias, the draws we will perform in order, and a set of boards.

Parsing done, onward!

#### ⭐ Day 4, Part 1

The puzzle text can be found here.

The approach we’ll take to solve part one is just like you would find if you were actually playing bingo. Keep drawing numbers in order until we find a single winning board.

Let’s start out with some extension functions to help us out. First, up, determining if a `BingoBoard` is a winner or not given the draws that have already happened (as a `Set<Int>`).

``````// In Day04

private fun BingoBoard.isWinner(draws: Set<Int>) =
this.any { row -> row.all { it in draws } } ||
(0..4).any { col -> this.all { row -> row[col] in draws } }
``````

Thankfully, we don’t have to count diagonals or this would be more complicated. To calculate we have a winning board, we first check to see if `any` row has `all` of its numbers in the `drawn` set. This means a complete row has been done. To check for a complete column, get the indexes of the rows (0 to 4) and check to see if `all` of the spots in that column are in the `drawn` set.

We’ll also define an extension function to sum up the number of unmarked spots on a given board:

``````// In Day04

private fun BingoBoard.sumUnmarked(draws: Set<Int>): Int =
this.sumOf { row ->
row.filterNot { it in draws }.sum()
}
``````

Like the previous function, this one takes a `Set<Int>` representing the draws that have already happened. We’ll go row-by-row and get the `sumOf` each individual row. The sum of an individual row can be calculated by filtering the drawn items that are not in the row, and taking the `sum` of them.

Now, we can solve part one of the puzzle:

``````// In Day04

fun solvePart1(): Int {
val drawn = draws.take(4).toMutableSet()
return draws.drop(4).firstNotNullOf { draw ->
drawn += draw
boards.firstOrNull { it.isWinner(drawn) }?.let { winner ->
draw * winner.sumUnmarked(drawn)
}
}
}
``````

We’ll set up a `Set<Int>` to represent the numbers that have been drawn already. Because we can’t win bingo with at least 5 draws, we’ll give ourselves a head start by marking the first four has having been drawn already. Then we’ll go through all of the draws remaining (taking care to `drop` the first 4) and find the first board that wins. Basically, for every draw we either find a single board that wins, or we find a null. Since we are using `firstNotNullOf`, our logic will stop running as soon as we find that winning board.

To find the winning board, we need to add the current `draw` to the set of `drawn` numbers. Then we’ll go through each board to see if one of them is a winner, again using `firstNotNullOf`. If one of them wins, we’ll calculate its score and return it as the first non-null value to both of our `firstNotNullOf` calls.

That number is our first winning board, and we can return it for a star!

Part one solved, onward!

#### ⭐ Day 4, Part 2

The puzzle text can be found here.

To solve part two we have a few options. We could go through the list of `BingoBoard`s draw-by-draw until we get down to one board and then calculate the answer. But what if we did the logic in part 1 in reverse? Instead of finding the first board to win, what if we found the first board to lose by going backwards through the draws?

The code for this is very similar to part one:

``````// In Day04

fun solvePart2(): Int {
val drawn = draws.toMutableSet()
return draws.reversed().firstNotNullOf { draw ->
drawn -= draw
boards.firstOrNull { !it.isWinner(drawn) }?.let { winner ->
draw * (winner.sumUnmarked(drawn) - draw)
}
}
}
``````

There are some differences to the code in part one. First, we’ll initiate our `drawn` set with all of the draws available. Next, we’ll go through the `draws` in reverse order by calling `reversed` on them. Like part one we’ll use `firstNotNullOf` to find the first board that matches the criteria. Of course, our criteria is backwards, so we’ll remove the `draw` from the set of `drawn` numbers, and instead of testing for `isWinner` we’ll test for the opposite. Once we have the board that lost first, we can calculate the answer.

There’s one thing to be aware of when doing that though. Because the `drawn` set we pass to `sumUnmarked` no longer contains the `draw` we just made, we’ll need to subtract it back out from the total (because `sumUnmarked` added it in).

Star earned!