Day 11: Dumbo Octopus

Built a grid and just iterated through it. During the first pass I looked at which ones were going to flash and stored that in a list. Then as flashes lit up their neighbors those got checked to see if they would flash too. Once something did flash I kept track of it to stop it from flashing again and also so I knew to reset it

import re
from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index2, row in enumerate(data):
    for index, val in enumerate(list(row)):
        grid[index2][index] = int(val)

bounds_x = len(grid.keys())
bounds_y = len(grid[0].keys())

def display_grid(grid):
    print("------------")
    for row in grid.keys():
        this_row = ""
        for col in grid[row].keys():
            this_row = this_row + str(grid[row][col])
        print(this_row)

        
directions = [(1,0),(1,1),(0,1),(0,-1),(-1,-1),(-1,0),(1,-1),(-1,1)]
flash_count = 0
for step in range(100):
    to_flash = []
    flashed = []
    for row in grid.keys():
        for col in grid[row].keys():
            grid[row][col] = grid[row][col] + 1
            if grid[row][col] > 9:
                to_flash.append((row, col))
    while len(to_flash) > 0:
        flash = to_flash.pop()
        flashed.append(flash)
        flash_count = flash_count + 1
        row = flash[0]
        col = flash[1]
        for direction in directions:
            nearby_x = row + direction[0]
            nearby_y = col + direction[1]
            if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
                grid[nearby_x][nearby_y] = grid[nearby_x][nearby_y] + 1
                if grid[nearby_x][nearby_y] > 9 and (nearby_x, nearby_y) not in to_flash and (nearby_x, nearby_y) not in flashed:
                    to_flash.append((nearby_x, nearby_y))
    #done flashing
    #print(flashed)
    for coords in flashed:
        grid[coords[0]][coords[1]] = 0
print(flash_count)
display_grid(grid)
            

It's a 10x10 grid, so 100 jellyfish. I just changed the loop to go from counting steps to seeing if 100 jellyfish flashed this iteration

import re
from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index2, row in enumerate(data):
    for index, val in enumerate(list(row)):
        grid[index2][index] = int(val)

bounds_x = len(grid.keys())
bounds_y = len(grid[0].keys())

def display_grid(grid):
    print("------------")
    for row in grid.keys():
        this_row = ""
        for col in grid[row].keys():
            this_row = this_row + str(grid[row][col])
        print(this_row)

        
directions = [(1,0),(1,1),(0,1),(0,-1),(-1,-1),(-1,0),(1,-1),(-1,1)]
flash_count = 0
synced = False
step_count = 0
while not synced:
    step_count = step_count + 1
    to_flash = []
    flashed = []
    for row in grid.keys():
        for col in grid[row].keys():
            grid[row][col] = grid[row][col] + 1
            if grid[row][col] > 9:
                to_flash.append((row, col))
    while len(to_flash) > 0:
        flash = to_flash.pop()
        flashed.append(flash)
        flash_count = flash_count + 1
        row = flash[0]
        col = flash[1]
        for direction in directions:
            nearby_x = row + direction[0]
            nearby_y = col + direction[1]
            if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
                grid[nearby_x][nearby_y] = grid[nearby_x][nearby_y] + 1
                if grid[nearby_x][nearby_y] > 9 and (nearby_x, nearby_y) not in to_flash and (nearby_x, nearby_y) not in flashed:
                    to_flash.append((nearby_x, nearby_y))
    #done flashing
    #print(flashed)
    for coords in flashed:
        grid[coords[0]][coords[1]] = 0
    if len(flashed) == 100:
        synced = True
print(step_count)
display_grid(grid)
            

• Building a visualizer may be really helpful so you can see what it was doing

• When debugging my simulation, I ran my output and the examples through https://www.diffchecker.com/diff, which is a neat way to tell the difference between blocks of text. It didn't highlight the individual differences, but it could tell me if my grids matched what they were supposed to be. This only works if you manage not to fuck up your x and y coordinates

• Like I mentioned above, you may be able to reuse code from previous days, like day 9

• The fact that each jellyfish can flash exactly once per step and all if them that flash reset to 0 greatly simplifies aspects of this model

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

