Conway Cubes
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-03-21 15:20:41

## [Advent of Code 2020 Day 17](https://adventofcode.com/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](https://www.reddit.com/r/adventofcode/wiki/solution_megathreads) 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
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
```

Here is my algorithm written in JavaScript
```js
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
```js
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
```js
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
```js
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:
```js
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:
```js
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:
```js
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:
```js
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!