Advent of code 2021: Day 11
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #11.
Part 1
I continue my Christmas themed submarine down the cavern and encounter a bunch of bioluminescent octopuses. They’re in a grid of 10x10 and they each have an energy level. Every step, the octopuses’ energy levels increase by 1. Once an octopus reaches an energy level >9 it flashes. A flash causes all surrounding octopuses (including diagonals) to increase by 1, which could cause subsequent flashes. All the flashed octopuses energy levels will reset to 0, once they’ve flashed. How many flashes occur after 100 steps for the provided input?
The first method I wrote was a get_points() method, which I took from “Largest product in a grid” and tweaked slightly to only return non-edge values:
type Grid = Vec<Vec<u8>>;
fn get_points(grid: &Grid, y: usize, x: usize) -> Vec<(i32, i32, u8)> {
let directions = vec![
(-1, -1), (-1, 0), (-1, 1), // TL T TR
(0, -1), (0, 1), // L R
(1, -1), (1, 0), (1, 1) // BL B BR
];
let mut found_points = vec![];
for (dy, dx) in directions {
let temp = vec![];
let y = y as i32 + dy;
let x = x as i32 + dx;
let y_row = grid.get(y as usize).unwrap_or(&temp);
if let Some(p) = y_row.get(x as usize) {
found_points.push((y, x, *p));
}
}
found_points
}
#[test]
fn test_get_points() {
let example = vec![
vec![5, 4, 8, 3, 1, 4, 3, 2, 2, 3],
vec![2, 7, 4, 5, 8, 5, 4, 7, 1, 1],
vec![5, 2, 6, 4, 5, 5, 6, 1, 7, 3],
vec![6, 1, 4, 1, 3, 3, 6, 1, 4, 6],
vec![6, 3, 5, 7, 3, 8, 5, 4, 7, 8],
vec![4, 1, 6, 7, 5, 2, 4, 6, 4, 5],
vec![2, 1, 7, 6, 8, 4, 1, 7, 2, 1],
vec![6, 8, 8, 2, 8, 8, 1, 1, 3, 4],
vec![4, 8, 4, 6, 8, 4, 8, 5, 5, 4],
vec![5, 2, 8, 3, 7, 5, 1, 5, 2, 6]
];
assert_eq!(
get_points(&example, 0, 0),
vec![(0, 1, 4), (1, 0, 2), (1, 1, 7)]
);
}
To count the actual flashes after a certain amount of steps, I wrote a single method. This method is a for-loop which is roughly split into three other loops. I’ll go over them one by one. The initial outside loop looks like this:
let size = octopuses.len();
let mut flashes = 0;
for _ in 0..steps {
// ...
}
I define two variables and a loop that executes a bit of code in a certain amount of steps. The first part of the inside of that loop does nothing more than adding 1 to the entire matrix and listing which octopuses are about to flash:
let mut flash_points = vec![];
for y in 0..size {
for x in 0..size {
octopuses[y][x] += 1;
if octopuses[y][x] > 9 {
flash_points.push((y, x));
}
}
}
The next loop is a variation of the same loop I wrote in Day 9. I start with a counter and go over each flashing octopus. Every surrounding octopus’ energy level is increased by 1. Next up, I test if any surrounding octopus therefor flashes, and if I haven’t already seen this octopus previously. Keep on going until no more new flashers have been discovered.
let mut start = 0;
while start < flash_points.len() {
let (fy, fx) = flash_points[start];
let surroundings = get_points(&octopuses, fy, fx);
for (sy, sx, _) in surroundings {
let ssy = sy as usize;
let ssx = sx as usize;
let point = (ssy, ssx);
octopuses[ssy][ssx] += 1;
if octopuses[ssy][ssx] > 9 &&
!flash_points.contains(&point) {
flash_points.push(point);
}
}
start += 1
}
The last bit is a bit dull, but it resets the flash points to 0 and adds 1 to the flashes counter.
for (fy, fx) in flash_points {
flashes += 1;
octopuses[fy][fx] = 0;
}
And this is how I resolved part 1! ⭐️
Part 2
The second part of the puzzle asks when all octopuses flash simultaneously. Because the setup I already have from the previous part is generic enough, this is really easy to solve. I extracted the inner-loop I described earlier to a separate method and reduced the 100-step flash code to this:
fn dumbo_octopus_flashes(octopuses: &mut Grid, steps: usize) -> usize {
let size = octopuses.len();
(0..steps).fold(0, |f, _| f + get_flash_points(octopuses, size))
}
To resolve when all octopuses flash simultaneously is - in essence - saying: when do the amount of flash points equal to the area of the grid?
fn all_flash(octopuses: &mut Grid) -> usize {
let size = octopuses.len();
let mut start = 0;
loop {
let step_flashes = get_flash_points(octopuses, size);
start += 1;
if step_flashes == size.pow(2) {
break start
}
}
}
That’s all it is. Solved! ⭐️
The full solution is available on GitHub.
