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/// Offsets for each of the eight neighbors. The last four offsets will wrap around when
13/// added to `u8` to give a smaller index.
14const NEIGHBORS: [u8; 8] = [1, 11, 12, 13, 243, 244, 245, 255];
15
16pub fn parse(input: &str) -> Input {
17    let bytes: Vec<_> = input.lines().map(str::as_bytes).collect();
18    let mut grid = [0; 144];
19
20    for y in 0..10 {
21        for x in 0..10 {
22            grid[12 * (y + 1) + (x + 1)] = bytes[y][x] - b'0';
23        }
24    }
25
26    grid
27}
28
29pub fn part1(input: &Input) -> usize {
30    let (total, _) = simulate(input, |_, steps| steps < 100);
31    total
32}
33
34pub fn part2(input: &Input) -> usize {
35    let (_, steps) = simulate(input, |flashes, _| flashes < 100);
36    steps
37}
38
39fn simulate(input: &Input, predicate: impl Fn(usize, usize) -> bool) -> (usize, usize) {
40    let mut grid = *input;
41    let mut flashed = [true; 144];
42    let mut todo = Vec::with_capacity(100);
43
44    let mut flashes = 0;
45    let mut steps = 0;
46    let mut total = 0;
47
48    while predicate(flashes, steps) {
49        flashes = 0;
50
51        // Bump each octopus' energy level by one. If it flashes then add to `todo` queue.
52        for y in 0..10 {
53            for x in 0..10 {
54                let index = 12 * (y + 1) + (x + 1);
55
56                if grid[index] < 9 {
57                    grid[index] += 1;
58                    flashed[index] = false;
59                } else {
60                    grid[index] = 0;
61                    flashed[index] = true;
62                    todo.push(index as u8);
63                }
64            }
65        }
66
67        // Process each flash, possibly adding more to the queue.
68        while let Some(index) = todo.pop() {
69            flashes += 1;
70
71            for offset in NEIGHBORS {
72                let next = index.wrapping_add(offset) as usize;
73                if flashed[next] {
74                    continue;
75                }
76
77                if grid[next] < 9 {
78                    grid[next] += 1;
79                } else {
80                    grid[next] = 0;
81                    flashed[next] = true;
82                    todo.push(next as u8);
83                }
84            }
85        }
86
87        steps += 1;
88        total += flashes;
89    }
90
91    (total, steps)
92}
aoc/year2021/day11.rs

aoc/year2021/
day11.rs
