Conway’s Game of Life in JavaScript

Try out the demo: Matt Kenefick’s Game of Life

My solution is extremely experimental by design. It’s not intended to be your standard run-of-the-mill approach.

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input.

Yesterday, I read an article the other day about how someone approached the Game of Life problem. I didn’t know about the problem before seeing this article, but it appears to be something you’d likely see in a technical interview.

What intrigued me at first was how beautiful the grid was and the way it could take on a life of its own. It’s like a living breathing crossword puzzle.

I started to read about the problem itself, and then his implementation; that’s where it took a turn for me. At first, I thought it’d be fun to give this problem a shot within an hour to see how far I got.

After I saw his code, I had a different mission:

As you can see in Alex’s code, he’s using nested loops for his multidimensional arrays, lots of conditionals, and even throwing errors. Later he uses more loops and conditionals to execute the function above.

This might be how places expect you to solve it, but I don’t care for it.

Eliminating loops, conditionals, and errors

It was no longer about simply solving the problem itself, but about how I solved it. I wanted to come up with a way that didn’t depend on multi-dimensional arrays, additional loops, excessive conditionals, and errors.

Why?

For fun.

Okay, so what did I do?

First concession is that there must be one loop. Obviously since we’re potentially changing a list of items, we have to look at each one.

Second, I was determined to use a basic map where you have a: top-left, top -middle, top-right, middle-left, middle-right, bottom-left, bottom-middle, and bottom-right.

There are three main points of processing for this problem:

1. Recursively process N iterations in an X, Y grid
2. Calculate neighbor count of each item in the grid
3. Apply our rules for each item based on neighbor count

The focal point of all of this how we calculate how many neighbors each grid item has. Before we get into that, I’m going to briefly touch on points #1 and #3 to get them out of the way.

#1. Process

The main purpose of this function iterates through how many items we have. If the grid is meant to be 3x3, that means we have a total of 9 items to potentially process.

We run this function recursively so we can reach N number of iterations. The logic starts with a base set of data and then calls itself N times passing in the previous set of data each time.

We utilize a basic cache mechanism to store previously processed iterations to reduce unnecessary processing power. This is optional, but optimal.

#3. Determination

The main purpose of this function is to make a determination of what should happen to each item based on the rules of Life. Here are the rules:

In my implementation, I handle this very explicitly with conditionals. The reason I’m doing it this way is because these rules are pretty arbitrary and could be changed to do anything. If I were to go out of my way to identify a pattern in here, it would just make changes more complicated to implement.

Note: This part uses conditionals, but the neighbor count part does not; technically.

Determining neighbor count

For this application, a neighbor is anything adjacent to a particular index including diagonals; it’s very much like Minesweeper. Here’s an extremely basic starting position for Life.

Black indicates a dead item, white indicates a live item. The number inside represents how many live items said block is in contact with other than itself.

I wanted to solve this problem using a flat array, meaning:

[0, 1, 2, 3, 4, 5, 6, 7, 8]

As opposed to a multi-dimensional array, such as:

[
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8]
]

One of the problems that comes with a flat array is the idea of wrapping. I’ll explain that in a minute.

Basic approach for finding neighbors

The basic approach for finding neighbors is to add / subtract positions based off your current index. So let’s say we want the value for “4” in that array above.

The item left of it is 3, so that’s 4−1
The item right of it is 5, so that’s 4+1

To get the items above and below it, you simply have to remove an entire row. Since we have 3 items per row, we can say:

The item above it is 1, so that’s 4−3−0
The item above-left is 0, so that’s 4−3−1
The item above-right is 2, so that’s 4−3+1

Then you would do the same thing for beneath it by adding 3 items per row.

What about the corners?

Edges and corners are where this starts to get tricky and why you’d find people using conditionals.

If you’re at position 2, that’s the top right corner. You shouldn’t expect to find any data to the right of it, nor should you expect data above it. Same goes for anything on the top edge, left edge, right edge, or bottom edge.

What’s more is that this creates a particularly difficult problem for flat array mapping. We mentioned before that determining the place to the right is index + 1, but if you apply that logic to a flat array at position 2, you’ll end up with 3.

    [0, 1, 2, 3, 4, 5, 6, 7, 8]

    [0, 1, 2] x
    [3, 4, 5]
    [6, 7, 8]

As you can see, 3 is not next to 2 on the grid view, it’s middle left.

How do we adjust for this?

This is where it gets complicated. I’m also going to bring in this disclaimer here for the purists ☺️

Disclaimer: I’ve mentioned how I wanted to eliminate “conditionals”, but I must disclaim that there may be some behind-the-scenes conditionals at play here, e.g. min and max functions.

/**
 * Checks a key/val's neighbors to determine what
 * the next state should be. Returns how many living
 * neighbors exist for the supplied item.
 *
 * @param int index
 * @param array data
 * @return int
 */
