An Implementation of Conway’s Game of Life Using Ramda and Functional JavaScript

I can recall the moment I deemed myself eligible to be a developer. I had written my own implementation of Conway’s Game of Life, and in doing so, had crossed a threshold. I reasoned then that programming was something I could do. I feel there are few motives so pure as coding an implementation of Life. I wonder if others do not view it as something of a rite of passage.

I find the game of Life useful as an exercise when attempting to learn a new language or library, and accordingly, I’ve coded variations on my initial implementation from years ago. Most recently, I sought to use Ramda, a functional library for JavaScript. In this article, I intend to unpack the results.

Let us begin with an overview. There are two factors that characterize the specific nature of our approach with the Game of Life:

1. Our step function, also commonly referred to as tick.This function evaluates as input only living cells. Here’s why: there is no reason to evaluate all cells on our grid — living or dead — when the full range of cells demanding evaluation reside within two cells of any living cell. Such is to say: any dead cell for which life might be possible will always be within two cells of some living cell. We can, therefore, accumulate all cells for evaluation by applying neighborhood to every cell returned by neighborhood for every living cell. To minimize redundancy, we’ll leverage Ramda’s uniq function, which serves to prune any overlap.
2. Rather than evaluate every cell against the sum of its neighbors, we will abstract and abide by the following rules:

• If the sum of all nine fields is three, the inner field state for the next generation will be life (regardless its previous contents).
• If the sum of all nine fields is four, the inner field retains its current state.
• Any other all-field sum stages the inner field for death.

Lastly, I will note that:

• Living cells shall be represented as an array of x and y coordinates, as with: [0, 1].
• The aggregate of all cells to evaluate shall be represented as an array of such cells, as with: [[0, 1], [0, 2], [0, 2]].

On the nature of our implementation, there are two functions that comprise the crux of our procedure, namely neighborhood and step. Ancillary functions requisite for seeding our algorithm and visualizing the output of our algorithm respectively include seed and paint.

To get warmed up, we will compose a function that returns the Moore neighborhood for any given cell.

𝒇: neighborhood():

Provided the coordinates for a cell, returns a list of the coordinates for all cells comprising the Moore neighborhood.

/**
 * Signature:
 * neighborhood :: [Number] -> [[Number]]
 */
function neighborhood([x = 0, y = 0] = []) {
  return reduce(
    (acc, dx) => concat(acc, map(dy => [dx, dy], range(y - 1, y + 2))),
    [],
    range(x - 1, x + 2)
  )
}

Let us advance, then, to the more difficult task of furnishing a step.

𝒇: step():

There is quite a bit happening here, so I’m going to unpack each of its components.

At the highest level, our function accepts as input an array of arrays, where each child array contains two numbers, denoting respective x and y coordinates. Hence, for arrIn, we expect something like:

[[51, 49], [50, 50], [51, 50], [52, 50], [52, 51]]

For output, our function applies calculations abstracted by Conway’s rules in Game of Life, and aggregates the next array of coordinates, for storage in variable arrOut. With arrOut, we will do two things: firstly, we’ll occasion a side effect to our function paint, and finally, we’ll pass such output into a recursive call to step, thus re-initializing the procedure.

Our use of Ramda’s reduce takes a total of three arguments, namely:

• A function, namely (acc, curr) => cond(...)
• An initial value for our accumulator, namely []
• A collection, which in this case is uniq(reduce(...))

In reverse:

For our purposes, we want to evaluate the Moore neighborhood for every incoming cell (i.e., arrIn), as we need to account for any cells that might undergo a transformation from dead to living. Accordingly, using reduce, we will apply neighborhood to each incoming cell, and we accumulate the result. We then wrap the new list effected by reduce with Ramda’s uniq, so as to discard any duplicate entries.

As arrOut will be a new array, we pass in an initial accumulator value of [].

Our function will leverage Ramda’s intersection and cond, so as to wax upon our empty list. We total the sum of all coordinates present in the neighborhood for each point that also appears in arrIn. We then pass this count via Array.prototype.length to cond, which, in turn, delegates the return value consumed by our outlying reduce. The rules used by cond are as follows:

• For a length totaling 3, add the current coordinate to our accumulator.
• For a length totaling 4, determine the current state of the coordinate in arrIn via contains; if living, include it with our accumulator; if dead, exclude its value by simply returning the current accumulator.
• In all other cases, return the accumulator.

function step(arrIn = []) {
  const arrOut = reduce(
    (acc, curr) =>
      cond([
        [equals(3), always([curr, ...acc])],
        [equals(4), () => (contains(curr, arrIn) ? [curr, ...acc] : acc)],
        [T, always(acc)],
      ])(intersection(neighborhood(curr), arrIn).length),
    [],
    uniq(reduce((acc, curr) => [...acc, ...neighborhood(curr)], [], arrIn))
  )
  paint(arrOut)
  return requestAnimationFrame(() => step(arrOut))
}

Using only neighborhood and step, we harness all of the calculations necessary for spawning proof of Life. It would be nice, however, were we to be able to render a visualization to the browser. Hence, paint.

𝒇: paint()

Our paint function is a little more imperative. It touches upon various APIs worthy of mention.

Most notably, we are using HTML5 canvas, which allows us to program graphics using JavaScript. We must use clearRect between each of our steps to erase previously-rendered content, else our living cells should otherwise persist. Finally, we use forEach to draw each of our cells, are we are occasioning side effects; were we returning a list, we, of course, would use some implementation of map.

/**
 * Signature:
 * paint :: ([[Number]], Number) -> Void
 */
function paint(arrIn = [], w = 8) {
  const context = document.getElementById('canvas').getContext('2d')
  context.clearRect(0, 0, 1512, 1512)
  return forEach(
    cell => context.fillRect(head(cell) * w, tail(cell) * w, 1 * w, 1 * w),
    arrIn
  )
}

Finally, we will want to seed our program with some data from which to start. Although I have written other functions in the past that can seed a grid at random, I much prefer usage of the following points, which succinctly convey considerable growth.

/**
 * Signature:
 * seed :: () -> [[Number]]
 */
function seed() {
  return [[51, 49], [50, 50], [51, 50], [52, 50], [52, 51]]
}

Our solution is certainly terse, at least for JavaScript¹. It is, unfortunately, awfully slow. By hand-crafting some of our own functions for uniq and intersection, however, we can dramatically accelerate execution of each step. Hence, we will use unique in lieu of Ramda’s unique, and intersectionLength in lieu of our combined usage of Array.prototype.length and Ramda’s intersection.

function unique(arr = []) {
  return last(
    reduce(
      (acc, val) =>
        head(acc).hasOwnProperty(val)
          ? acc,
          : [{...head(acc), [val]: true}, [...last(acc), val]],
      [{}, []],
      arr
    )
  )
}

function intersectionLength(arrOne = [], arrTwo = []) {
  return reduce(
    (acc, [x1, y1]) =>
      acc +
      reduce(
        (innerAcc, [x2, y2]) =>
          x1 === x2 && y1 === y2 ? inc(innerAcc) : innerAcc,
        0,
        arrTwo
      ),
    0,
    arrOne
  )
}

Here’s the final, optimized code, along with a visualization, on codepen.

Footnote:

---

Functional Programming JavaScript Languages Programming