TheLazy.Dev
Portfolio GitHub

Blog

adventofcode |programming |algorithms |computerscience

Conway Cubes

rmion

Robert Mion

Posted on March 21, 2022

Conway Cubes

Advent of Code 2020 Day 17

Task: Solve for X where... 

X = the number of cubes in an active state after 6 cycles
Enter fullscreen mode Exit fullscreen mode

Example input 

.#.
..#
###
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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:
.....
.....
.#.#.
..##.
..#..
Enter fullscreen mode Exit fullscreen mode

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:

#.#
.##
.#.
Enter fullscreen mode Exit fullscreen mode

Instead of the original 3x3 portion:

...
#.#
.##
Enter fullscreen mode Exit fullscreen mode

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:
[[[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’#’,’.’,’.’],
  [‘.’,’.’,’.’,’#’,’.’],
  [‘.’,’#’,’#’,’#’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]],
 [[‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’],
  [‘.’,’.’,’.’,’.’,’.’]]]
Enter fullscreen mode Exit fullscreen mode

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?
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]]]
Enter fullscreen mode Exit fullscreen mode 
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
Enter fullscreen mode Exit fullscreen mode

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]]]
Enter fullscreen mode Exit fullscreen mode

Lastly:

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

Part 1: Writing the actual algorithm

  1. Checking all adjacent cubes of a single origin cube
  2. Generating the list of cubes needing switched
  3. Padding the array with an extra 1-element-sized wrapper
  4. The first step last: generating the initial conway cube
  5. An outline of my full working algorithm for Part 1
  6. The journey of Part 1
  7. 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
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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))
]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Displaying the count:

console.log(conway.flat(3).filter(el => el == 1).length)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

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])
}
Enter fullscreen mode Exit fullscreen mode

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!

💖 💪 🙅 🚩
rmion
Robert Mion

Posted on March 21, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Rain Risk
adventofcode Rain Risk

April 3, 2022

Docking Data
adventofcode Docking Data

March 28, 2022

Rambunctious Recitation
adventofcode Rambunctious Recitation

March 25, 2022

Shuttle Search
adventofcode Shuttle Search

March 31, 2022

Ticket Translation
adventofcode Ticket Translation

March 24, 2022