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

aoc/year2021/
day11.rs
