Advent of Code 2021: Day 6

06 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 6 of Advent of Code asks you to model a lanternfish population growing at an alarming rate. It was also a great example of how the two-part formula for these problems can trigger refactors and rewrites. Let’s dive in.

Part 1: Hey, this is Easy!

I started by literally implementing this statement in the problem:

Each day, a 0 becomes a 6 and adds a new 8 to the end of the list, while each other number decreases by 1 if it was present at the start of the day.

Here’s what that algorithm looks like in Go.

func part1(fishes []int) int {
	for day := 0; day < 80; day++ {
		newFish := 0
		for i, fish := range fishes {
			if fish == 0 {
				fishes[i] = 6
				newFish++
				continue
			}
			fishes[i]--
		}
		for i := 0; i < newFish; i++ {
			fishes = append(fishes, 8)
		}
	}
	return len(fishes)
}

It passes the example in the problem, it gives me the first gold star. Woo!

Part 2: I’ve Been a Fool!

Part 2 is a very simple question:

After 256 days in the example above, there would be a total of 26984457539 lanternfish! How many lanternfish would there be after 256 days?

Ohhh dear. Something tells me that a slice with 26 billion entries is going to be a problem. I try increasing the number of days to 256, and my test case times out after 30 seconds! As the Advent of Code about page says, “every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.” Time for a rethink.

It’s clear that modeling each fish as its own timer isn’t sustainable. But do I need to know about each fish individually, or do I need to know how may fish are at a specific day in their lifecycle? Seems like it’s time for a new approach.

The Counting Sort

When you’ve got a large set of data within a bounded range, you’ll be glad you heard of the counting sort. The counting sort works by keeping track of how many instances of a specific value are in a dataset. As an example:

data: 1,1,5,2,1,1,5,5,3,1,1,1,1,1,1,3,4,5,2,1,2,1
sort: [0, 12, 3, 2, 1, 4]

In this example, each value in sort represents the number of times its respective instance appears in data. Because the value 1 appears 12 times in data, sort[1] = 12.

Counting sorts are super useful, but they only work if all your data is zero or positive integers, and the upper bound for your data set is something finite and reasonable for a datastructure.

You Spin Me Right Round

I suspected that I could model the lanternfish in a more sustainable way by building a counting sort and somehow transforming it for each day of the simulation. To get a sense for the data, I generated counting sorts for the first 18 days of the example.

 0 [0 1 1 2 1 0 0 0 0]
 1 [1 1 2 1 0 0 0 0 0]
 2 [1 2 1 0 0 0 1 0 1]
 3 [2 1 0 0 0 1 1 1 1]
 4 [1 0 0 0 1 1 3 1 2]
 5 [0 0 0 1 1 3 2 2 1]
 6 [0 0 1 1 3 2 2 1 0]
 7 [0 1 1 3 2 2 1 0 0]
 8 [1 1 3 2 2 1 0 0 0]
 9 [1 3 2 2 1 0 1 0 1]
10 [3 2 2 1 0 1 1 1 1]
11 [2 2 1 0 1 1 4 1 3]
12 [2 1 0 1 1 4 3 3 2]
13 [1 0 1 1 4 3 5 2 2]
14 [0 1 1 4 3 5 3 2 1]
15 [1 1 4 3 5 3 2 1 0]
16 [1 4 3 5 3 2 2 0 1]
17 [4 3 5 3 2 2 1 1 1]
18 [3 5 3 2 2 1 5 1 4]

Hm, Values shift from right to left each day for bins 0 through 5. Additionally, the value of bin 0 seems to wrap around to the other side and end up in bin 8. This shouldn’t be a surprise if we think about the rules for a moment. On a given day, we know the following:

• All the fish with 4 days left had 5 days left yesterday
• All the fish with 3 days left had 4 days left yesterday
• etc..

So, if we rotated the array containing the counting sort by 1, we could capture most of the action.

1 [1 1 2 1 0 0 0 0 0] --> rotate --> 2 [1 2 1 0 0 0 1 0 1]

This works because the value in bin i yesterday needs to be in bin i-1 today. But, it’s not quite right. Let’s compare the rotated array against what we should have from day 2:

rotated: [1 2 1 0 0 0 0 0 1]
actual:  [1 2 1 0 0 0 1 0 1]

Bin 6’s count is off! Ah, right. When a lanternfish hits day 0, it creates a new lanternfish and resets its timer to 6. So, before we rotate the array, we need to save the count in bin 0, and add it to the count in bin 6 once we rotate!

Putting it Together

I ended up writing a function simulate() that carries out this algorithm. Note that I’m returning an int64 to avoid any nasty surprises from an integer wraparound.

func simulate(fishes []int, days int) int64 {
	hist := make([]int, 9)

	for _, fish := range fishes {
		hist[fish]++
	}

	for day := 0; day < days; day++ {
		zero := hist[0]
		hist = append(hist[1:], zero)
		hist[6] += zero
	}

	sum := int64(0)
	for _, count := range hist {
		sum += int64(count)
	}

	return sum
}

We create a counting sort hist using the input data, and for each day of the simulation, we rotate the array and update the count in bin 6. At the end, we can count the total population simply by summing the values across all the bins!

Takeaways

The transition from Part 1 to Part 2 is rough. Some days, it’s an incremental change. Other days, it triggers a full rewrite of your code. Don’t get discouraged when this happens, it’s by design! Software engineering is all about adapting to changing requirements. Sometimes, when the requirements change, it’s what inspires you to try a new approach.

Once again, Advent of Code reminds us to be mindful of what we model. We don’t need to know the timer for each individual fish, we just need to be able to know how many are at a certain day. If a problem seems like it’s generating an absurd amount of work and/or data, see if you can simplify your representation of the problem set.

Additionally, it helps to explore the data set and the examples! Analyzing the data in the examples helped me clue into the fact that an array rotation was in play. If you’ve got a hypothesis, there’s nothing wrong with analyzing the data set to see if your theory holds up.

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.