Advent of Code 2021 - Day 6

For the first time this year, we have to find an efficient algorithm with a proper data structure in order to solve the part 2 of the problem.

This is a rather easy problem (I solved it in 45 minutes)… as long as you have some knowledge of Computer Science and don’t attempt a brute-force solving with a $O(scary)$ complexity.

A little bit of mathematics

The problem is easily modelized with the following recursive definition :

where $u_{s,n}$ represents the number of lanternfish on day $n$, with an internal timer (or state) of $s$.

The simulation function

The algorithm we use has a linear complexity.

First, we initialize a state counts vector with the input data. This is a vector of 9 integers representing the number of lanternfish for each state on a given day. Then, we apply the formula seen above for each day to update the vector.

pub fn simulate_lanternfishes(init_states: Vec<u64>, duration: usize) -> Vec<u64> {
    let mut lanternfish_counts = Vec::<u64>::new();
    
    for state in 0..=8 {
        lanternfish_counts.push(init_states.iter().filter(|&&x| x == state).count() as u64);
    }

    for _day in 0..duration {
        let mut new_lanternfish_counts = vec![0; 9];
        for state in 1..=8 {
            new_lanternfish_counts[state - 1] = lanternfish_counts[state]; 
        }
        new_lanternfish_counts[6] += lanternfish_counts[0];
        new_lanternfish_counts[8] += lanternfish_counts[0];
        lanternfish_counts = new_lanternfish_counts.clone();
    }

    lanternfish_counts
}

A better idea I discovered while reviewing other participants’ solutions is to use the method rotate_left(). This would make to the intermediate variable new_lanternfish_counts useless.

Final calculations (part 1 and part 2)

In the main function, we simply call the simulation function with the duration parameter (80 days for part 1) and we sum the vector returned by this function.

pub const DAYS_PART1: usize = 80;

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let lanternfish_states = input.iter()
        .map(|s| u64::from_str(s)
             .expect("States must be positive numbers")).collect::<Vec<u64>>();
    let lanternfish_counts = simulate_lanternfishes(lanternfish_states, DAYS_PART1);

    lanternfish_counts.iter().sum()    
}

The main function for part 2 is almost identical. The only difference is the duration parameter (256 days instead of 80) injected in the simulation function.

With my input data, I found that there would be 1632779838045 (more than 1.6 trillion) lanternfish after 256 days. A brute-force algorithm would have required terabytes of RAM.

On my new laptop, with a AMD Ryzen 7-4700U CPU, the part 1 was solved in 210 µs, and the part 2 in 430 µs.