Looks like we can also cross Cellular Automata off the bingo card!

Today's puzzle involves implementing an grid of octopuses that gain energy, then eventually flash, and reset. A flashing octopus also emits energy to its immediate neighbours.

The puzzle input is a 2D grid of energy levels, where each cell represents a single octopus.

It was a quick job to parse the structure into a state table.

type
Point = tuple[x: int, y: int]
State = Table[Point, int]

proc parse(input: string): State =
let lines = splitLines(input)
for y, line in lines:
for x, c in line:
result[(x: x, y: y)] = parseInt($c)

The first part of the puzzle was to count the number of flashes after 100 steps.

For the simulation, I recreated the neighbours iterator that I have used for a few other days.

iterator neighbours(pos: Point): Point =
let (x, y) = pos
for nx in x - 1 .. x + 1:
for ny in y - 1 .. y + 1:
if nx != x or ny != y:
yield (x: nx, y: ny)

This time, the iterator considers diagonals.

Simulating a single time unit involves iterating over all octopuses and incrementing their energy by one.

proc simulate(state: var State): int =
var stack: seq[Point]
var flashed: HashSet[Point]

for pos, energy in state:
state[pos] = energy + 1

Next, we can make a note of all the octopuses who will flash.

proc simulate(state: var State): int =
var stack: seq[Point]
var flashed: HashSet[Point]

for pos, energy in state:
state[pos] = energy + 1

for pos, energy in state:
if energy <= 9: continue
flashed.incl(pos)
stack.add(pos)

After flashing, we need to transfer one energy to all the neighbouring octopuses, and if they flash, we need to continue the process.

I usually find these kinds of recursive solutions easier to implement with a stack, so that's what I did here.

proc simulate(state: var State): int =
var stack: seq[Point]
var flashed: HashSet[Point]

# ...

while stack.len > 0:
var pos = stack.pop()

for next in neighbours(pos):
if next in state and next notin flashed:
state[next] += 1
if state[next] > 9:
stack.add(next)
flashed.incl(next)

The final step to reset the octopuses that flashed and return the length of the flashed set to solve the first part of the puzzle.

proc part1(input: string): int =
var state = parse(input)
for i in 1 .. 100:
result += simulate(state)

The second part of the puzzle was to find the first time step where all octopuses flash together.

My implementation for part one made this straightforward.

proc part2(input: string): int =
var state = parse(input)
for i in 1 .. high(int):
let flashes = simulate(state)
if flashes == state.len:
return i

I initially tried to use inf but in Nim, inf is a float, so I used high(int) instead, to make sure the loop kept going for as long as possible.

Not much more to say, here's the code:

GitHub Day 11