function findNeighbors(x,y,octopusGrid) {
	let neighbors = [];
	let rowBoundary = octopusGrid.length-1;
	let colBoundary = octopusGrid[0].length-1;
	// left
	if (x-1 >= 0) {
		neighbors.push({ x: x-1, y: y });
	}
	// right
	if (x+1 <= colBoundary) {
		neighbors.push({ x: x+1, y: y });
	}
	// up
	if (y-1 >= 0) {
		neighbors.push({ x: x, y: y-1 });
	}
	// down
	if (y+1 <= rowBoundary) {
		neighbors.push({ x: x, y: y+1 });
	}
	// up-left
	if (x-1 >= 0 && y-1 >= 0) {
		neighbors.push({ x: x-1, y: y-1 });
	}
	// up-right
	if (x+1 <= colBoundary && y-1 >= 0) {
		neighbors.push({ x: x+1, y: y-1 });
	}
	// down-left
	if (x-1 >= 0 && y+1 <= rowBoundary) {
		neighbors.push({ x: x-1, y: y+1 });
	}
	// down-right
	if (x+1 <= colBoundary && y+1 <= rowBoundary) {
		neighbors.push({ x: x+1, y: y+1 });
	}
	return neighbors;
}

function simulateStep(octopusGrid) {
	let flashedThisStep = [];
	let newGrid = [];
	// serialize into objects
	for (let y = 0; y < octopusGrid.length; y++) {
		let currentRow = octopusGrid[y];
		let newRow = [];
		for (let x = 0; x < currentRow.length; x++) {
			newRow.push({ numericValue: octopusGrid[y][x] });
		}
		newGrid.push(newRow);
	}
	// increment every octopus' value by 1
	for (let y = 0; y < newGrid.length; y++) {
		let currentRow = newGrid[y];
		for (let x = 0; x < currentRow.length; x++) {
			newGrid[y][x].numericValue++;
		}
	}
	// check for flashes
	for (let y = 0; y < newGrid.length; y++) {
		let currentRow = newGrid[y];
		for (let x = 0; x < currentRow.length; x++) {
			let currentOctopus = currentRow[x];
			// on flash, if not already flashed this step
			if (currentOctopus.numericValue > 9 && flashedThisStep.filter(e => e.x === x && e.y === y).length === 0) {
				let flashesToResolve = [ { x: x, y: y } ];
				while (flashesToResolve.length > 0) {
					//console.log("DEBUG: flashesToResolve = " + flashesToResolve.map(e => e.x + ',' + e.y).join(';'));
					let resolvingFlash = flashesToResolve.pop();
					//console.log("DEBUG: " + resolvingFlash.x + "," + resolvingFlash.y + " (" + newGrid[resolvingFlash.y][resolvingFlash.x].numericValue + ") flashed");
					// add to flashedThisStep
					flashedThisStep.push({ x: resolvingFlash.x, y: resolvingFlash.y });
					let neighbors = findNeighbors(resolvingFlash.x,resolvingFlash.y,newGrid);
					//console.log("DEBUG: neighbors: " + neighbors.map(e => e.x + "," + e.y).join(';'));
					// increase all neighbors
					for (const neighbor of neighbors) {
						//console.log("DEBUG: increasing neighbor " + neighbor.x + "," + neighbor.y + " (" + newGrid[neighbor.y][neighbor.x].numericValue + ") -> (" + (newGrid[neighbor.y][neighbor.x].numericValue + 1) + ")");
						newGrid[neighbor.y][neighbor.x].numericValue++;
						// check for flashes
						if (newGrid[neighbor.y][neighbor.x].numericValue > 9
								&& flashedThisStep.filter(e => e.x === neighbor.x && e.y === neighbor.y).length === 0
								&& flashesToResolve.filter(e => e.x === neighbor.x && e.y === neighbor.y).length === 0) {
							//console.log("DEBUG: adding " + neighbor.x + "," + neighbor.y + " to flashesToResolve");
							// add to flashesToResolve
							flashesToResolve.push(neighbor);
						}
					}
				}
			}
		}
	}
	// all flashed octopi have their energy reset
	for (const flashed of flashedThisStep) {
		newGrid[flashed.y][flashed.x].numericValue = 0;
	}
	return { updatedGrid: newGrid.map(e => e.map(f => f.numericValue)), flashedThisStep: flashedThisStep };
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let octopusArr = [];
	let totalFlashes = 0;
	for (const line of inputArr) {
		let tempLine = [];
		for (const char of line) {
			tempLine.push(parseInt(char));
		}
		octopusArr.push(tempLine);
	}
	//console.log(octopusArr.map(e => e.join('')).join('\n'));
	console.log("DEBUG: start of step 1: ");
	console.log(octopusArr.map(e => e.join('')).join('\n'));
	console.log("DEBUG: totalFlashes = " + totalFlashes);
	let updatedArr = simulateStep(octopusArr);
	totalFlashes += updatedArr.flashedThisStep.length;
	console.log("DEBUG: end of step 1: ");
	console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
	console.log("DEBUG: totalFlashes = " + totalFlashes);
	for (let i = 0; i < 99; i++) {
		console.log("DEBUG: start of step " + (i+2) + ": ");
		console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
		console.log("DEBUG: totalFlashes = " + totalFlashes);
		updatedArr = simulateStep(updatedArr.updatedGrid);
		totalFlashes += updatedArr.flashedThisStep.length;
		console.log("DEBUG: end of step " + (i+2) + ": ");
		console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
		console.log("DEBUG: totalFlashes = " + totalFlashes);
	}
})();