getNeighborCount(index = 0, data) {
    data || (data = this.data);
    index = parseFloat(index);

    let output = 0;

    const x = this.board.columns;
    const y = this.board.rows;

    const a = Math.max(0, Math.floor((index - x) / x));
    const b = Math.floor(index / x);
    const c = Math.min(y - 1, Math.floor((index + x) / x));

    const grid = {
        [(a * x) + Math.abs(parseInt((index % x - 1).toString(36), x))]: 1,
        [(a * x) + parseInt((index % x - 0).toString(36), x)]: 1,
        [(a * x) + Math.min(x, parseInt((index % x + 1).toString(36), x))]: 1,

        [(b * x) + Math.abs(parseInt((index % x - 1).toString(36), x))]: 1,
        [(b * x) + Math.min(x, parseInt((index % x + 1).toString(36), x))]: 1,

        [(c * x) + Math.abs(parseInt((index % x - 1).toString(36), x))]: 1,
        [(c * x) + parseInt((index % x - 0).toString(36), x)]: 1,
        [(c * x) + Math.min(x, parseInt((index % x + 1).toString(36), x))]: 1,
    };

    output = Object
        .keys(grid)
        .filter(x => x >= 0 && x != index && data[x] === STATE_ALIVE)
        .length;

    return output;
}

As you can see, this grid map doesn’t use a bunch of complicated conditionals and loops to determine what’s next to it. It simply uses TL, TM, TR, ML, MR, BL, BM, and BR.

Variables a, b, and c are integers representing rows above, middle, under. They’re using max & min to clamp them within the bounds of the grid; but I should note this isn’t entirely necessary.

The four important aspects of this approach are:

1. Using Object keys
2. Modulo %
3. Math.abs
4. parseInt(…, base)

By using the Object keys, we are able to naturally overwrite indexes. If multiple calculations yield -2, that’s fine. As a matter of fact, it’s better that we don’t have to apply additional filters on it.

Modulo allows us to determine a remainder and it’s because of this that we can logically separate rows. Each row has 3 items, so for a list of items 6, 7, 8, it will look like:

6 % 3 = 0
7 % 3 = 1
8 % 3 = 2
9 % 3 = 0

You can see how those calculated values will be useful in determining each items position in the “column,” i. e. 6 % 3 = 0 meaning 0 index in a column.

Math.abs is a trick that allows us to deal with left-most edge specific cases. Above we talked about converting numbers using modulo to pseudo column indexes which is great, but what if want the item left of 6?

6 - 1 = 5; // no good
0 - 1 = -1; // off the grid

Using the -1 solution will either error us off the grid or calculate 5 by wrapping around the flat array; neither are what we want. If we wrap it in Math.abs(-1) it becomes simply 1 which is what we’d use for determining the item RIGHT ADJACENT, i.e. 7.

Since we’re using Object keys which will naturally be overwritten, the absolute value of -1 becoming 1 is essentially just throwing the value away because it’s already been determined by other calculations.

parseInt(…, base) is another trick that allows us to deal with right-most edge specific cases. It involves one of my favorite things ever: numerical bases. In other words, we’re leaving base-10.

For this, we’ll set the base to be how every many items exist in a row (3). Now ordinarily when you count something in base 3, it would look like:

0, 1, 2, 10, 11, 12, 20, 21, 22

But with parseInt() we will find that overflowing numbers are NaN, so here’s what you’ll get:

parseInt(0, 3) == 0
parseInt(1, 3) == 1
parseInt(2, 3) == 2
parseInt(3, 3) == NaN

🛑 Edit: I didn’t initially take into account double digit values and radix for this conversion, so it threw unexpected errors. For example:

parseInt(12, 19) == 21  // bad
parseInt('c', 19) == 12 // good
(12).toString(36) == 'c' // that's where it comes from

If we want to find what is right adjacent of our top right corner (x value below), we would be doing 2+1, but in a flat map that will give us 3. If we consider each row with bases, it would be parseInt(2 + 1, 3) which equals NaN. Since we’re using Object keys, that means we’ll be setting a key of NaN.

    [0, 1, 2] x
    [3, 4, 5]
    [6, 7, 8]

What does it all do?

Now if we process each row and apply that grid object to it, we’ll retrieve a result that looks like this:

Look at the keys: 1, 2, 4, 5, NaN then analyze those positions in the grid. They’re all neighbors (with self included).

Let’s look at the 9th position (bottom left). You can see how the only neighbors are 6, 7, 10 (with self included).

Now that we have that Object of keys, we can flip it and remove ourself from it. There are other ways of implementing this and it could also be optimized.

output = Object
    .keys(grid)
    .filter(x => x >= 0 && x != index && data[x] === STATE_ALIVE)
    .length;

We get the keys, then we check our indexes (keys), and determine if it’s an ALIVE value. The length of said array is how many living neighbors our index is in contact with.

Summary

Using the grid method above, we minimized the amount of conditionals, loops, and thrown errors required in order to reliably determine how many living neighbors a particular index has.

Is this the best approach? Maybe, maybe not.

Was it fun? Yes, and no.

The idea for changing bases came first as a solution for right-most edge cases but it didn’t fix left-most problems. If you put -1 into the parseInt function, it’ll return -1 regardless of what base you’re in. Applying modulo before entering it in would defeat the purpose.

It took like 20 minutes to come up with the Math.abs solution for left-most edge cases. I was worried that maybe I had hit a wall and my approach to solving it wasn’t doable.

I realize it’s not a conventional approach, but that was the point. I wanted to see if something like this could be done using nearly 100% arithmetic, one primary loop, and little-to-no conditionals/errors and it seems like the answer is yes; at least for JavaScript.

Try out the demo: Matt Kenefick’s Game of Life