Advent of Code 2021 - Day 4

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

It's bingo time. The input to today's problem is one line with a sequence of numbers, the ones that will be called, and then several boards: each five lines of five numbers; boards are separated by blank lines. In fact, we won't make assumptions on the size (except expecting that the sizes are coherent).

We take the first line and map the int constructor to each number in there. Then, we build a list of boards: we start with an empty list, and an empty board. For each line, we interpret it as a list of ints, and add that as a row to the board. When we reach a blank line, the board is compete; we add it to the list of boards and start a new one. If at the end there is a non-empty board (it will happen if the file does not end with a blank line), we add that one, too.

Part 1

We will run the game by marking numbers as they are called on the boards. Once a board has a full row or column marked, it wins; the resulting score is the sum of unmarked numbers in the board, and that's the answer to our puzzle.

Rather than checking every row and column of every board after each number, we will use some data structures to make keeping track of things easier. We will use a dictionary to know where each number can be found, identified by a triplet of board, row, column. That's number_placements. Then we use a couple of arrays to count how many numbers are marked in each row and column of each board. The rows array is a list, and each item in it is a list for the corresponding board, with one element for each row, initialized to 0. The columns array is exactly the same.

We start calling numbers. For each, we add it to the marked set and check the number_placements to see where to mark it; then we go to the appropriate elements in the rows and columns array to increment the marked counters, and if one reaches 5 (the length of a row or column), we have the winner board.

We just take the board, as a set, so we can directly take out the marked numbers as set difference, and add up the remaining ones.

Part 2

Now we want to let the wookie giant squid win, so we will look at the last board to win. We will need to add a new set of remaining boards (identified by their indices), initialized with all of them. Once a board becomes a winner, we remove it from the remaining set, and add it to the winners set. We need the winners set, not just the remaining set, because when remaining gets to one element, that is the one we have to chose, but we still need to keep calling numbers until it marks a full row or column so we can calculate its score.

If we add the winning board to the winners set before removing it from the remaining set, and check that there is a single remaining element which is also included in winners at this point we identify this precise moment.

We can include all of this into the same loop of part 1 by using a to_win flag to chose which conditions to check.