const fs = require('fs');
const readline = require('readline');

let inputArr = [];

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		try {
			inputArr.push(line);
		} catch(e) {
			console.error(e);
		}
	}
}

function findNeighbors(x,y,octopusGrid) {
	let neighbors = [];
	let rowBoundary = octopusGrid.length-1;
	let colBoundary = octopusGrid[0].length-1;
	// left
	if (x-1 >= 0) {
		neighbors.push({ x: x-1, y: y });
	}
	// right
	if (x+1 <= colBoundary) {
		neighbors.push({ x: x+1, y: y });
	}
	// up
	if (y-1 >= 0) {
		neighbors.push({ x: x, y: y-1 });
	}
	// down
	if (y+1 <= rowBoundary) {
		neighbors.push({ x: x, y: y+1 });
	}
	// up-left
	if (x-1 >= 0 && y-1 >= 0) {
		neighbors.push({ x: x-1, y: y-1 });
	}
	// up-right
	if (x+1 <= colBoundary && y-1 >= 0) {
		neighbors.push({ x: x+1, y: y-1 });
	}
	// down-left
	if (x-1 >= 0 && y+1 <= rowBoundary) {
		neighbors.push({ x: x-1, y: y+1 });
	}
	// down-right
	if (x+1 <= colBoundary && y+1 <= rowBoundary) {
		neighbors.push({ x: x+1, y: y+1 });
	}
	return neighbors;
}

function simulateStep(octopusGrid) {
	let flashedThisStep = [];
	let newGrid = [];
	// serialize into objects
	for (let y = 0; y < octopusGrid.length; y++) {
		let currentRow = octopusGrid[y];
		let newRow = [];
		for (let x = 0; x < currentRow.length; x++) {
			newRow.push({ numericValue: octopusGrid[y][x] });
		}
		newGrid.push(newRow);
	}
	// increment every octopus' value by 1
	for (let y = 0; y < newGrid.length; y++) {
		let currentRow = newGrid[y];
		for (let x = 0; x < currentRow.length; x++) {
			newGrid[y][x].numericValue++;
		}
	}
	// check for flashes
	for (let y = 0; y < newGrid.length; y++) {
		let currentRow = newGrid[y];
		for (let x = 0; x < currentRow.length; x++) {
			let currentOctopus = currentRow[x];
			// on flash, if not already flashed this step
			if (currentOctopus.numericValue > 9 && flashedThisStep.filter(e => e.x === x && e.y === y).length === 0) {
				let flashesToResolve = [ { x: x, y: y } ];
				while (flashesToResolve.length > 0) {
					//console.log("DEBUG: flashesToResolve = " + flashesToResolve.map(e => e.x + ',' + e.y).join(';'));
					let resolvingFlash = flashesToResolve.pop();
					//console.log("DEBUG: " + resolvingFlash.x + "," + resolvingFlash.y + " (" + newGrid[resolvingFlash.y][resolvingFlash.x].numericValue + ") flashed");
					// add to flashedThisStep
					flashedThisStep.push({ x: resolvingFlash.x, y: resolvingFlash.y });
					let neighbors = findNeighbors(resolvingFlash.x,resolvingFlash.y,newGrid);
					//console.log("DEBUG: neighbors: " + neighbors.map(e => e.x + "," + e.y).join(';'));
					// increase all neighbors
					for (const neighbor of neighbors) {
						//console.log("DEBUG: increasing neighbor " + neighbor.x + "," + neighbor.y + " (" + newGrid[neighbor.y][neighbor.x].numericValue + ") -> (" + (newGrid[neighbor.y][neighbor.x].numericValue + 1) + ")");
						newGrid[neighbor.y][neighbor.x].numericValue++;
						// check for flashes
						if (newGrid[neighbor.y][neighbor.x].numericValue > 9
								&& flashedThisStep.filter(e => e.x === neighbor.x && e.y === neighbor.y).length === 0
								&& flashesToResolve.filter(e => e.x === neighbor.x && e.y === neighbor.y).length === 0) {
							//console.log("DEBUG: adding " + neighbor.x + "," + neighbor.y + " to flashesToResolve");
							// add to flashesToResolve
							flashesToResolve.push(neighbor);
						}
					}
				}
			}
		}
	}
	// all flashed octopi have their energy reset
	for (const flashed of flashedThisStep) {
		newGrid[flashed.y][flashed.x].numericValue = 0;
	}
	return { updatedGrid: newGrid.map(e => e.map(f => f.numericValue)), flashedThisStep: flashedThisStep };
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let octopusArr = [];
	let totalFlashes = 0;
	for (const line of inputArr) {
		let tempLine = [];
		for (const char of line) {
			tempLine.push(parseInt(char));
		}
		octopusArr.push(tempLine);
	}
	//console.log(octopusArr.map(e => e.join('')).join('\n'));
	console.log("DEBUG: start of step 1: ");
	console.log(octopusArr.map(e => e.join('')).join('\n'));
	console.log("DEBUG: totalFlashes = " + totalFlashes);
	let updatedArr = simulateStep(octopusArr);
	totalFlashes += updatedArr.flashedThisStep.length;
	console.log("DEBUG: end of step 1: ");
	console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
	console.log("DEBUG: totalFlashes = " + totalFlashes);
	let i = 1;
	while (updatedArr.flashedThisStep.length < (updatedArr.updatedGrid.length * updatedArr.updatedGrid[0].length)) {
		console.log("DEBUG: start of step " + (i+1) + ": ");
		console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
		console.log("DEBUG: totalFlashes = " + totalFlashes);
		updatedArr = simulateStep(updatedArr.updatedGrid);
		totalFlashes += updatedArr.flashedThisStep.length;
		console.log("DEBUG: end of step " + (i+1) + ": ");
		console.log(updatedArr.updatedGrid.map(e => e.join('')).join('\n'));
		console.log("DEBUG: totalFlashes = " + totalFlashes);
		i++;
	}
	console.log("Answer found! They synchronize on step " + i);
})();

