Robert Mion

Posted on Mar 21, 2022

Conway Cubes

#adventofcode #programming #algorithms #computerscience

Advent of Code 2020 Day 17

Task: Solve for X where...

X = the number of cubes in an active state after 6 cycles

Example input

.#.
..#
###

It represents

Cubes in either an active # or inactive . state
A 3x3x1 region of cubes within an infinite 3-dimensional grid

Visualizing the 26 neighboring cubes

Top-down view of a center cube's neighboring cubes

Top     Middle  Bottom
***     ***     ***
***     * *     ***
***     ***     ***

9 * 3 - 1 = 27 - 1 = 26

Criteria for changing state:

Stay active if:
  Count of neighbors in active state is 2
  or Count of neighbors in active state is 3

Stay inactive if:
  Count of neighbors in active state is not 3

Otherwise, maintain current state

Visualizing the grid for the first cycle

Input:

.#.
..#
###

As cube:

Top     Middle   Bottom
  .       .        .
 . .     # #      . .
. . .   . . #    . . .
 . .     . #      . .
  .       #        .

Becomes:
#.#
.##
.#.

Wait. What? No it doesn't!

For example:
- the top-left cube is inactive
- there is only one active cube adjacent to it
- so it stays inactive
- but the example diagram suggests it switches to active

After lots of head scratching on my own, I consulted the Advent of Code Sub-Reddit's Solution Mega-thread for this puzzle.

Thankfully, one of the commenter's shared my confusion:

How does the middle cube, with 5 active neighbors, become active - when the rules state that an inactive cube needs exactly 3 active neighbors to change state?

More thankfully, a responder shared that - contrary to what you might think the example diagram depicts - the cube represented by the middle dot in the input is represented by the top-middle dot in the z=0 diagram after 1 cycle.

I needed to draw it out:

Input:
.#.
..#
###

Just those 9 cubes become:
...
#.#
.##

But the grid is infinite...
...so we must expand our view

Input expanded:
.....
..#..
...#.
.###.
.....

All 25 cubes become:
.....
.....
.#.#.
..##.
..#..

Thus, the z=0 layer of After 1 cycle now makes sense.

The author chose to only show the 3x3 portion of that layer which encompassed all active cubes:

#.#
.##
.#.

Instead of the original 3x3 portion:

...
#.#
.##

Mini-mission accomplished:

Confirm my understanding of the rules
Confirm my re-create at least one cycle's new states

Considering how to construct a data structure to represent an expanding cube

Input:
.#.
..#
###

As array:
[['.','#','.'],
 ['.','.','#'],
 ['#','#','#']]

As middle layer of a 3x3 cube:
[[['.','.','.'],
  ['.','.','.'],
  ['.','.','.']],
 [['.','#','.'],
  ['.','.','#'],
  ['#','#','#']],
 [['.','.','.'],
  ['.','.','.'],
  ['.','.','.']]]

As middle layer of a 5x5 cube:
[[[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’#’,’.’,’.’],
  [‘.’,’.’,’.’,’#’,’.’],
  [‘.’,’#’,’#’,’#’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]]]

Checking all 26 adjacent cubes

For x as each of these three relative positions:
[-1,0,1]

Check all 9 cubes along [y, z] axes according to these relative positions:
[-1,-1]
[ 0,-1]
[ 1,-1]
[-1, 0]
[ 0, 0]
[ 1, 0]
[-1, 1]
[ 0, 1]
[ 1, 1]

Except [0,0] if x is 0

So, nested [-1,0,1] loops?

I simultaneously feel full - and void - of clarity.

That's enough for one day's worth of algorithmic thinking.

Ok, back at it.

A first pass at pseudocode for Part 1's algorithm

Setup:
1. Process the input into an array of arrays of binary values:
  Split the input on each new line character
  Split each string into an array of characters
  Coerce each # and . character into a 1 and 0 respectively
2. Add padding to the array so it gains a 1-element-sized border
3. Create two additional layers of equal size - filling both with all 0 values

An attempt at visualizing the setup algorithm:

Before 1:
.#.
..#
###

After 1:
[[0,1,0],
 [0,0,1],
 [1,1,1]]

After 2:
[[0,0,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,0],
 [0,1,1,1,0]
 [0,0,0,0,0]]

After 3
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]],
 [[0,0,0,0,0],
  [0,0,1,0,0],
  [0,0,0,1,0],
  [0,1,1,1,0]
  [0,0,0,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]]]

Main loop:
1. Add padding in all three dimensions, turning the current array into the core of a 1-element-greater-sized shape
2. Keeping scope only to the new core, check each cube's 26 adjacent cubes, tracking the tallies of active cubes
3. Change the state of any cubes that meet the criteria

An attempt at visualizing the main loop algorithm

End of setup:
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]],
 [[0,0,0,0,0],
  [0,0,1,0,0],
  [0,0,0,1,0],
  [0,1,1,1,0]
  [0,0,0,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
  [0,0,0,0,0]]]

