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.

# The future/future.apply packages provide access to multiple R worker processes
# 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(
  ".#.",
  "..#",
  "###"
)
real_input <- readLines('input.txt')

# 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.

# The future/future.apply packages provide access to multiple R worker processes
# 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(
  ".#.",
  "..#",
  "###"
)
real_input <- readLines('input.txt')

# 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!

comments powered by Disqus