The important thing that I kept missing is that each octopus only resets its value to 0 /at the very end of each full cycle/, NOT right after updating all its neighbors. You have to keep track of all the octopodes that flashed this cycle (and may now have counters over 10), and reset all of them at once.

def compute_p1(input)
  grid = Grid.new(input)
  grid.update do |_x, _y, value|
    value.to_i
  end

  flashes = 0
  100.times do
    grid.update do |_x, _y, value|
      value + 1
    end

    already_flashed = Set.new

    until (to_flash = grid.coords_where { |value| value > 9 }
                          .to_set - already_flashed
          ).empty?

      x, y = to_flash.first
      already_flashed += [[x, y]]

      [
        [-1, -1], [0, -1], [+1, -1],
        [-1,  0],          [+1, 0],
        [-1, +1], [0, +1], [+1, +1]
      ].map { |dx,dy| [x+dx,y+dy] }
        .each do |nx,ny|
        next unless grid.in_bounds?(nx, ny)

        grid.set(nx, ny, grid.get(nx, ny) + 1)
      end
    end

    already_flashed.each do |x, y|
      grid.set(x, y, 0)
    end

    flashes += already_flashed.count
  end

  return flashes
end

Having finally got my head around the flash rules, the logic for part 2 pretty much exactly the same as part 1, we just keep going until all the values in the grid are the same. I also went ahead and updated my Grid class to add some more useful helpers.

def compute_p2(input)
  grid = Grid.new(input)
  grid.update do |_x, _y, value|
    value.to_i
  end

  cycles = 0
  until grid.all?(grid.get(0, 0))
    grid.update do |_x, _y, value|
      value + 1
    end

    already_flashed = Set.new

    until (to_flash = grid.coords_where { |value| value > 9 }
                        .to_set - already_flashed
          ).empty?

      x, y = to_flash.first
      already_flashed += [[x, y]]

      [
        [-1, -1], [0, -1], [+1, -1],
        [-1,  0],          [+1, 0],
        [-1, +1], [0, +1], [+1, +1]
      ].map { |dx,dy| [x+dx,y+dy] }
        .each do |nx,ny|
        next unless grid.in_bounds?(nx, ny)

        grid.set(nx, ny, grid.get(nx, ny) + 1)
      end
    end

    already_flashed.each do |x,y|
      grid.set(x, y, 0)
    end

    cycles += 1
  end

  return cycles
end

#!/usr/bin/env ruby

