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()andslice()
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!
Top comments (0)