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 mut grid = [0; 144];
15
16    for (y, row) in input.lines().enumerate() {
17        for (x, b) in row.bytes().enumerate() {
18            grid[12 * (y + 1) + (x + 1)] = b - b'0';
19        }
20    }
21
22    grid
23}
24
25pub fn part1(input: &Input) -> usize {
26    let (total, _) = simulate(input, |_, steps| steps < 100);
27    total
28}
29
30pub fn part2(input: &Input) -> usize {
31    let (_, steps) = simulate(input, |flashes, _| flashes < 100);
32    steps
33}
34
35fn simulate(input: &Input, predicate: fn(usize, usize) -> bool) -> (usize, usize) {
36    let mut grid = *input;
37    let mut flashed = [true; 144];
38    let mut todo = Vec::with_capacity(100);
39
40    let mut flashes = 0;
41    let mut steps = 0;
42    let mut total = 0;
43
44    while predicate(flashes, steps) {
45        flashes = 0;
46
47        // Bump each octopus's energy level by one. If it flashes then add to `todo` queue.
48        for y in 0..10 {
49            for x in 0..10 {
50                let index = 12 * (y + 1) + (x + 1);
51                flashed[index] = false;
52                bump_octopus(&mut grid, &mut flashed, &mut todo, index);
53            }
54        }
55
56        // Process each flash, possibly adding more to the queue.
57        while let Some(i) = todo.pop() {
58            flashes += 1;
59
60            for next in [i + 1, i + 11, i + 12, i + 13, i - 1, i - 11, i - 12, i - 13] {
61                if !flashed[next] {
62                    bump_octopus(&mut grid, &mut flashed, &mut todo, next);
63                }
64            }
65        }
66
67        steps += 1;
68        total += flashes;
69    }
70
71    (total, steps)
72}
73
74/// Increments an octopus's energy. If it reaches 10, it flashes and is added to the queue.
75#[inline]
76fn bump_octopus(grid: &mut [u8], flashed: &mut [bool], todo: &mut Vec<usize>, index: usize) {
77    if grid[index] < 9 {
78        grid[index] += 1;
79    } else {
80        grid[index] = 0;
81        flashed[index] = true;
82        todo.push(index);
83    }
84}
aoc/year2021/day11.rs

aoc/year2021/
day11.rs