class Grid
  attr_accessor :grid
  attr_reader :width
  attr_reader :height
  attr_reader :default

  def initialize(input, default: nil)
    @grid = input.lines
              .map(&:strip)
              .map(&:chars)
    @width = @grid[0].size
    @height = @grid.size
    @default = default
  end

  def in_bounds?(x, y)
    x >= 0 && x < @width && y >= 0 && y < @height
  end

  def get(x,y)
    if x < 0 || x >= @width || y < 0 || y >= @height
      @default
    else
      @grid[y][x]
    end
  end

  def set(x,y,val)
    if x < 0 || x >= @width || y < 0 || y >= @height
      raise "Tried to write out of bounds"
    else
      @grid[y][x] = val
    end
  end

  def all_coords
    (0...width).to_a.product((0...height).to_a)
  end

  def coords_where
    all_coords.filter { |x, y| yield(@grid[y][x]) }
  end

  def each_index
    height.times do |y|
      width.times do |x|
        yield(x,y)
      end
    end
  end

  def update
    each_index do |x, y|
      @grid[y][x] = yield(x, y, @grid[y][x])
    end
  end

  def ==(other)
    return false if other.class != Grid
    return other.grid == @grid
  end

  def all?(value)
    return @grid.flatten.all?(value)
  end

  def neighbors(x,y)
    [
      [-1, -1], [0, -1], [+1, -1],
      [-1,  0],          [+1, 0],
      [-1, +1], [0, +1], [+1, +1]
    ].map { |dx, dy| get(x+dx, y+dy) }
  end

  def to_s
    s = ""
    height.times do |y|
      width.times do |x|
        s << get(x,y) || default.to_s
      end
      s << "\n"
    end
    return s
  end

  def count(value)
    if block_given?
      @grid.flatten.count(&block)
    else
      @grid.flatten.count(value)
    end
  end
end

I opted for a kind-of object-oriented style; the Grid struct is generic, while its specialization, OctopusGrid, is responsible for actually keeping track of the octopi energy levels. While Grid is kind-of trivial, I'm sure I'll find a way to reuse it in later puzzles.

I'm slightly unhappy that the OctopusGrid does not specify the neighbor-relationship; on the other hand, a separate neighborhood function can be reused elsewhere, so maybe that's preferrable.

use std::collections::VecDeque;

type Row<T> = Vec<T>;

#[derive(Clone)]
pub struct Grid<T: Copy> {
    width: usize,
    height: usize,
    rows: Vec<Row<T>>,
}

impl<T: Copy> Grid<T> {
    // Check whether the coordinate is inside the Grid
    fn in_bounds(&self, x: usize, y: usize) -> bool {
        x < self.width && y < self.height
    }

    // Width of the Grid
    fn width(&self) -> usize {
        self.width
    }

    // Height of the Grid
    fn height(&self) -> usize {
        self.height
    }

    // Size of the Grid
    fn size(&self) -> usize {
        self.width * self.height
    }

    // Get the value at (x, y)
    fn get(&self, x: usize, y: usize) -> Option<T> {
        if !self.in_bounds(x, y) {
            return None;
        }

        Some(self.rows[y][x])
    }

    fn set(&mut self, x: usize, y: usize, val: T) {
        if !self.in_bounds(x, y) {
            return;
        }

        self.rows[y][x] = val;
    }
}

type OctopusGrid = Grid<u8>;

impl OctopusGrid {
    // Increase the energy level of the octopus (up to a maximum of 254)
    fn increase(&mut self, x: usize, y: usize) {
        if let Some(val) = self.get(x, y) {
            if val < 254 {
                self.set(x, y, val + 1);
            }
        }
    }

    // If the octopus at coordinate (x, y) has not flashed
    // yet in this step, return true to indicate it flashes
    // and then set its energy level to the sentinel value.
    fn flash(&mut self, x: usize, y: usize) -> bool {
        if !self.in_bounds(x, y) {
            return false;
        }

        if let Some(255) = self.get(x, y) {
            return false;
        }

        self.set(x, y, 255);
        true
    }

    // Resets an octopus's energy level to zero
    fn reset(&mut self, x: usize, y: usize) {
        if let Some(val) = self.get(x, y) {
            if val >= 10 {
                self.set(x, y, 0)
            }
        }
    }
}

I wrapped this inside a module this time. Not sure if I like that, but it does seem cleaner and potentially more reuseable.

mod parse {
    use nom::{
        character::complete::{digit1, multispace0},
        combinator::eof,
        multi::many1,
        IResult,
    };

