Advent of Code - Day 11: Dumbo Octopus

lib/advent_of_code/2021/day-11.livemd

Tyler Johnson

@tylerj

aoc

Share to X

Share to Bluesky

More notebooks

Advent of Code - Day 11: Dumbo Octopus

Mix.install([:kino])

Day 11: Dumbo Octopus

Part One: Prompt

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. Adjacent flashes can cause an octopus to flash on a step even if it begins that step with very little energy. Consider the middle octopus with 1 energy in this situation:

Before any steps:
11111
19991
19191
19991
11111

After step 1:
34543
40004
50005
40004
34543

After step 2:
45654
51115
61116
51115
45654

Here is how the larger example above progresses:

Before any steps:
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526

After step 1:
6594254334
3856965822
6375667284
7252447257
7468496589
5278635756
3287952832
7993992245
5957959665
6394862637

After step 2:
8807476555
5089087054
8597889608
8485769600
8700908800
6600088989
6800005943
0000007456
9000000876
8700006848

# ...

After step 9:
9060000644
7800000976
6900000080
5840000082
5858000093
6962400000
8021250009
2221130009
9111128097
7911119976

After step 10:
0481112976
0031112009
0041112504
0081111406
0099111306
0093511233
0442361130
5532252350
0532250600
0032240000

After step 10, there have been a total of 204 flashes. Fast forwarding, here is the same configuration after 100 steps:

After step 100:
0397666866
0749766918
0053976933
0004297822
0004229892
0053222877
0532222966
9322228966
7922286866
6789998766

After 100 steps, there have been a total of 1656 flashes.

Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps.

How many total flashes are there after 100 steps?

To begin, get your puzzle input.

Part One: Solution

input = Kino.Input.textarea("Please paste your input file:")

list = input |> Kino.Input.read() |> String.split("\n", trim: true)

["8258741254", "3335286211", "8468661311", "6164578353", "2138414553", "1785385447", "3441133751",
 "3586862837", "7568272878", "6833643144"]

grid =
  list
  |> Enum.with_index()
  |> Enum.reduce(%{}, fn {row, i}, acc ->
    row
    |> String.split("", trim: true)
    |> Enum.with_index()
    |> Enum.into(acc, fn {col, j} -> {{i, j}, String.to_integer(col)} end)
  end)

%{
  {4, 5} => 1,
  {5, 9} => 7,
  {1, 2} => 3,
  {8, 5} => 7,
  {0, 9} => 4,
  {8, 6} => 2,
  {5, 2} => 8,
  {3, 6} => 8,
  {2, 4} => 6,
  {4, 8} => 5,
  {6, 5} => 3,
  {0, 3} => 8,
  {1, 1} => 3,
  {9, 6} => 3,
  {4, 3} => 8,
  {3, 7} => 3,
  {5, 0} => 1,
  {0, 5} => 4,
  {0, 1} => 2,
  {8, 9} => 8,
  {4, 0} => 2,
  {3, 2} => 6,
  {9, 8} => 4,
  {8, 1} => 5,
  {7, 3} => 6,
  {7, 9} => 7,
  {0, 8} => 5,
  {3, 1} => 1,
  {6, 1} => 4,
  {2, 0} => 8,
  {8, 3} => 8,
  {8, 4} => 2,
  {2, 7} => 3,
  {4, 6} => 4,
  {9, 4} => 6,
  {6, 2} => 4,
  {0, 7} => 2,
  {9, 0} => 6,
  {7, 2} => 8,
  {0, 0} => 8,
  {8, 7} => 8,
  {5, 8} => 4,
  {7, 6} => 2,
  {2, 8} => 1,
  {1, 4} => 2,
  {5, 6} => 5,
  {9, 5} => 4,
  {6, 6} => 3,
  {9, ...} => 3,
  {...} => 7,
  ...
}

defmodule Octopus do
  def find_simultaneous_flash(grid, step_count \\ 1, flash_count \\ 0) do
    with {new_flash_count, new_grid} <- perform_step(grid, flash_count) do
      if new_flash_count - flash_count == map_size(grid) do
        {step_count, new_flash_count, new_grid}
      else
        find_simultaneous_flash(new_grid, step_count + 1, new_flash_count)
      end
    end
  end

  def perform_n_steps(grid, n, flash_count \\ 0) do
    Enum.reduce(
      1..n,
      {flash_count, grid},
      fn _n, {flash_count, grid} ->
        perform_step(grid, flash_count)
      end
    )
  end

  def perform_step(grid, flash_count) do
    grid
    |> increase_grid_by_1()
    |> execute_flashes()
    |> count_and_reset_flashed(flash_count)
  end

  def increase_grid_by_1(grid) do
    for {xy, value} <- grid, into: %{}, do: {xy, value + 1}
  end

  def execute_flashes(grid) do
    Enum.reduce(grid, grid, &flash_xy(&2, &1))
  end

  defp flash_xy(grid, {xy, 10}) do
    grid |> increase_xy(xy) |> increase_adjacent(xy)
  end

  defp flash_xy(grid, _), do: grid

  defp increase_xy(grid, xy) do
    case Map.has_key?(grid, xy) do
      true -> Map.update!(grid, xy, &(&1 + 1))
      false -> grid
    end
  end

  defp increase_adjacent(grid, {x, y}) do
    [
      {x - 1, y - 1},
      {x + 0, y - 1},
      {x + 1, y - 1},
      {x - 1, y + 0},
      {x + 1, y + 0},
      {x - 1, y + 1},
      {x + 0, y + 1},
      {x + 1, y + 1}
    ]
    |> Enum.reduce(grid, &increase_and_flash/2)
  end

  defp increase_and_flash(xy, grid) do
    if Map.has_key?(grid, xy) do
      grid
      |> increase_xy(xy)
      |> then(fn grid -> flash_xy(grid, {xy, grid[xy]}) end)
    else
      grid
    end
  end

  def count_and_reset_flashed(grid, flash_count) do
    Enum.reduce(grid, {flash_count, grid}, &count_and_reset_if_flashed/2)
  end

  defp count_and_reset_if_flashed({xy, value}, {flash_count, grid}) when value > 10,
    do: {flash_count + 1, Map.put(grid, xy, 0)}

  defp count_and_reset_if_flashed(_, input), do: input
end

{:module, Octopus, <<70, 79, 82, 49, 0, 0, 23, ...>>, {:count_and_reset_if_flashed, 2}}

grid |> Octopus.perform_n_steps(100) |> elem(0)

How many total flashes are there after 100 steps?

Your puzzle answer was `1694`.

The first half of this puzzle is complete! It provides one gold star: *

Part Two: Prompt

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!

In the example above, the first time all octopuses flash simultaneously is step 195:

After step 193:
5877777777
8877777777
7777777777
7777777777
7777777777
7777777777
7777777777
7777777777
7777777777
7777777777

After step 194:
6988888888
9988888888
8888888888
8888888888
8888888888
8888888888
8888888888
8888888888
8888888888
8888888888

After step 195:
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

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?

grid |> Octopus.find_simultaneous_flash() |> elem(0)

Part Two: Solution

The following function was added to the Octopus module above:

def find_simultaneous_flash(grid, step_count \\ 1, flash_count \\ 0) do
  with {new_flash_count, new_grid} <- perform_step(grid, flash_count) do
    if new_flash_count - flash_count == map_size(grid) do
      {step_count, new_flash_count, new_grid}
    else
      find_simultaneous_flash(new_grid, step_count + 1, new_flash_count)
    end
  end
end