Now, let’s study a little cellular automaton.

Problem description

The cellular automaton is a 10x10 array. Each square contains an octopus, described by its level of energy, from 0 to 9.

During each automaton step, the three following parts are performed consecutively :

Data structure

We need to know, during an automaton step and for each octopus, whether it has flashed or not. That is why a structure defintion is useful.

#[derive(Copy, Clone)]
pub struct Octopus {
    value: u64,
    has_flashed: bool
}

Part 1

The most natural design is to build a function, to simulate one cellular automaton step. This function uses a mutable reference, and returns the number of flashes that occur during the step.

The little trick seen in day 9 (add a border to our 2-dimensional array) is used in this problem, again.

pub fn octopuses_step(octopuses_map: &mut Vec<Vec<Option<Octopus>>>) -> u64 {
    let octopuses_map_size = octopuses_map.len() - 2;
    let mut flashes = 0;

    for i in 1..=octopuses_map_size {
        for j in 1..=octopuses_map_size {
            octopuses_map[i][j] = Some(Octopus {
                value: octopuses_map[i][j].unwrap().value + 1, has_flashed: false });
        }
    }

    let mut loop_flashes = true;
    while loop_flashes {
        loop_flashes = false;
        for i in 1..=octopuses_map_size {
            for j in 1..=octopuses_map_size {
                let octopus = octopuses_map[i][j].unwrap();
                if octopus.value > 9 && !octopus.has_flashed {
                    octopuses_map[i][j] = Some(Octopus {value: octopus.value, has_flashed: true });
                    flashes += 1;
                    loop_flashes = true;
                    update_adjacent_octopuses(octopuses_map, i, j);
                }
            }
        }
    }

    for i in 1..=octopuses_map_size {
        for j in 1..=octopuses_map_size {
            if octopuses_map[i][j].unwrap().has_flashed {
                octopuses_map[i][j] = Some(Octopus {value: 0, has_flashed: true });
            }
        }
    }

    flashes
}

The 8 possible directions are described in an array of tuples, and a little helper function is used to update the adjacent octopuses energy levels of flashing octopuses.

const DIRS: [(isize, isize); 8] = [(-1, 0), (-1, 1), (0, 1), (1, 1),
    (1, 0), (1, -1), (0, -1), (-1, -1)];

pub fn update_adjacent_octopuses(octopus_map: &mut Vec<Vec<Option<Octopus>>>,
    row: usize, col: usize) {
    for dir in &DIRS {
        let adj_row = (row as isize + dir.0) as usize;
        let adj_col = (col as isize + dir.1) as usize;

        match octopus_map[adj_row][adj_col] {
            Some(octopus) => { octopus_map[adj_row][adj_col] = 
                Some( Octopus {value: octopus.value + 1, has_flashed: octopus.has_flashed})
            },
            None => {}
        }
    }
}

Finally, in the main function, 100 steps are simulated, and the total number of flashes is returned.

const STEPS: usize = 100;

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let mut octopus_map = parse_octopuses_map(input);
    let mut flashes = 0;

    for _i in 0..STEPS {
        flashes += octopuses_step(&mut octopus_map);
    }

    flashes
}

I was a bit confused when reading the puzzle description (I did not understand that “flashed” octopuses should lose their energy at the very end of the automaton step), and had to do some extra debug work. I spent about 1 hour and 10 minutes.

Part 2

Now, the number of steps is unlimited. The simulation is run until a particular state is reached, where all octopuses flash at the same time (they are “synchronized”).

We add a little function to check if all octopuses have flashed.

pub fn is_synchronizing(octopuses_map: &Vec<Vec<Option<Octopus>>>) -> bool {
    let octopuses_map_size = octopuses_map.len() - 2;
    
    for i in 1..=octopuses_map_size {
        for j in 1..=octopuses_map_size {
            if !octopuses_map[i][j].unwrap().has_flashed {
                return false;
            }
        }
    }

    true
}

pub fn solve_part2(input: &Vec<String>) -> usize {
    let mut octopuses_map = parse_octopuses_map(input);
    let mut step = 1;

    loop {
        octopuses_step(&mut octopuses_map);
        if is_synchronizing(&octopuses_map) {
            return step;
        }
        step += 1;
    }
}

I finished this part in 15 minutes. I made - again - a little mistake : I did not see that the number of steps was limited, and I spent a few minutes debugging the code.

A note on performances and technological advances

Part 1 runs in 130 µs and part 2 in 230 µs.

As I was reading other contestants messages about this puzzle, I noticed that someone solved it… with a Commodore 64 BASIC code !. This code runs in 1 hour and 20 minutes according to its author. This means there a Rust program running on a brand new laptop is about 13 million times faster than a BASIC program running on Commodore 64 (launched in 1982).