    fn row(input: &str) -> IResult<&str, super::Row<u8>> {
        let (input, _) = multispace0(input)?;
        let (input, row) = digit1(input)?;

        let row = row.chars().map(|c| c as u8 - b'0').collect();

        Ok((input, row))
    }

    pub fn grid(input: &str) -> IResult<&str, super::Grid<u8>> {
        let (input, rows) = many1(row)(input)?;
        let (input, _) = multispace0(input)?;
        let (input, _) = eof(input)?;

        let height = rows.len();
        let width = rows[0].len();

        let grid = super::Grid {
            rows,
            width,
            height,
        };

        Ok((input, grid))
    }
}

// Returns the neighbors of a given octopus. If a coordinate goes below zero,
// it is wrapped to a large positive number, making it easy to recognize
// and check for.
fn neighbors(x: usize, y: usize) -> [(usize, usize); 8] {
    [
        (x, y.wrapping_sub(1)),
        (x + 1, y.wrapping_sub(1)),
        (x + 1, y),
        (x + 1, y + 1),
        (x, y + 1),
        (x.wrapping_sub(1), y + 1),
        (x.wrapping_sub(1), y),
        (x.wrapping_sub(1), y.wrapping_sub(1)),
    ]
}

// Increases the enery level of each octopus and returns a
// VecDeque containing all octopi ready to flash.
fn prepare_octopi(grid: &mut OctopusGrid) -> VecDeque<(usize, usize)> {
    let mut result = VecDeque::new();

    for y in 0..grid.height {
        for x in 0..grid.width {
            grid.increase(x, y);

            if grid.get(x, y) > Some(9) {
                result.push_back((x, y));
            }
        }
    }

    result
}

// Starting from a list of ready octopi, flash all of them
fn flash_octopi(grid: &mut OctopusGrid, q: &mut VecDeque<(usize, usize)>) -> usize {
    let mut flash_count = 0;

    while let Some((x, y)) = q.pop_front() {
        // The octopus flashes if it is able to
        if !grid.flash(x, y) {
            continue;
        }

        flash_count += 1;

        // All surrounding octopi increase their energy level
        for &(nx, ny) in &neighbors(x, y) {
            grid.increase(nx, ny);

            if (Some(10)..Some(255)).contains(&grid.get(nx, ny)) {
                q.push_back((nx, ny));
            }
        }
    }

    flash_count
}

// Resets the energy level of all octopi that flashed
fn reset_octopi(grid: &mut OctopusGrid) {
    for y in 0..grid.height {
        for x in 0..grid.width {
            grid.reset(x, y);
        }
    }
}

// Simulate num_steps steps
fn step_for(grid: &mut OctopusGrid, num_steps: usize) -> usize {
    let mut count_sum = 0;

    for _ in 0..num_steps {
        let mut q = prepare_octopi(grid);
        let count = flash_octopi(grid, &mut q);
        reset_octopi(grid);

        count_sum += count;
    }

    count_sum
}

Something I learned today was that you can wrap values with Some in more places than I expected (e.g. in comparisons, not just in if let statements).

// Part I
fn part1(grid: &OctopusGrid) -> usize {
    step_for(&mut grid.clone(), 100)
}

// Part II
fn part2(grid: &OctopusGrid) -> usize {
    let mut grid = grid.clone();

    // The counter is not incremented on the last step (while loop exit condition)
    // so we need to start it at 1.
    let mut step = 1;

    while step_for(&mut grid, 1) < grid.size() {
        step += 1;
    }

    step
}

fn main() {
    let input = include_str!("../../input-11.txt");
    let grid = parse::grid(input).expect("Failed to parse puzzle").1;

    println!("Part I:  {}", part1(&grid));
    println!("Part II: {}", part2(&grid));
}

For example, I used 255 as the sentinel value for an octopus that has already flashed. However, 0 is a much better sentinel value; we're incrementing all energy levels each step, so 0 does not occur naturally and I can completely eliminate the loop that resets all octopi to zero...

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use point2d::point2d::Point2D;

const GRID_SIZE: usize = 10;
const DEBUG: bool = false;

