Advent of Code 2021: Day 4

04 Dec 2021 . category: . Comments

This marks the second year that I’ve done Advent of Code. Now and then, I’d like to write about my experience with a given day’s puzzle. Advent of Code is free, it’s fun, and you probably already know someone who’s doing it. Check it out!

Day 4 of Advent of Code asks you to find the winning-est Bingo board out of a set of 100. I’ll start by covering some of the tactics that helped me solve this problem, then describe the solution.

My Tactics

It’s Always a Hashmap.

This was a favorite phrase of one of my mentors. Hash tables are super duper useful for mapping instances of one data type (key) to another (value). While most of us have used strings as the key in a hash table, by definition, any hashable datatype can be a sufficient key. This includes ints!

When you build your bingo board, you’ll need to resolve a value (if it exists) into a coordinate pair on the board. You could scan the board, but wouldn’t it be nice to just…look it up? Having a hash table index values to coordinate pairs simplifies playing a round. Additionally, if the key isn’t found in the hash table, it means that it wasn’t on the gameboard, so you can move to the next round!

Model the Right Thing.

This problem is begging you to work in a two dimensional array. The input looks like a two dimensional array. And, indeed, you could implement an algorithm that updates entries in a two dimensional array as you go. However, the win condition is very narrow: a board wins when all 5 spaces in a row or column are filled.

As such, if you keep count of how many spaces are filled in each row/column, you can check the most recently played row/column counters and signify a win if one of them shows 5. This ends up being way nicer than traversing a two dimensional array each time you play a number, and it’s faster, too!

This seems to be a common refrain in Advent of Code problems: the computer does not need to see the problem the way you do. Algorithms that model the problem in terms of the solution are likely to be simpler with fewer corner cases.

Amortize the Work.

One of the annoying bits about the problem is that you’re asked to compute the sum of the unmarked values as one of the products to the winning score. You could potentially keep track of the unmarked numbers and add them together at the end, but there’s nothing stopping you from keeping track of the sum from round to round!

If you tally up the sum of all values on the game board when you initialize the game and subtract numbers from the sum as you play them, you’ll have a running score that becomes simple to tabulate when you find the win condition.

My Solution

My approach for Part 1 and Part 2 was to implement a greedy algorithm that played each board sequentially. I was tempted to play the boards simultaneously the way that the example did, but there were 100 called numbers and 100 boards to play, making this a tiny problem. If, say, there were 20,000 boards or numbers, I might have needed to get creative.

The Bingo Board

Setting up the bingo board, we initialize our counters, our cumulative sum, and our index mapping values to coordinates.

type indexPair struct {
	I, J int
}

type bingoBoard struct {
	lookup    map[int]indexPair
	rowCounts []int
	colCounts []int
	sum       int
}

func newBingoBoard(input []string) *bingoBoard {
	b := &bingoBoard{
		lookup:    make(map[int]indexPair),
		rowCounts: make([]int, 5),
		colCounts: make([]int, 5),
	}

	for i, line := range input {
		for j, val := range strings.Fields(line) {
			parsed, _ := strconv.Atoi(val)
			idx := indexPair{i, j}
			b.lookup[parsed] = idx
			b.sum += parsed
		}
	}

	return b
}

I defined a type indexPair that holds row and columm coordinates in I and J, respectively. The strings.Fields() function makes it super easy to extract the strings in a given row, and strconv.Atoi() lets me parse them. Now that I’ve set up the board, playing a game is as follows:

func (b *bingoBoard) playGame(rounds []int) (int, int) {
	for round, called := range rounds {
		idx, ok := b.lookup[called]
		if !ok {
			continue
		}

		b.sum -= called
		b.rowCounts[idx.I]++
		b.colCounts[idx.J]++

		if b.rowCounts[idx.I] == 5 || b.colCounts[idx.J] == 5 {
			return round, b.sum * called
		}
	}

	return len(rounds) + 1, -1
}

For each called number, I will:

1. Check if the number is in the board and skip the number if it isn’t.
2. Update my cumulative sum.
3. Update the row/col counters.
4. Check for a win condition and return values if I get there!

Note that the function returns two values: the index in roundsand the winning score. The tail return looks funny, but since every board is a winner eventually (something my teachers told me often…) the tail return line of code never gets hit in practice. Returning both values helps my greedy algorithm, which we’ll see in a minute.

The Greedy Algorithm

Now that I have a nice, encapsulated bingo board, I can play em all! To make my life easier, I read the file as “sections” (an array of arrays of strings).

func part1(input [][]string) int {
	parts := strings.Split(input[0][0], ",")
	rounds := make([]int, len(parts))
	for i, part := range parts {
		rounds[i], _ = strconv.Atoi(part)
	}

	boards := input[1:]

	minRounds := len(rounds) + 1
	winningScore := -1

	for _, board := range boards {
		b := newBingoBoard(board)
		count, score := b.playGame(rounds)
		if count < minRounds {
			winningScore = score
			minRounds = count
		}
	}

	return winningScore
}

Here we can see the greedy algorithm in action. It keeps track of the winningest score and the number of rounds it took. When it comes across a board that wins in fewer rounds, it updates its round count and score. Once we’ve played all the boards, we’ve found the definitive winningest score and we can return it!

You can check out the full source code here.

Vishal Kotcherlakota is a reformed sysadmin, who writes code and will talk incessantly about DevOps to anyone who will listen. All views expressed here are his and not those of his employers.