Advent of Code 2021 - Day 4, in Kotlin - Giant Squid • Todd Ginsberg

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 Ints.

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 Ints.

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 BingoBoards 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!

⭐ Day 4, Part 1

⭐ Day 4, Part 2

Further Reading