# Advent of Code 2020 - Day 17

By Eric Burden | December 18, 2020

In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.

Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.

# Day 17 - Conway Cubes

Find the problem description HERE.

## Part One - Look At This Light

Turns out 2D Conway’s Game of Life with airport seats wasn’t enough for this year’s Advent of Code, now we have GOL in three dimensions. Cool! Lucky for us, R makes this sort of multidimensional problem fairly painless to reason about with ‘arrays, which are like matrices, but with more dimensions. This problem allowed us to short-cut the neighbor-finding algorithm a bit by just selecting a ‘chunk’ of the three-dimensional matrix centered on each point we were interested in and just replacing the central element with an empty string, which we just ignored.

# to speed up apply-type operations through the use of future_*apply functions.
library(future)
library(future.apply)
plan(multisession, workers = 6)

test_input <- c(
".#.",
"..#",
"###"
)

# Given a set of input lines representing a 'slice' of a 3d space input,
# returns a three-dimensional array containing that slice
initialize_cube <- function(input) {
dim1 <- length(input)
dim2 <- nchar(input[[1]])
input_matrix <- matrix(unlist(strsplit(input, '')), dim1, dim2, TRUE)
new_cube <- array('.', c(dim1, dim2, 1))
new_cube[1:dim1, 1:dim2, 1] <- input_matrix
new_cube
}

# Given a three-dimensional array cube, expands the array by one index in all
# directions, filling the new spaces with the '.' character
grow_cube <- function(cube) {
d <- dim(cube)
new_cube <- array('.', d + 2)

new_cube[seq(d[1])+1, seq(d[2])+1, seq(d[3])+1] <- cube
new_cube
}

# Given the x, y, and z coordinates of an element in a three-dimensional array
# (d1, d2, and d3, respectively) and the three-dimensional array cube,
# returns a sub-array containing the elements immediately adjacent to the
# indicated coordinate in all dimensions. The central element, defined by the
# indicated coordinate, is replaced by an empty string.
get_neighbors <- function(d1, d2, d3, cube) {
d <- dim(cube)
d1_range <- max(1, d1-1):min(d1+1, d[1])
d2_range <- max(1, d2-1):min(d2+1, d[2])
d3_range <- max(1, d3-1):min(d3+1, d[3])
cube[d1, d2, d3] <- ''
neighbor_slice <- cube[d1_range, d2_range, d3_range]
neighbor_slice
}

# Given a three-dimensional array cube, returns the elements that comprise the
# 'shell' of that array, that is, the elements on the outer edges of the array
# in all dimensions. Elements along the interface between the dimensions are
# included multiple times.
get_shell <- function(cube) {
d <- dim(cube)
d1_edge_cells <- cube[c(1, d[1]), ,  ]
d2_edge_cells <- cube[ , c(1, d[2]), ]
d3_edge_cells <- cube[ , , c(1, d[3])]
c(d1_edge_cells, d2_edge_cells, d3_edge_cells)
}

# Given a single numeric index to a three-dimensional array element index and
# the three-dimensional array cube, returns the value of that element after
# applying the rules for modifying an element per the puzzle instructions
next_cell_state <- function(index, cube) {
# Convert the single number index to an array index
arr_indices <- which(slice.index(cube, c(1, 2, 3)) == index, arr.ind = TRUE)

# Split the array index into d1, d2, and d3
d1 <- arr_indices[,1]; d2 <- arr_indices[,2]; d3 <- arr_indices[,3]
neighbors <- get_neighbors(d1, d2, d3, cube)  # Get neighbors
is_active <- cube[d1, d2, d3] == '#'          # Current cell is active?
active_neighbors <- sum(neighbors == '#')     # Count active numbers

# Apply the rules for changing the value of the index
if (is_active && active_neighbors %in% c(2, 3)) { return('#') }
if (!is_active && active_neighbors == 3) { return('#') }
return('.')
}

# Given a three-dimensional array cube, iterate through the array and return
# an array containing the next state of each element. If the 'shell' of the
# cube contains any '#', expands the cube one unit in each dimension before
# returning it.
next_cube_state <- function(cube) {

# Applies the next_cell_state() function to each element in the cube
next_cube <- future_apply(
slice.index(cube, c(1, 2, 3)),
c(1, 2, 3),
next_cell_state,
cube
)

# Expands the cube if any exterior element == '#'
if (any(get_shell(next_cube) == '#')) { next_cube <- grow_cube(next_cube) }
next_cube
}

new_cube <- initialize_cube(real_input)  # Start up the cube
next_cube <- grow_cube(new_cube)         # Expand one time for good measure
for (i in 1:6) {  next_cube <- next_cube_state(next_cube) }  # Six generations
answer1 <- sum(next_cube == '#')  # Count the '#''s

I kind of wish I had time to figure out how to animate this one, it should be neat to look at.

## Part Two - Tesseract

Three dimensions not enough for you, you say? Well then, do it again… in four dimensions! (evil laughter echoing) Actually, thanks to arrays, we don’t have to change much for part two, but the changes are sprinkled throughout our part one code. I’ll mark the changes with comments below.

