conways-life.js

const { expect } = require('chai');

//
// Conway's Life, in modern javascript
//
// - Built with node 8, mocha, chai; uses modern javascript features
// - All data immutable
// - No classes or other pap.
//
// github.com/davidmfoley
//
// Each section below contains tests and implementation for one component
// They are sorted from "bottom" to "top", so the integration tests and
// implementation of conways life are at the end.
//
//

// =====================================================================================
// Finding neighbors
//
// In Conway's Life, and other cellular automata, the state of a cell in the next
// generation is derived in part from the number of alive neighbors... so we need to
// find them.
//
// In unbounded 2 dimensional space, each cell has eight neighbors.
//
// This implementation is unbounded, but this is not the only possible 2D implementation.
// One could choose to "wrap" around very large/small coordinate values,
// or enact hard boundaries and return fewer than 8 neighbors for the "edge" locations.
//
describe('findNeighbors2D', () => {
  it('returns neighbors', () => {
    const neighbors = findNeighbors2D([1,2]);
    expect(neighbors.sort()).to.eql([
      [0,1],
      [0,2],
      [0,3],
      [1,1],
      [1,3],
      [2,1],
      [2,2],
      [2,3],
    ]);
  });
});

const findNeighbors2D = ([x, y]) => [
  [x - 1, y - 1],
  [x - 1, y    ],
  [x - 1, y + 1],
  [x    , y - 1],
  [x    , y + 1],
  [x + 1, y - 1],
  [x + 1, y    ],
  [x + 1, y + 1],
];

//====================================================================
// Neighborhood
//
// for each generation of Conway's Life, we need to collect some state
// about each location that could possibly be alive in the next
// generation, so that we can decide its fate.
//
// a neighborhood is immutable and has two methods:
//
// - update(coordinates, state => nextState)
//    This returns a copy of the neighborhood with updated state for the 
//    given coordinates
//
// - filter(state => boolean)
//    This finds all locations that should live in the next generation,
//    based on the passed in function
//
describe('neighborhoods', () => {
  const defaultState = { alive: false, neighborCount: 0 };

  let neighborhood;
  beforeEach(() => neighborhood = createNeighborhood(defaultState));

  describe('updating cell state', () => {
    it('uses default state for new coordinate', () => {
      const updated = neighborhood.update([1,2], state => {
        expect(state.neighborCount).to.eq(0);
        expect(state.alive).to.eq(false);
        return {alive: true, neighborCount: 0};
      });
    });

    it('does not mutate itself', () => {
      neighborhood.update([1,2], state => {
        return {alive: true, neighborCount: 0};
      });

      expect(neighborhood.filter(() => true)).to.eql([ ]);
    });

    it('returns a neighborhood with the updated state included', () => {
      const updated = neighborhood.update([1,2], state => ({
        alive: true, neighborCount: 0
      }));

      updated.update([1,2], state => {
        expect(state).to.eql({alive: true, neighborCount: 0});
      });
    });
  });

  describe('filtering locations', () => {
    it('initially has no locations', () => {
      expect(neighborhood.filter(() => true)).to.eql([]);
    });

    describe('with some cell states', () => {
      beforeEach(() => {
        neighborhood = neighborhood
          .update([1,1], () => ({fast: true}))
          .update([1,2], () => ({furious: true}))
          .update([2,1], () => ({fast: true, furious: true}))
      });

      it('can filter locations by state', () => {
        expect(neighborhood.filter(state => state.fast)).to.eql([
          [1,1],
          [2,1]
        ]);

        expect(neighborhood.filter(state => state.furious)).to.eql([
          [1,2],
          [2,1]
        ]);
      });
    });
  });
});

// to support non-array coordinates,this would need to change
const getHashKey = (coordinates) => coordinates.join(':');

const createNeighborhood = (defaultState, locations = {}) => ({
  // return a new neighborhood with updated state at a single location
  // coordinates are specified as an array
  // transform is a function taking existing state and returning new state
  // if no state exists for the passed location, transform gets the default state
  update: (coordinates, transform) => {
    const key = getHashKey(coordinates);
    const location = locations[key] || { state: defaultState, coordinates };
    const updatedLocations = Object.assign({}, locations, {
      [key]: { state: transform(location.state), coordinates}
    });

    return createNeighborhood(defaultState, updatedLocations);
  },

  // return an array of coordinates whose associated state matches a predicate
  filter: predicate => Object.values(locations)
    .filter(location => predicate(location.state))
    .map(location => location.coordinates)
});