const PART_1_STEPS: usize = 100;

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D { x: pt.x  , y: pt.y-1 },  // up
         Point2D { x: pt.x+1, y: pt.y   },  // right
         Point2D { x: pt.x  , y: pt.y+1 },  // down
         Point2D { x: pt.x+1, y: pt.y+1 },  // right down
         Point2D { x: pt.x-1, y: pt.y+1 },  // left down
         Point2D { x: pt.x+1, y: pt.y-1 },  // right up
         Point2D { x: pt.x-1, y: pt.y-1 },  // left up
         Point2D { x: pt.x-1, y: pt.y   }]  // left
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build octopus map
    let mut oct_map: Vec<Vec<u32>> = vec![vec![0; GRID_SIZE]; GRID_SIZE];
    let mut flash_map: Vec<Vec<usize>> = vec![vec![usize::MAX; GRID_SIZE]; GRID_SIZE];
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            oct_map[x][y] = ch.to_digit(10).unwrap();
        }
    }

    // Simulate
    let mut flashes: usize = 0;
    'main_lp: for step in 0.. {

        // Part 1
        if step == PART_1_STEPS {
            println!("Part 1: {}", flashes); // 1691
        }

        // Part 2
        if oct_map.iter().flatten().sum::<u32>() == 0 {
            println!("Part 2: {}", step); // 216
            break 'main_lp;
        }

        // Debug
        if DEBUG {
            println!("Step: {}", step);        
            for y in 0..GRID_SIZE {
                for x in 0..GRID_SIZE {
                    print!("{}", oct_map[x][y]);
                }
                println!();
            }
        }
        
        // First, the energy level of each octopus increases by 1.
        for y in 0..GRID_SIZE {
            for x in 0..GRID_SIZE {
                oct_map[x][y] += 1;
            }
        }

        // Then, any octopus with an energy level greater than 9 flashes.
        'inner: loop {
            let mut changes = 0;
            for y in 0..GRID_SIZE {
                for x in 0..GRID_SIZE {
                    if oct_map[x][y] > 9 && flash_map[x][y] != step {
                        flash_map[x][y] = step;
                        flashes += 1;
                        changes += 1;

                        // This increases the energy level of all adjacent octopuses by 1,
                        // including octopuses that are diagonally adjacent.
                        let pt = Point2D { x: x as i64, y: y as i64 };
                        for neighbor in neighbor_addresses(&pt) {
                            let (newx,newy) = (neighbor.x as usize, neighbor.y as usize);
                            if newx >= GRID_SIZE || newy >= GRID_SIZE { continue; }
                            oct_map[newx][newy] += 1;
                        }
                    }
                }
            }
            if changes == 0 { break 'inner; }
        }

        // Finally, any octopus that flashed during this step has its energy
        // level set to 0, as it used all of its energy to flash.
        for y in 0..GRID_SIZE {
            for x in 0..GRID_SIZE {
                if flash_map[x][y] == step {
                    oct_map[x][y] = 0;
                }
            }
        }
    }

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

defmodule AdventOfCode.Solution.Year2021.Day11.FlashCounter do
  use Agent

  def start_link do
    Agent.start_link(fn -> 0 end, name: __MODULE__)
  end

  def stop do
    Agent.stop(__MODULE__)
  end

  def increment do
    Agent.cast(__MODULE__, &(&1 + 1))
  end

  def value do
    Agent.get(__MODULE__, &Function.identity/1)
  end
end

defmodule AdventOfCode.Solution.Year2021.Day11.Octopus do
  use Agent

  alias AdventOfCode.Solution.Year2021.Day11.FlashCounter

  defstruct level: 0,
            neighbors: []

  def start_link(coords, level, neighbors) do
    Agent.start_link(
      fn -> %__MODULE__{level: level, neighbors: neighbors} end,
      name: agent_name(coords)
    )
  end

  def stop(coords) do
    Agent.stop(agent_name(coords))
  end

  # Use Agent.update/2 for tick increments so that the call blocks until
  # agent process has received the message and updated its state
 def increment(coords, :tick) do
    Agent.update(agent_name(coords), &do_increment(&1, :tick))
  end

  # Use Agent.cast/2 ("fire-and-forget") for increments caused by
  # neighboring flashes since message order isn't important during this part
  def increment(coords, :flash) do
    Agent.cast(agent_name(coords), &do_increment(&1, :flash))
  end

  def maybe_flash(coords) do
    Agent.cast(agent_name(coords), &do_maybe_flash/1)
  end

  def done?(coords) do
    Agent.get(agent_name(coords), fn _state -> do_done?() end)
  end

  defp do_increment(state, source)

  # A tick always increments
  defp do_increment(state, :tick), do: %{state | level: state.level + 1}

  # A neighbor's flash has no effect if this octopus has already flashed during this step
  defp do_increment(%{level: 0} = state, :flash), do: state

  # A neighbor's flash increments and may cause this octopus to flash
  defp do_increment(state, :flash) do
    do_maybe_flash(%{state | level: state.level + 1})
  end

  defp do_maybe_flash(%{level: level} = state) when level > 9 do
    flash(state.neighbors)
    %{state | level: 0}
  end

  defp do_maybe_flash(state), do: state

  defp flash(neighbors) do
    FlashCounter.increment()
    Enum.each(neighbors, &increment(&1, :flash))
  end

  defp do_done? do
    match?({:messages, []}, Process.info(self(), :messages))
  end

  defp agent_name(coords), do: {:global, {__MODULE__, coords}}
