Advent of code 2021: Day 6

This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.

In this article I'll be solving: Advent of code 2021: Day #6.

Part 1

The puzzle gives you an input file containing a bunch of numbers. Each number represents a single lantern fish, where the number itself represent the amount of days before a new lantern fish is born from said lantern fish. Each 7 days a new lantern fish is born, however firstborn lantern fishes take 9-days to produce their first new lantern fish.

The first, kind of brain-dead, method is this:

fn immaculate_conception(mut lantern_fish: Vec<i16>, days: i16) -> u128 {
    for _ in 0..days {
        for i in 0..lantern_fish.len() {
            if lantern_fish[i] == 0 {
                lantern_fish[i] = 6;
                lantern_fish.push(8);
            } else {
                lantern_fish[i] -= 1;
            }
        }
    }

    lantern_fish.len() as u128
}

#[test]
fn test_lantern_fish() {
    let mut lantern_fish = vec![3, 4, 3, 1, 2];
    let count = immaculate_conception(lantern_fish.clone(), 18);
    assert_eq!(count, 26);

    let count = immaculate_conception(lantern_fish.clone(), 80);
    assert_eq!(count, 5934);
}

Gained one star!

Part 2

Here is where things get really tricky, because the puzzle asks how many fishes there will be after 256 days. The problem with 256 is that the population growth will be too much to handle reasonably in a single array. The array will grow insanely large, grinding the whole process to a halt.

I’ve been looking around to see if we can solve it with some basic math, but I think we need some of the more advanced chapters of math, to solve this one. However, here are my thoughts:

Assume we have 1 fish who takes 7 days (6) before there’s new offspring. Assume that each new offspring also takes 7 days the first time around, instead of the 9-days (I know, that’s not the case, but let’s just make the problem smaller). If that’s the case, we’d say: “each 7 days the population doubles”. If we let this one lantern fish swim about for 30 days, we’d assume that this lantern fish ends up with 30 / 7 = 4, 2⁴ = 16 lantern fishes.

If the lantern fish only takes 2 days (1) before there’s new offspring, the lantern fish would take (30 - 2) = 28, 28 / 7 = 4, 2⁵ = 32 lantern fishes. Now to tackle the 9-day limit for the firstborns:

Brain fart 1: Determining the growth factor

I think the question I need to answer is: “How much does the population increase over N days?”. When we remove the 9-day constraint for newborns, and assume N = 30, what would the growth factor look like?

Assume we have 1 fish

0) 6 (Start at 6)
-----------------
1) 5
2) 4
3) 3
4) 2
5) 1
6) 0
7) 6 (x2, or (1 + 100 / 100))
8) 5
9) 4
10) 3
11) 2
12) 1
13) 0
14) 6 (x2, or (1 + 100 / 100))
15) 5
16) 4
17) 3
18) 2
19) 1
20) 0
21) 6 (x2, or (1 + 100 / 100))
22) 5
23) 4
24) 3
25) 2
26) 1
27) 0
28) 6 (x2, or (1 + 100 / 100))
29) 5
30) 4

Reading up on growth factors [1] I guess to calculate what’s going on here:

Every 7 days we double are population, so 100%.
The growth factor is:

1 + (100 / 100) = 2

The growth factor per day is 2^(1/7) = 1.104089

1.104089^30 = 19.504
1.104089^28 = 15.999

We end up with 16 fishes, not 19 fishes. The reason why this is a bit broken is that this also counts how many non-completed fishes are formed within the other fishes, which adds up as a complete lantern fish. This shouldn’t happen but with some integer division, we can work around this problem, namely by doing (30 / 7) x 7.

This still only resolves the problem, without taking into account the initial 9-days. This brain fart will bring me nowhere.

Brain fart 2: counting with a vector

What if we could do something like this:

let lantern_fish = vec![3, 4, 3, 1, 2];
let mut fish_counts = vec![1; lantern_fish.len()];

// do some magic

We know that after 3 days, I gain a fish for lanter_fish[0]. To do the rest, we do something like this:

for i in 0..lantern_fish.len() {
    if days > lantern_fish[i] {
        fish_counts[i] += 1; // Initial cycle

        let d_left = days - lantern_fish[i];
        println!("{}", d_left);
    }
}

// d_left prints 15,14,15,17,16

The first time, let’s ignore the 9 rule, and just stick to the 7 rule. So our fishes double each 7th day.

… yeah, this is also going nowhere.

Time to watch match videos!

The generic growth rate formula is: “y = a * e^kt” [2]. However, for this puzzle we don’t really have a generic growth rate now do we? If we have 1 fish, it takes 7 days to make a baby, but that one baby takes 9-days (at step 1) + steps of 7 days ad infinitum, to make more fishes. If we had one fish at 3 days before it would spawn another baby and 30 days on the clock we’d get:

Fish count: 1

(30 - 3) = 27 1 clone
27 / 7 = 3 clones

My one original fish, will be solely responsible for 5 fishes already. The clones happen at day 3, day 10, day 17, day 24. The fish born on day 3 will clone itself on day 12 and on day 19 and 26.

You’d end up with 15 fishes in total, if I resolve it by pen and paper. I have no idea how to make a formula for this. If we assume that the ‘9-days for fish 1’ is not a real rule we’d get: “2^{(N - start) / 7}”. With the example above we’d get:

2^((30 - 3) / 7) = 14,491578628

It’s close, but no cigar. The 9 is a singular shift of 2? So maybe this results in the right answer?

2^((30 + 2 - 3) / 7) = 14.48

Maybe I need to drop off some fishes? Because this does give me too many fish for sure.

If we take the example for 3,4,3,1,2 and 18 days, resulting in 26 fish we’d get:

2^((18 - 3) / 7) = 4.46
2^((18 - 4) / 7) = 4
2^((18 - 3) / 7) = 4.46
2^((18 - 1) / 7) = 5.38
2^((18 - 2) / 7) = 4.87
------------------------------+
21 + 5 = 26

After some fiddling I end up with:

fn fast_conception(l: Vec<u16>, days: u16) -> u128 {
    l.iter().map(|n| 2_u128.pow((days - n) as u32 / 7)).sum()
}

This doesn’t exactly work because it comes out too high….

I gave up. I broke a rule and checked out the answers. It sucks, but at one point I have to throw in the towel. There’s no way I would’ve come up with any of these answers.

Sources

[1] https://www.dr-aart.nl/Percentages-growth-factors.html

[2] https://www.mathsisfun.com/algebra/exponential-growth.html

The full solution is available on GitHub.

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