After 1:
[[[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]]]

After 2:
[[[0,0,0,0,0],
  [0,0,0,0,0],
  [0,!,0,0,0],
  [0,0,0,!,0]
  [0,0,!,0,0]],
 [[0,0,0,0,0],
  [0,0,!,0,0],
  [0,!,0,1,0],
  [0,!,1,1,0]
  [0,0,!,0,0]]
 [[0,0,0,0,0],
  [0,0,0,0,0],
  [0,!,0,0,0],
  [0,0,0,!,0]
  [0,0,!,0,0]]]

After 3:
[[[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,1,0,0],
  [0,0,0,1,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,1,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,0,0,1,0,0,0],
  [0,0,0,0,0,0,0]],
 [[0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0]]]

Lastly:

Repeat main loop 6 times
Count the number of 1s across all arrays
Return the count

Part 1: Writing the actual algorithm

Checking all adjacent cubes of a single origin cube
Generating the list of cubes needing switched
Padding the array with an extra 1-element-sized wrapper
The first step last: generating the initial conway cube
An outline of my full working algorithm for Part 1
The journey of Part 1
Simulator? Part 2?

Checking all adjacent cubes of a single origin cube

Starting from the 3-element list `[-1,0,1]`
  Generate a flattened 27-element list, where each element -  except 1: at the origin point `[0,0,0]` - contains the relative coordinates of all 26 adjacent cubes.

For each relative coordinate
  Look-up the value in the 3D array at that location
  And replace the coordinate with that value

Here is my algorithm written in JavaScript

const adjacents = [-1,0,1].flatMap(
  x => [-1,0,1].flatMap(
    y => [-1,0,1].map(
      z => [x,y,z].every(el => el == 0) 
        ? null : [x,y,z])))
  .filter(el => el != null)

const checkAdjacentCubes = ([X,Y,Z] = coordinate, cube) =>
  adjacents.map(([x,y,z] = c) => cube[X + x][Y + y][Z + z])

Generating the list of cubes needing switched

Create an empty list of cubes needing switched
For each layer of the cube except the first and last
  For each row except the first and last
    For each column except the first and last
      Generate the list containing all adjacent cubes' values
      Filter it to only include active cubes
      Return and store the count of active cubes
      Perform the rule checking and, if it passes given this cube's state:
        Add to the coordinates of this cube to the list
For each coordinate in the list
  Switch the value at that coordinate from 0 to 1 or vice versa

Here is my algorithm written in JavaScript

let switchers = []
for (let X = 1; X < grid.length - 1; X++) {
  for (let Y = 1; Y < grid[X].length - 1; Y++) {
    for (let Z = 1; Z < grid[X][Y].length - 1; Z++) {
      let actives = checkAdjacentCubes([X,Y,Z], grid)
                      .filter(el => el == 1).length
      grid[X][Y][Z] == 1 
        ? [2,3].includes(actives) 
        ? null : switchers.push([X,Y,Z]) :
        actives == 3 ? switchers.push([X,Y,Z]) : null
    }
  }
}
switchers.forEach(
  ([X,Y,Z] = s) => grid[X][Y][Z] = 1 - grid[X][Y][Z]
)

Padding the array with an extra 1-element-sized wrapper

Generate a template array that is two elements wider and taller than a source array
Create two independent copies to eventually act as 'buns' sandwiching the original array

For each row in each nested array
  Insert a 0 at the beginning and end of the row
For each nested array
  Insert an array filled with 0s and matching the new length of each row at the beginning and end of the array
Insert the 'buns' at the beginning and end of the outer-most array

Here is my algorithm written in JavaScript

const padArray = (RA) => {
  let template = new Array(RA[0].length + 2)
    .fill(new Array(RA[0][0].length + 2).fill(0))
  let topPlane = template.slice().map(r => r.slice())
  let bottomPlane = template.slice().map(r => r.slice())
  RA = RA.map(
    plane => plane.map(
      row => [0, ...row, 0]))
    .map(plane => {
      let template = new Array(plane[0].length).fill(0)
      let topRow = template.slice()
      let bottomRow = template.slice()
      return [topRow, ...plane, bottomRow]
  })
  RA.unshift(topPlane) && RA.push(bottomPlane)
  conway = RA
}

