aoc/year2021/
day11.rs

1//! # Dumbo Octopus
2//!
3//! This puzzle resembles the [`Day 9`] flood fill a little. Since there are only 100 octopuses
4//! a fixed size array is used both to track current energy levels and a second array to track
5//! if an octopus has flashed this turn. Each time an octopus flashes it bumps its neighbors
6//! energy levels, which can propagate recursively through the entire grid.
7//!
8//! [`Day 9`]: crate::year2021::day09
9
10/// Pad the 10x10 grid by 1 on either side so that we can avoid boundary checks.
11type Input = [u8; 144];
12
13pub fn parse(input: &str) -> Input {
14    let bytes: Vec<_> = input.lines().map(str::as_bytes).collect();
15    let mut grid = [0; 144];
16
17    for y in 0..10 {
18        for x in 0..10 {
19            grid[12 * (y + 1) + (x + 1)] = bytes[y][x] - b'0';
20        }
21    }
22
23    grid
24}
25
26pub fn part1(input: &Input) -> usize {
27    let (total, _) = simulate(input, |_, steps| steps < 100);
28    total
29}
30
31pub fn part2(input: &Input) -> usize {
32    let (_, steps) = simulate(input, |flashes, _| flashes < 100);
33    steps
34}
35
36fn simulate(input: &Input, predicate: fn(usize, usize) -> bool) -> (usize, usize) {
37    let mut grid = *input;
38    let mut flashed = [true; 144];
39    let mut todo = Vec::with_capacity(100);
40
41    let mut flashes = 0;
42    let mut steps = 0;
43    let mut total = 0;
44
45    while predicate(flashes, steps) {
46        flashes = 0;
47
48        // Bump each octopus's energy level by one. If it flashes then add to `todo` queue.
49        for y in 0..10 {
50            for x in 0..10 {
51                let index = 12 * (y + 1) + (x + 1);
52                flashed[index] = false;
53                bump_octopus(&mut grid, &mut flashed, &mut todo, index);
54            }
55        }
56
57        // Process each flash, possibly adding more to the queue.
58        while let Some(index) = todo.pop() {
59            flashes += 1;
60
61            for next in [
62                index + 1,
63                index + 11,
64                index + 12,
65                index + 13,
66                index - 1,
67                index - 11,
68                index - 12,
69                index - 13,
70            ] {
71                if !flashed[next] {
72                    bump_octopus(&mut grid, &mut flashed, &mut todo, next);
73                }
74            }
75        }
76
77        steps += 1;
78        total += flashes;
79    }
80
81    (total, steps)
82}
83
84/// Increments an octopus's energy. If it reaches 10, it flashes and is added to the queue.
85#[inline]
86fn bump_octopus(grid: &mut [u8], flashed: &mut [bool], todo: &mut Vec<usize>, index: usize) {
87    if grid[index] < 9 {
88        grid[index] += 1;
89    } else {
90        grid[index] = 0;
91        flashed[index] = true;
92        todo.push(index);
93    }
94}
aoc/year2021/day11.rs

aoc/year2021/
day11.rs
