Advent Of Code - Day 6

Alright. This time, we are going to learn something that AOC does from time to time… Let’s break it down.

Day 6 - Part 1

We start off really easy. We venture around in the sea, looking for nothing but trouble. We have our squid friend with us, whom we were telling everything about vents on the sea floor. Which happen to line up perfectly straight for some weird reason.

And then we encounter a bunch of fish. Like… a LOT of fish. Nothing to worry about, right? But just in case, we map how these fish reproduce. AOC tells us here that they might be reproducing in an exponential. And in hindsight, this should have given us a clue on part 2. But I get ahead of myself.

First, let’s list our constraints, or rules. We read the text and it’s not a 100% clear yet. We see some text in bold, usually those mean something. And with the number 7 we have our first rule.

• fish reproduce every 7 day

We read on and we see that there is a behavior example there. Reading this requires a bit of understanding. But what comes out of it is that..

• A fish has an internal clock which decreases each day.
• When it hits 0 a new fish is created with initial timer of 8.
• The fish’s timer is then reset to 6.

And that’s it. The rest is just basically telling us that then all fish will have their timer move. The rest of the text is basically fluff after this. We read things like, why it’s reset to 6 and not 7. But we already know that in computer science everything starts from 0 anyways. And it’s usually hinted if not. Then we have some more information that the new fish’s timer only ticks on the new day and not on the day it was born. That’s all fine.

Then we have our first example. Cool, looks really nice. Let’s take it on.

Now, here I decided that upon reading this, I’m going to create a fish struct and track the internal timer. Further, I decided that I’m going to let the fish take care of the tick event on each new day.

This looks like this:

type fish struct {
	timer int
}

func (f *fish) tick() *fish {
	if f.timer == 0 {
		f.timer = 6
		return newFish()
	}
	f.timer--
	return nil
}

func newFish() *fish {
	return &fish{
		timer: 8,
	}
}

Basically, once it hits 0 we create a new fish with timer 8 and reset the timer back to 6. Pretty easy.

We loop this in a 80 day cycle, and the length of the created list is how many fish we’ll have. We always tick each fish on each day ( this should have raised an alarm flag here, but I was typing fast… ).

The main loop looks like this:

	days := 0
	for days < max {
		for _, f := range fishes {
			if fish := f.tick(); fish != nil {
				fishes = append(fishes, fish)
			}
		}
		days++
	}

Sweet. We list the length of the list, and indeed, that’s the correct answer. We wrote a solution in about a minute or so. Little did we know that we were about to hit in the face with a giant fish shaped fist.

Day 6 - Part 2

So, AOC does this sometimes. It present you with a simple problem and then says, okay, now do this times 1000000. And you sit there using your machine as a heating device for the next couple days while your solution is calculating.

Obviously, that’s not the right way to do it. When you face something like this, there is ALWAYS a solution which will run withing a couple seconds. There are two solutions. You either need caching, or you need to math that sh*t out.

I don’t see an obvious way of caching here, so we’ll have to be a bit clever about it.

Let’s try to think about this a bit. What is the most difficult part in this that runs to longest? Checking each and every fish and ticking them individually. We cannot do that. That will never ever be possible. There are way too many fish. We have to find a different angle to the problem. If we can’t track the fishes what can we track? We can track the number of days. But does that help us in any way?

Let’s look at the example and try to see if we can find some kind of pattern as we go.

The ticks of the fish are the numbers of days it has left until it gives birth. All of the numbers will be in the range of 0-8.

Initial day looks like this: 3, 4, 3, 1, 2. From the example. Sometimes it helps me to sort these numbers, see if I can make out a pattern. 1, 2, 3, 3, 4. Okay, we see there are two fishes which are on the same cycle. If, like we said, we are trying to track the days instead of the fish, take a look how many fishes on a day there are.

Okay, let’s manually go and one-by-one increase the days and count the fish. Maybe we’ll see an emerging pattern.

Day 1:

After 1 day: 2,3,2,0,1

Immediately we see something very cool. The numbers all remained the same, but they shifted by one to the left.

Let’s keep going.

After 2 days: 1,2,1,6,0,8

Now we get to one of the rules. Once a fish reaches 0, there is a new fish and we reset the current fish to 6. What does that mean in our little table? Who was 0 before will be a 6 and an 8 now. Which means on the next day we can see that it will be 2, 0, 0, 0, 0, 1, 1, 1, 1 without even checking. Because our two 1s will be 0s on the next day and our one 2 will be a 1 and we get a new fish because we had a 0. But let’s check to make sure.

After 3 days: 0,1,0,5,6,7,8

And indeed, our assumption was right. But how do we track the increase? 6s will increase and 8s will track the new number of incoming fish.

So what does this tell us? It will help us keep track of the count of fish on each days. How do we get the total number of fish then? We’ll just sum up the numbers in this list.

Let’s see some code. We start off by creating our initial list with the right number of fish from our input:

	days := make([]int, 9)
	for _, f := range fishes {
		days[f]++
	}

This will produce our starting numbers. Now, what’s our cycle? Each day our fishes shift one to the left. With one tiny rule that the 0s will become 8s and 6s. Because they birth a new fish and they reset their timer back to 6. Shifting the numbers is easy, we just assign the next item to the current item. But we save the 0 first. And we create as many 6s and 8s as there were 0s.

	for i := 0; i < max; i++ {
		first := days[0]
		for i := 0; i < 8; i++ {
			days[i] = days[i+1]
		}
		days[6] += first // we add them because there might be `6`s from the previous day too we don't want to override those.
		days[8] = first // there are as many new fish as there were `0`s on the previous day
	}

Next, we sum up the numbers:

	sum := 0
	for _, f := range days {
		sum += f
	}

	fmt.Println("number of fish: ", sum)

And we are done. We run on our input, and this produces the right number pretty quickly instead of a year or a thousand.

Conclusion

Phew, this one was a nice one! It prepared us for thinking a bit instead of blindly following the rules on the first part. It helps to take a look at the numbers and draw them out one by one on a piece of paper or on the computer or anywhere. Just trace the numbers by hand, which will surely make you see a pattern in all of it.

And remember, that there is always a solution which will run fast. Whether it’s caching or a bit of math. And again, don’t be afraid to ask for clues! The people in the reddit forum are super nice and they will give you hints without spoiling the end result.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Gergely.