Home

Day 11: Dumbo Octopus

https://adventofcode.com/2021/day/11

Challenge

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

An octopus is highlighted when it flashed during the given step.

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 3:
0050900866
8500800575
9900000039
9700000041
9935080063
7712300000
7911250009
2211130000
0421125000
0021119000

After step 4:
2263031977
0923031697
0032221150
0041111163
0076191174
0053411122
0042361120
5532241122
1532247211
1132230211

After step 5:
4484144000
2044144000
2253333493
1152333274
1187303285
1164633233
1153472231
6643352233
2643358322
2243341322

After step 6:
5595255111
3155255222
3364444605
2263444496
2298414396
2275744344
2264583342
7754463344
3754469433
3354452433

After step 7:
6707366222
4377366333
4475555827
3496655709
3500625609
3509955566
3486694453
8865585555
4865580644
4465574644

After step 8:
7818477333
5488477444
5697666949
4608766830
4734946730
4740097688
6900007564
0000009666
8000004755
6800007755

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 every 10 steps:

After step 20:
3936556452
5686556806
4496555690
4448655580
4456865570
5680086577
7000009896
0000000344
6000000364
4600009543

After step 30:
0643334118
4253334611
3374333458
2225333337
2229333338
2276733333
2754574565
5544458511
9444447111
7944446119

After step 40:
6211111981
0421111119
0042111115
0003111115
0003111116
0065611111
0532351111
3322234597
2222222976
2222222762

After step 50:
9655556447
4865556805
4486555690
4458655580
4574865570
5700086566
6000009887
8000000533
6800000633
5680000538

After step 60:
2533334200
2743334640
2264333458
2225333337
2225333338
2287833333
3854573455
1854458611
1175447111
1115446111

After step 70:
8211111164
0421111166
0042111114
0004211115
0000211116
0065611111
0532351111
7322235117
5722223475
4572222754

After step 80:
1755555697
5965555609
4486555680
4458655580
4570865570
5700086566
7000008666
0000000990
0000000800
0000000000

After step 90:
7433333522
2643333522
2264333458
2226433337
2222433338
2287833333
2854573333
4854458333
3387779333
3333333333

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?

🔗 Part Two

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?

🔗 Part A

The octopus patterns feel equal parts

Game of Life and

Sandpiles. The fact that octopuses sort of "queue up" their flashes and only flash once per "tick" makes this problem unique.

First we read our input.

import { strings } from "./util"

const octopuses: number[][] = []
strings().forEach(line => {
  octopuses.push(
    line.split("").map(c => parseInt(c))
  )
})

Then we need to model a single "tick." The algorithm can be divided into three parts.

Increase every octopus by one
1. If an octopus reaches a value of 10, queue it up (we actually use a stack but it's the same) to flash
While there are octopuses to flash:
1. Increase the total number of flashes this tick
2. Spill over to the neighbors
Set the energy of all flashed octopuses back to 0.

function tickOnce() {
  let flashes = 0
  const toFlash: [number, number][] = []
  octopuses.forEach((row, r) =>
    row.forEach((_, c) => {
      octopuses[r][c]++
      if (octopuses[r][c] === 10) {
        toFlash.push([r, c])
      }
    })
  )

  while (toFlash.length > 0) {
    const [r, c] = toFlash.pop()
    if (octopuses[r][c] === 10) {
      flashes++
      ;[
        [r - 1, c - 1],
        [r - 1, c],
        [r - 1, c + 1],
        [r, c - 1],
        [r, c + 1],
        [r + 1, c - 1],
        [r + 1, c],
        [r + 1, c + 1],
      ].forEach(([r, c]) => {
        increaseNeighbor(r, c, toFlash)
      })
    }
  }

  octopuses.forEach((row, r) =>
    row.forEach((_, c) => {
      if (octopuses[r][c] === 10) {
        octopuses[r][c] = 0
      }
    })
  )

  return flashes
}

Our increaseNeighbor function is fairly simple. It just has a couple safety checks to:

Make sure the coordinate is actually on our grid
Make sure the octopus getting ready to flash hasn't done so yet

function increaseNeighbor(
  r: number,
  c: number,
  toFlash: [number, number][]
) {
  if (
    r >= 0 &&
    r < octopuses.length &&
    c >= 0 &&
    c < octopuses[r].length &&
    octopuses[r][c] < 10
  ) {
    octopuses[r][c]++
    if (octopuses[r][c] === 10) {
      toFlash.push([r, c])
    }
  }
}

Finally, we can model a tick by repeatedly calling tickOnce and tracking the total number of flashes, and log our result.

function tick(n: number) {
  let flashes = 0
  for (let i = 0; i < n; i++) {
    flashes += tickOnce()
  }
  return flashes
}

console.log(tick(100))

🔗 Part B

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.

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?

Part B doesn't introduce any new logic that's foreign to us, so we'll reuse almost all of our code from part A.

We'll rip out tick(n: number) and replace it with a loop that does not track the total number of flashes, but instead tracks if tickOnce flashes all octopuses. The code is as follows:

const totalOctopuses =
  octopuses.length * octopuses[0].length

for (let step = 1; true; step++) {
  const flashes = tickOnce()
  if (flashes === totalOctopuses) {
    console.log(step)
    break
  }
}