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 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:
- Our
step
function, also commonly referred to astick
.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 applyingneighborhood
to every cell returned byneighborhood
for every living cell. To minimize redundancy, we’ll leverage Ramda’suniq
function, which serves to prune any overlap. - 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, 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
totaling3
, add the current coordinate to our accumulator. - For a
length
totaling4
, determine the current state of the coordinate inarrIn
viacontains
; 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^{1}. 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.
And check out what the rest of the engineering team has shared.
Through our blog, we learn in public.
Footnote:
- One of the more remarkable implementations of Life that I’ve uncovered is written in Clojure, and may be found here. There is also a one line implementation written in APL, but I find it entirely unreadable. ā†©