Dumbo Octopus

We’re back to NumPy problems, it seems.

We have some grid of values and we (mostly) want to manipulate these values as a whole (in parallel).

Let’s do the mandatory prelude:

aoc = __import__('aoc-common').aoc()
import numpy as np
import scipy.ndimage as ndi
from itertools import count

# test = '''5483143223
# 2745854711
# 5264556173
# 6141336146
# 6357385478
# 4167524645
# 2176841721
# 6882881134
# 4846848554
# 5283751526
# '''

text = aoc.input_text(11)
lines = text.splitlines()

octi = np.array([np.frombuffer(s.encode(), 'u1') for s in lines], 'i4')
octi -= ord('0')

Now we have some 2-dimensional array octi with numbers in [0..9]. This is our state.

Advancing the State

The core logic is how we advanced from one state to the next for a given array:

  1. let inactive be an empty set of indices.
  2. increase all values in the array by 1.
  3. for each index not in the inactive set whose value is 10 or higher:
    1. add this index to the inactive set,
    2. increase the values of this index’ direct neighbors (including diagonals) by 1, (called a “flash” in the problem statement — the value spreading out to neighboring values)
    3. return to step 3 above.
  4. reset all values with indices in the inactive set to value 0.

As it’s outlined in the problem text, the numbers represent octopodes that accumulate energy and then “flash” and spread energy to their neighbors. The key part here (step 3.2) we can model as a convolution.

Imagine we deal with 2-dimentional matrices, and that we have a masking matrix such that only where a “flash” occurs. The increase to a given element is the sum of all bordering 1s in this matrix. And we can count them by applying a convolution with a simple kernel:

Where the central element doesn’t matter. This is how image filters (blur, edge detection etc.) in photo editors used to work too, before they got all super advanced and AI.


kernel = np.ones((3,3), bool)

def step(octi, b=10):
  """In-place step octopus matrix `octi` with base (threshold) `b`."""
  octi += 1
  flashes = np.zeros(octi.shape, bool)
  while True:
    new = (octi >= b) & ~flashes
    if not np.any(new):
      break
    flashes |= new
    spread = ndi.convolve(new.astype('i1'), kernel, mode='constant', cval=0)
    octi += spread

  octi[octi >= b] = 0
  return np.count_nonzero(flashes)

Here I’ve also applied the natural generalization, i.e. we can change the “base” from 10 to some other number.

Part 1 & Part 2

With this, it’s easy:

answer1 = sum(step(octi.copy()) for i in range(100))

print(f'answer to part 1: {answer1}')

def first_flash(octi):
  # XXX: a loop detection algorithm should be used instead, as this will run
  # into an infinite loop on most random inputs.
  for i in count(1):
    if step(octi) == octi.size:
      return i

answer2 = first_flash(octi)

print(f'answer to part 2: {answer2}')

But There’s a Ton to Explore

The input is specifically crafted so that the matrix ends up in a cycle of length 10, with all values in the array or matrix being synchronized.

  • What other kinds of cycles can we get?

It turns out that length-10 cycles are actually fairly rare. Almost all random states end up in a cycle whose length is a multiple of 7. (From cycles of length 7 to cycles with length of several thousands (yet still multiples of 7). Of course the larger the matrix, the longer the potential cycles.)

It seems that all cycles (in this setup) are either 10 or some multiple of 7, but I haven’t attempted to prove it.

  • Why 7?

More generally, it seems that most random matrices end up in cycles with a factor where is the base. That’s why it’s 7 for base 10. Why? I don’t know, but my guess is it has to do with the diagonals and the fact that the corners of the matrix influence only three other values?

  • What about higher-dimensional arrays?

Haven’t checked.

  • What is the maximum cycle length given a matrix M×N and a base B?

I have no idea.

  • What happens at different topologies? (I.e. let’s say the edges wrapped around, which would give a torus-like topology.)

Again, a question for those with more time on their hands.