end

defmodule AdventOfCode.Solution.Year2021.Day11 do
  alias AdventOfCode.CharGrid
  alias __MODULE__.FlashCounter
  alias __MODULE__.Octopus

  def part1(input) do
    octopuses = setup(input)
    result = flash_count_after_step(octopuses, 100)
    teardown(octopuses)

    result
  end

  def part2(input) do
    octopuses = setup(input)
    result = get_first_synchronized_step(octopuses, length(octopuses))
    teardown(octopuses)

    result
  end

  defp setup(input) do
    FlashCounter.start_link()

    grid = CharGrid.from_input(input)

    grid
    |> CharGrid.to_list()
    |> tap(fn cells ->
      Enum.each(cells, fn {coords, level_char} ->
        Octopus.start_link(coords, level_char - ?0, CharGrid.adjacent_coords(grid, coords))
      end)
    end)
    |> Enum.map(fn {coords, _} -> coords end)
  end

  defp teardown(octopuses) do
    FlashCounter.stop()
    Enum.each(octopuses, &Octopus.stop/1)
  end

  defp flash_count_after_step(octopuses, step, current_step \\ 0)

  defp flash_count_after_step(_, step, step), do: FlashCounter.value()

  defp flash_count_after_step(octopuses, step, current_step) do
    run_step(octopuses)

    flash_count_after_step(octopuses, step, current_step + 1)
  end

  defp get_first_synchronized_step(octopuses, expected_flashes, current_step \\ 1) do
    initial_flash_count = FlashCounter.value()
    run_step(octopuses)
    flash_count = FlashCounter.value()

    if flash_count - initial_flash_count == expected_flashes do
      current_step
    else
      get_first_synchronized_step(octopuses, expected_flashes, current_step + 1)
    end
  end

  defp run_step(octopuses) do
    Enum.each(octopuses, &Octopus.increment(&1, :tick))
    Enum.each(octopuses, &Octopus.maybe_flash/1)
    block_until_step_is_done(octopuses)
  end

  defp block_until_step_is_done(octopuses) do
    unless Enum.all?(octopuses, &Octopus.done?/1) do
      block_until_step_is_done(octopuses)
    end
  end
end

#!/usr/bin/awk -f
function flash(grid, x, y,	ox, oy) {
	grid[x, y] = 0
	total += 1

	for (ox = -1; ox <= 1; ox += 1)
		for (oy = -1; oy <= 1; oy += 1)
			if (grid[x + ox, y + oy])
				if (++grid[x + ox, y + oy] >= 10)
					flash(grid, x + ox, y + oy)
}

BEGIN { FS = "" }

{
	for (i = 1; i <= NF; ++i)
		grid[i, NR] = $i
}

END {
	for (i = 1; i <= 100; ++i) {
		for (y = 1; y <= NR; ++y)
			for (x = 1; x <= NF; ++x)
				grid[x, y] += 1

		for (y = 1; y <= NR; ++y)
			for (x = 1; x <= NF; ++x)
				if (grid[x, y] >= 10)
					flash(grid, x, y)
	}

	print total
}

#!/usr/bin/awk -f
function flash(grid, x, y,	ox, oy) {
	total += 1
	grid[x, y] = 0

	for (ox = -1; ox <= 1; ox += 1)
		for (oy = -1; oy <= 1; oy += 1)
			if (grid[x + ox, y + oy])
				if (++grid[x + ox, y + oy] >= 10)
					flash(grid, x + ox, y + oy)
}

BEGIN { FS = "" }

{
	for (i = 1; i <= NF; ++i)
		grid[i, NR] = $i
}

END {
	for (i = 1 ;; ++i) {
		last = total

		for (y = 1; y <= NR; ++y)
			for (x = 1; x <= NF; ++x)
				grid[x, y] += 1

		for (y = 1; y <= NR; ++y)
			for (x = 1; x <= NF; ++x)
				if (grid[x, y] >= 10)
					flash(grid, x, y)

		if (total - last == NR * NF)
			break
	}

	print i
}