The first step last: generating the initial conway cube

Enclose in an array the result of the following:
  Process the input as a string
  Replace all '.' characters with 0s
  Replace all '#' characters with 1s
  Split the string at each new line character
  For each string
    Split the string at each character
    Coerce to a number: 0 or 1

Here is my algorithm written in JavaScript

let conway = [
  fs.readFileSync('input.txt', 'utf-8')
  .replaceAll(/\./g,0)
  .replaceAll(/#/g,1)
  .split('\n')
  .map(line => line.split('').map(Number))
]

An outline of my full working algorithm for Part 1

Generate the conway cube from the input
Generate the list of 26 adjacent cube relative coordinates
Pad the conway cube

Do 6 times:
  Pad the conway cube
  Switch the appropriate cubes
    Check all adjacent cubes of each cube - except the outer-most layer
    Track which cubes need to be switched
    Perform the switch

Return the count of cubes who's state is active - a.k.a. 1

Displaying the count:

console.log(conway.flat(3).filter(el => el == 1).length)

The journey of Part 1

From frustration of not recognizing what the example diagrams indicated...
...to documenting my way towards understanding, developing a strategy, and implementing several small algorithms...
...to successfully generating a correct answer
I'm feeling pretty fantastic!

Simulator? Part 2?

Simulator: I'm just not feeling motivated to make one, especially since it seems like it will be a lot of work to translate a multi-dimensional array into several stacked and skewed planes of text. Maybe another time.
Part 2? Well, I have to look...right?

Part 2

Hmm. So, I just need to account for one more nested array?
Let's try going one sub-routine at a time

Identify relative coordinates of 80 adjacent cubes:

const adjacents = [-1,0,1].flatMap(
  x => [-1,0,1].flatMap(
    y => [-1,0,1].flatMap(
      z => [-1,0,1].map(
        w => [x,y,z,w].every(el => el == 0) 
        ? null : [x,y,z,w])))
      )
  .filter(el => el != null)

Works!

Check all 80 adjacent cubes:

const checkAdjacentCubes = ([X,Y,Z,W] = coordinate, cube) =>
  adjacents.map(([x,y,z,w] = c) => cube[X + x][Y + y][Z + z][W + w])

Should work!

Switch all flagged cubes:

const switchCubes = () => {
  let switchers = []
  for (let X = 1; X < conway.length - 1; X++) {
    for (let Y = 1; Y < conway[X].length - 1; Y++) {
      for (let Z = 1; Z < conway[X][Y].length - 1; Z++) {
        for (let W = 1; W < conway[X][Y][Z].length - 1; W++) {
          let actives = checkAdjacentCubes([X,Y,Z,W], conway)
                        .filter(el => el == 1).length
          conway[X][Y][Z][W] == 1 
            ? [2,3].includes(actives) 
            ? null : switchers.push([X,Y,Z,W]) :
            actives == 3 ? switchers.push([X,Y,Z,W]) : null
        }
      }
    }
  }
  switchers.forEach(([X,Y,Z,W] = s) => conway[X][Y][Z][W] = 1 - conway[X][Y][Z][W])
}

Should work!

Pad an array:

???
Here's the hardest part, and the one I couldn't quite grasp
Too many nested arrays
I got confused by all my chained calls to Array().fill.map() and slice()

Oh, well.

I'm still proud of all this work.

And at least solving Part 1...especially in a way that set me up well to potentially solve Part 2.

Time to move on, finally!

DEV Community

Conway Cubes

Advent of Code 2020 Day 17

Task: Solve for X where...

Example input

Visualizing the 26 neighboring cubes

Visualizing the grid for the first cycle

Considering how to construct a data structure to represent an expanding cube

Checking all 26 adjacent cubes

A first pass at pseudocode for Part 1's algorithm

Part 1: Writing the actual algorithm

Checking all adjacent cubes of a single origin cube

Generating the list of cubes needing switched

Padding the array with an extra 1-element-sized wrapper

The first step last: generating the initial conway cube

An outline of my full working algorithm for Part 1

The journey of Part 1

Simulator? Part 2?

Part 2

Top comments (0)

Read next

Cookie Clicker using Python Tkinter

AI Models Can Improve Abstract Reasoning During Testing Phase, Study Shows

Comparative Benchmarking: ILP, A*, and Branch and Bound Algorithms in High-Throughput Scenarios

Navigating the Directed Maze: Finding the Minimum Spanning Tree