John Conway passed away this weekend as a result of complications from COVID-19. I think the first time I heard of his Game of Life was in high school when one of my teachers had us reading Stephen Hawking and Leonard Mlodinow’s The Grand Design, which used the game to illustrate some deep thoughts about the universe. Of course, our “states” in real life are (ever so slightly) more complex than to be determined by the binary number of “Alive” or “Dead” cells that surround us, but Hawking and Mlodinow make two arguments with the game. First, for a large range of possible starting “states,” the universe would have been unable to sustain life. This is similar to the fine-tuned universe argument. Second, the game raises the possibility of the existence of immutable laws that govern the universe. I’ve been thinking a lot about this in reflection to the purpose of social science (and mathematical modeling and estimation), but that will have to be left for a different post (more likely never expanded upon here). Conway’s own game of life has ended, but his brilliant insights will live on. May he rest in peace.

What better way to honor his memory (perhaps besides this lovely XKCD comic) than for a puzzle in his honor? The Riddler Classic from this weekend is an homage to Conway, and my friend Ricky Martinez and I tackled it together in R. I’d also love to give a special shoutout to Dan Adajian—who despite not working with us throughout, helped us get unstuck at a particular point. We found the answer, and we also found a wonderfully challenging problem which we tried to generalize a bit further with less success (though perhaps stay tuned to an updated version of this post!) and a greater appreciation for John Conway. As a quick side-note, we used Microsoft’s Visual Studio to collaborate—something we had never done before—and it worked quite effectively. No more screen sharing needed!

Here’s the text of the problem in full:

Riddler Nation was deeply saddened to hear of the loss of John Conway last week. It is only fitting that this week’s Classic is a spin on Conway’s Game of Life.

In the most common version of the game, there is an infinite grid of square cells, which are initially either alive or dead. Each square has eight neighbors — the eight squares that surround it. And after every step in time, or “tick,” all the cells are simultaneously updated according to the following rules:

A living cell with two or three living neighbors remains living. A living cell with any other number of living neighbors dies (due to under- or overpopulation). A dead cell with exactly three living neighbors comes alive (due to reproduction). These relatively simple rules lead to some startlingly complex, emergent behaviors. For example, some formations of living cells are known as “oscillators,” which change form from one tick to the next, ultimately returning back to their original formation.

Now suppose we were to replace the infinite grid with a finite grid that has periodic boundary conditions, so that cells in the first row are neighbors with cells in the last row, and cells in the first column are neighbors with cells in the last column. If there are three rows and N columns, what is the smallest value of N that can support an oscillator?

The answer is 4. Where 1 represents alive cells and 0 represents dead cells, the following is a pattern will sustain an oscillator:

We found the answer by simulating the problem, which proved to be particularly tricky. It’s computationally expensive to increase $N$, but maybe someone with a better computer can edit our code (which in and of itself is very messy!). For the rest of the post, I walk through our logic. Any notes on improving computational efficiency in this or generalizability would be appreciated.

library(rlist)
library(arrangements)
library(plyr)

First, we load in three required packages, rlist, arrangements, and plyr. The first makes working with lists easier in R, the second helps us create permutations, and the third lets us remove NULL elements from lists in a simple manner.

next_tick <- function(state) {
  cell_deltas <- list(c(-1,-1), c(-1, 0), c(-1, 1), c(0, -1), c(0, 1), c(1, -1), c(1, 0), c(1, 1))
  old_state <- state
  for (i in 1:nrow(state)) {
    for (j in 1:ncol(state)) {    
      cell_state <- old_state[i, j]
      living_neighbors <- 0
      for (delta in 1:length(cell_deltas)) {
        old_i <- i + cell_deltas[[delta]][1]
        old_j <- j + cell_deltas[[delta]][2]
        if (old_i == 0) {
          old_i <- nrow(state)
        }
        if (old_j == 0) {
          old_j <- ncol(state)
        }
        if (old_i == nrow(state)+1) {
          old_i <- 1
        }
        if (old_j == ncol(state)+1) {
          old_j <- 1
        }
        if (old_state[old_i,old_j] == "Alive") {
          living_neighbors <- living_neighbors + 1
        }
      }
      if (living_neighbors == 3 | (cell_state == "Alive" & living_neighbors == 2)) {
        state[i, j] <- "Alive"
      } else {
        state[i, j] <- "Dead"
      }
    }
  }
  return(state)
}

Next, we write a function, next_tick that will take a starting matrix as an input, and apply Conway’s rules once. The periodic boundary conditions stumped us for a while, which we got around by creating a list of the different neighbors of each cell, cell_deltas. For each cell (row = $i$, column = $j$) in the original matrix, the function finds its eight neighbors and sees how many are alive, which is sufficient to apply Conway’s rules. If the number of living neighbors is exactly equal to three, then the cell will be alive, regardless of what its original state was. If the cell was initially alive and its number of living neighbors is two, then it will stay alive. Otherwise, the cell will die.

candidate <- function(starting_state, MAX) {
  temp_statelist <- list(starting_state)
  for (i in 2:MAX) {
    temp_statelist[[i]] <- next_tick(temp_statelist[[i-1]])
  }
  if (!identical(temp_statelist[[MAX-1]], temp_statelist[[MAX]])) {
    return(temp_statelist)
  }
}

The next function candidate evaluates the starting arrangement of cells by attempting to find good candidates for oscillators. Given a particular starting arrangement, it runs next_tick until a specified MAX value. If the last two ticks are not identical, then we have a candidate for an oscillator. Some human checking is necessary as unfortunately—and it’s impossible to set MAX to infinity, but above a certain value, we can be reasonably confident that we’ve found an oscillator. This function will return the whole list through MAX, so it would be interesting to determine a pattern as to when the arrangement first started oscillating. Some folks, like Michael S. Branicky here have generalized patterns for $N$-period oscillators.

rows <- 3
columns <- 4
perms <- permutations(k = rows*columns, v = c("Alive", "Dead"), replace = TRUE)
all_starts <- list()
matrix_perms <- for (i in 1:nrow(perms)) {
  all_starts[[i]] <- matrix(perms[i,], nrow = rows, ncol = columns)
}

results <- lapply(1:length(all_starts), function(perm) candidate(all_starts[[perm]], 10))

results <- compact(results)

Now we can finally find our answer! For a given number of rows and columns, we can work through every possible permutation of starting arrangements. The number of possibilities is the $2^{\text{rows } \times \text{ columns}}$, where $\text{rows}$ is the number of rows and $\text{columns}$ is the number of columns, so this blows up really quickly! Nonetheless, we can run this for three rows and four columns to confirm our answer of interest. The results object will return results for all of these possible permutations, but starting arrangements without oscillators will be NULL, so we can easily use the compact function to reduce the numbers down. Out of the 4,096 possible starting combinations for a $3 \times 4$ matrix, I found 76 starting arrangements that lead to an oscillator at ticks 9 and 10. Neat! What’s interesting is that I imagine as the matrix gets larger, it will take longer for a starting arrangement to reach an oscillating pattern. Since both increasing MAX and increasing the number of possible permutations make this all run much more slowly, it’s tough to tell where the answers lie in for larger matrices.

Thank you to John Conway and Zach Wissner-Gross for a wonderful weekend puzzle! And to say good-bye, here’s an animation of an oscillator for three rows and four columns, made with gganimate—if you squint a bit, it does look like it’s waving at you.