// =======================================================================
// Cellular Automaton
//
// "cellular automaton" is the generic name for systems like conway's life
// most well-known cellular automata operate on 2D coordinate systems
// this implementation is agnostic of the coordinate system
//
describe('cellular automata', () => {
  describe('in an uninhabitable world', () => {
    it('all dies', () => {
      const everyoneDies = () => false;
      const uninhabitable = createCellularAutomaton(findNeighbors2D, everyoneDies);
      expect(uninhabitable([[1,2],[1,1],[1,3]])).to.eql([]);
    });
  });

  describe('in a static world', () => {
    it('remains static', () => {
      const nothingEverChanges = state => state.alive;
      const staticWorld = createCellularAutomaton(findNeighbors2D, nothingEverChanges);
      const aliveLocations = [ [0,1], [1,1], [2,1] ];
      expect(staticWorld(aliveLocations)).to.eql(aliveLocations);
    });
  });

  describe('in a one-dimensional world', () => {
    it('works', () => {
      const findNeighbors1D = ([x]) => ([[x - 1], [x + 1]]);
      const aliveIfOneNeighbor = state => state.neighborCount === 1;
      const oneDimensionalWorld = createCellularAutomaton(findNeighbors1D, aliveIfOneNeighbor);
      const aliveLocations = [ [0], [2] ];
      expect(oneDimensionalWorld(aliveLocations).sort()).to.eql([[-1], [3]]);
    });
  });

  describe('in an eastward-growing world', () => {
    it('grows', () => {
      const eastNeighborOnly = coordinate => [
        [coordinate[0] + 1, coordinate[1] ]
      ];

      const allNeighborsLive = () => true;
      const eastward = createCellularAutomaton(eastNeighborOnly, allNeighborsLive);
      const result = eastward([ [1,1] ]);

      expect(result).to.eql([
        [1,1], [2,1]
      ]);

      expect(eastward(result)).to.eql([
        [1,1], [2,1], [3,1]
      ]);
    });
  });
});

const defaultState = {
  alive: false,
  neighborCount: 0
};

const emptyNeighborhood = createNeighborhood(defaultState);

// the transformations we make to neighborhoods
const setAlive = ({neighborCount})  => ({alive: true, neighborCount});
const incrementNeighborCount = ({alive, neighborCount})  => ({alive, neighborCount: neighborCount + 1});
const incrementNeighborCounts = (neighborhood, neighborCoordinates) => neighborhood.update(neighborCoordinates, incrementNeighborCount);

const createCellularAutomaton = (findNeighbors, shouldBeAlive) => {
  const updateNeighborhoodForLocation = (neighborhood, coordinates) => (
    findNeighbors(coordinates).reduce(
      incrementNeighborCounts,
      neighborhood.update(coordinates, setAlive)
    )
  );

  const populateNeighborhood = aliveCellLocations => aliveCellLocations.reduce(
    updateNeighborhoodForLocation,
    emptyNeighborhood
  );

  return aliveCellLocations => populateNeighborhood(aliveCellLocations).filter(shouldBeAlive);
}

// =====================================================
// Conway's Life
//
// Now that we can create a generic cellular automaton,
// make sure that it actually works for Conway's Life
//
describe(`Conway's Life `, () => {
  it('handles a box', () => {
    const box = [
      [2,3],
      [2,4],
      [3,3],
      [3,4],
    ];
    expect(conwaysLife(box)).to.eql(box);
  });

  it('handles a three element line', () => {
    const line = [
      [1,3],
      [1,4],
      [1,5],
    ];
    expect(conwaysLife(line).sort()).to.eql([
      [0,4],
      [1,4],
      [2,4],
    ]);
  });
});

// the basic rule for conway's life:
// alive cell with 2 or 3 neighbors lives, dead cell with 3 neighbors comes to life
const conwaysLifeShouldBeAlive = ({alive, neighborCount})  => (alive && neighborCount === 2) || neighborCount === 3;

// conway's life cellular automaton function
const conwaysLife = createCellularAutomaton(findNeighbors2D, conwaysLifeShouldBeAlive);