# to speed up apply-type operations through the use of future_*apply functions.
library(future)
library(future.apply)
plan(multisession, workers = 6)

test_input <- c(
".#.",
"..#",
"###"
)

# Given a set of input lines representing a 'slice' of a 4d space input,
# returns a *four*-dimensional array containing that slice
initialize_hcube <- function(input) {
dim1 <- length(input)
dim2 <- nchar(input[[1]])
input_matrix <- matrix(unlist(strsplit(input, '')), dim1, dim2, TRUE)
new_hcube <- array('.', c(dim1, dim2, 1, 1))     # Extra dimension
new_hcube[1:dim1, 1:dim2, 1, 1] <- input_matrix  # Extra dimension
new_hcube
}

# Given a *four*-dimensional array hcube, expands the array by one index in all
# directions, filling the new spaces with the '.' character
grow_hcube <- function(hcube) {
d <- dim(hcube)
new_hcube <- array('.', d + 2)

new_hcube[seq(d[1])+1, seq(d[2])+1, seq(d[3])+1, seq(d[4])+1] <- hcube  # Changed
new_hcube
}

# Given the x, y, and z coordinates of an element in a *four*-dimensional array
# (d1, d2, d3, and d4, respectively) and the *four*-dimensional array hcube,
# returns a sub-array containing the elements immediately adjacent to the
# indicated coordinate in all dimensions. The central element, defined by the
# indicated coordinate, is replaced by an empty string.
get_neighbors <- function(d1, d2, d3, d4, hcube) {
d <- dim(hcube)
d1_range <- max(1, d1-1):min(d1+1, d[1])
d2_range <- max(1, d2-1):min(d2+1, d[2])
d3_range <- max(1, d3-1):min(d3+1, d[3])
d4_range <- max(1, d4-1):min(d4+1, d[4])  # Added fourth 'd'
hcube[d1, d2, d3, d4] <- ''               # Changed
neighbor_slice <- hcube[d1_range, d2_range, d3_range, d4_range]  # Changed
neighbor_slice
}

# Given a *four*-dimensional array hcube, returns the elements that comprise the
# 'shell' of that array, that is, the elements on the outer edges of the array
# in all dimensions. Elements along the interface between the dimensions are
# included multiple times.
get_shell <- function(hcube) {
d <- dim(hcube)
d1_edge_cells <- hcube[c(1, d[1]), , ,  ]
d2_edge_cells <- hcube[ , c(1, d[2]), , ]
d3_edge_cells <- hcube[ , , c(1, d[3]), ]
d4_edge_cells <- hcube[ , , , c(1, d[4])]  # Added fourth dimension edges
c(d1_edge_cells, d2_edge_cells, d3_edge_cells, d4_edge_cells)
}

# Given a single numeric index to a *four*-dimensional array element index and
# the *four*-dimensional array hcube, returns the value of that element after
# applying the rules for modifying an element per the puzzle instructions
next_cell_state <- function(index, hcube) {

# Multiple small changes to add the fourth dimension here
arr_indices <- which(slice.index(hcube, c(1, 2, 3, 4)) == index, arr.ind = TRUE)
d1 <- arr_indices[,1]; d2 <- arr_indices[,2]; d3 <- arr_indices[,3]; d4 <- arr_indices[,4]
neighbors <- get_neighbors(d1, d2, d3, d4, hcube)
is_active <- hcube[d1, d2, d3, d4] == '#'
active_neighbors <- sum(neighbors == '#')

if (is_active && active_neighbors %in% c(2, 3)) { return('#') }
if (!is_active && active_neighbors == 3) { return('#') }
return('.')
}

# Given a *four*-dimensional array hcube`, iterate through the array and return
# an array containing the next state of each element. If the 'shell' of the
# hcube contains any '#', expands the hcube one unit in each dimension before
# returning it.
next_hcube_state <- function(hcube) {
next_hcube <- future_apply(
slice.index(hcube, c(1, 2, 3, 4)),  # Added fourth dimension
c(1, 2, 3, 4),                      # Added fourth dimension
next_cell_state,
hcube
)
if (any(get_shell(next_hcube) == '#')) { next_hcube <- grow_hcube(next_hcube) }
next_hcube
}

new_hcube <- initialize_hcube(real_input)  # Start up the hcube
next_hcube <- grow_hcube(new_hcube)        # Expand one time for good measure
for (i in 1:6) {                           # Six generations
cat('\r', paste('Simulating hcube state:', i))
next_hcube <- next_hcube_state(next_hcube)
}
answer2 <- sum(next_hcube == '#')          # Count the '#''s

Neat.

## Wrap-Up

I liked this puzzle. Granted, I like playing with COGL, so that’s a given, but I don’t often find myself working with data beyond two dimensions (rows/columns), so the opportunity to explore higher order arrays in R was a good learning experience. As noted above, this is one I’d like to come back to and try my hand at visualizing.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!