Advent of Code 2021 - Day 3

Deep under the water, we find ourselves hearing creaking noises. Our submarine handily gives us a diagnostics report. Sadly, as is oft too common in AoC, the report format is complete garbage, to put it mildly.

Our puzzle input comes in the form of binary numbers. The task is to compute a gamma rate and an epsilon rate based on a simple algorithm. The example report given to us looks like this:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

Instead of taking these binary numbers as-is, we need to construct new ones to get the gamma and epsilon rates. We do this by looking at the binary numbers bit by bit. The gamma rate results from taking the most common bit amongst all binary numbers for each position.

A short example can illustrate this much better than words, so let's take the first three binary numbers from above:

00100
11110
10110
=====
10110

By looking at the first bit of each number, we can see that there are two 1s and only one 0, so the first digit of the gamma rate is 1. We continue this for each digit until we get a gamma rate of 10110 or 22 in decimal.

The epsilon rate is obtained the same way, but we're taking the least common bit this time. A careful observer will notice that this can also be obtained by simply negating each bit of the gamma rate.

Part 1

Naïvely, we can skip converting the input to their actual binary representation and work on them as ASCII characters. We can read the file into a []string. For each position in the bitstring, we use a counter that increases for every 1 and decreases for every 0.

var cntr []int = make([]int, len(lines[0]))
for _, line := range lines {
	for idx, ch := range line {
		switch ch {
			case '1':
				cntr[idx] += 1
			case '0':
				cntr[idx] -= 1
		}
	}
}

In the next step, we can use this to construct the gamma and epsilon values using binary shifts:

var gamma, epsilon uint64
for idx, val := range cntr {
	if val > 0 {
		gamma = gamma | 1 << (len(cntr) - 1 - idx)
	} else {
		epsilon = epsilon | 1 << (len(cntr) - 1 - idx)
	}
}

We can then compute the puzzle answer as the product of gamma and epsilon.

Part 2

Part two is a bit of a tricky variation on part one. Instead of finding the most common bit value at each position, we use the most common bit as a cumulative filter for the whole list of numbers.

Initially, I solved this by building a binary tree where the edges represented a zero or a one. By traversing the tree and walking in the direction of the subtree with the most child nodes, it was easy to find the solution.

A binary isn't very efficient for this type of puzzle - after all, we're just dealing with binary numbers, and if there's something computers are fast at, it's binary.

A much faster solution comes from my friend @javorszky, who solved this part recursively. His algorithm makes use of bitmasks. To explain this, let's take the first four numbers:

00100
11110
10110
10111

For each position, we construct a bitmask. For the first position, this is simply 1<<5 or 10000. Any number bigger or equal to the bitmask has a one in that position; any number smaller has a zero. We continue this until we've filtered all the sublists down into a single element.

func filterNumbers(list []uint, pos int, larger bool) uint {
	if len(list) == 1 {
		return list[0]
	}
	mask := uint(1 << pos)
	ones := []uint{}
	zeros := []uint{}

	for _, item := range list {
		if item&mask >= mask {
			ones = append(ones, item)
		} else {
			zeros = append(zeros, item)
		}
	}

	if (len(ones) >= len(zeros) && larger) || (len(ones) < len(zeros) && !larger) {
		return filterNumbers(ones, pos-1, larger)
	}
	return filterNumbers(zeros, pos-1, larger)
}

Wrapping up

This was an interesting challenge that offered many solutions. We're not yet in the realm of puzzles that need heavily optimized algorithms, so it's great to play around a little. Implementing a binary tree from scratch isn't something I get to do very often. I'm definitely looking forward to more challenging puzzles going forward, but this was another well-crafted puzzle.