Advent of Code 2021 in Julia – Day 11: Dumbo Octopus

December 11, 2021 4-minute read

Table of Contents

Part 1
Part 2

I like the concept behind the puzzle today. It’s about autonomous synchronization. It happens in the nature all the time, see this simulation.

Part 1

Show challenge - day 11, part 1

You enter a large cavern full of rare bioluminescent dumbo octopuses! They seem to not like the Christmas lights on your submarine, so you turn them off for now.

There are 100 octopuses arranged neatly in a 10 by 10 grid. Each octopus slowly gains energy over time and flashes brightly for a moment when its energy is full. Although your lights are off, maybe you could navigate through the cave without disturbing the octopuses if you could predict when the flashes of light will happen.

Each octopus has an energy level - your submarine can remotely measure the energy level of each octopus (your puzzle input). For example:

The energy level of each octopus is a value between 0 and 9. Here, the top-left octopus has an energy level of 5, the bottom-right one has an energy level of 6, and so on.

You can model the energy levels and flashes of light in steps. During a single step, the following occurs:

First, the energy level of each octopus increases by 1.
Then, any octopus with an energy level greater than 9 flashes. This increases the energy level of all adjacent octopuses by 1, including octopuses that are diagonally adjacent. If this causes an octopus to have an energy level greater than 9, it also flashes. This process continues as long as new octopuses keep having their energy level increased beyond 9. (An octopus can only flash at most once per step.)
Finally, any octopus that flashed during this step has its energy level set to 0, as it used all of its energy to flash.

…

Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps. How many total flashes are there after 100 steps?

Here’s the provided input.

Show input - day 11

Here’s the solution to part 1:

using Pipe: @pipe

input = "4764745784
4643457176
8322628477
7617152546
6137518165
1556723176
2187861886
2553422625
4817584638
3754285662
"

function find_flash(d)
    positions = findall(>(9), d)
    return positions
end

function diffuse_energy(pos::CartesianIndex, d=dumbos)
    x, y = pos.I
    d = [repeat([0], 10);; d;; repeat([0], 10)]
    d = [repeat([0], 12)'; d; repeat([0], 12)']
    d[x:x+2, y:y+2] = d[x:x+2, y:y+2] .+
        [1; 1; 1;; 1; 0; 1;; 1; 1; 1;;]
    d = d[2:11, 2:11]
    return(d)
end


dumbos = @pipe split(strip(input), "\n") .|> string .|>
    collect |> hcat(_...) |>
    parse.(Int, _) |> transpose

count = 0

for i in 1:100
    dumbos = dumbos .+ 1
    flash_pos = []
    new_pos = find_flash(dumbos)
    flash_pos = [flash_pos; new_pos]
    count = count + length(new_pos)
    while true
        for pos in new_pos
            dumbos = diffuse_energy(pos)
        end
        # heatmap(dumbos) |> display
        new_pos = setdiff(find_flash(dumbos), flash_pos)
        flash_pos = [flash_pos; new_pos]
        count = count + length(new_pos)
        if length(new_pos) == 0
            dumbos[dumbos .> 9] .= 0
            break
        end
    end
end

count |> print

Part 2

Show challenge - day 11, part 2

It seems like the individual flashes aren’t bright enough to navigate. However, you might have a better option: the flashes seem to be synchronizing!

If you can calculate the exact moments when the octopuses will all flash simultaneously, you should be able to navigate through the cavern. What is the first step during which all octopuses flash?

Here’s the solution to part 2:

using Pipe: @pipe

input = "4764745784
4643457176
8322628477
7617152546
6137518165
1556723176
2187861886
2553422625
4817584638
3754285662
"

function find_flash(d)
    positions = findall(>(9), d)
    return positions
end

function diffuse_energy(pos::CartesianIndex, d=dumbos)
    x, y = pos.I
    d = [repeat([0], 10);; d;; repeat([0], 10)]
    d = [repeat([0], 12)'; d; repeat([0], 12)']
    d[x:x+2, y:y+2] = d[x:x+2, y:y+2] .+
        [1; 1; 1;; 1; 0; 1;; 1; 1; 1;;]
    d = d[2:11, 2:11]
    return(d)
end


dumbos = @pipe split(strip(input), "\n") .|> string .|>
    collect |> hcat(_...) |>
    parse.(Int, _) |> transpose

count = 0
steps = 0

while true
    steps = steps + 1
    dumbos = dumbos .+ 1
    flash_pos = []
    new_pos = find_flash(dumbos)
    flash_pos = [flash_pos; new_pos]
    count = count + length(new_pos)
    while true
        for pos in new_pos
            dumbos = diffuse_energy(pos)
        end
        # heatmap(dumbos) |> display
        new_pos = setdiff(find_flash(dumbos), flash_pos)
        flash_pos = [flash_pos; new_pos]
        count = count + length(new_pos)
        if length(new_pos) == 0
            dumbos[dumbos .> 9] .= 0
            break
        end
    end
    if all(dumbos .== 0)
        break
    end
end

steps |> print