Messing around with the Game of Life in Coffeescript. I don't know what I'm doing.

conways_game_of_life.coffee

Dystopia =
  expands: (world) -> []
  lives: (cell) -> false

Utopia =
  expands: (world) -> world
  lives: (cell) -> true

evolve_world = (world, rules=Dystopia) ->
  rules.expands(world).filter (cell) -> rules.lives(cell)

describe "toBe and toEqual", ->
  it "toBe means same", ->
    expect([]).not.toBe([])
    empty = []
    expect(empty).toBe(empty)

  it "toEqual means equal", ->
    expect([]).toEqual([])

describe "Evolve world based on rules", ->
  it "nothing to evolve", ->
    expect(evolve_world([])).toEqual([])

  describe "one cell to evolve", ->
    it "dies", ->
      cell = {}
      rules =
        expands: (world) -> world
        lives: (cell) -> false
      expect(evolve_world([cell], rules)).toEqual([])

    it "lives", ->
      cell = {}
      rules =
        expands: (world) -> world
        lives: (cell) -> true
      expect(evolve_world([cell], rules)).toEqual([cell])

  describe "cells outside the universe can be born", ->
    it "breathes life into new cells", ->
      world = [{ name: "Nobody" }, { name: "Also nobody" }, { name: "Totally nobody" }]
      will_be_born = { name: "I will be born" }

      rules =
        expands: (world) -> world.concat([will_be_born])
        lives: (cell) -> cell == will_be_born

      expect(evolve_world(world, rules)).toEqual([will_be_born])

_ = require("lodash")

describe "Learn underscore", ->
  describe "reduce", ->
    it "using OO style", ->
      # The extra parentheses around the iterator makes that part clearer
      # to the interpreter. Perhaps assign the function to a variable?
      copy = _.reduce([-1,0,1], ((sum, x) -> sum.concat([x])), [])
      expect(copy).toEqual([-1,0,1]) 

    it "using functional style", ->
      concatenate = (sum, x) -> sum.concat([x])
      copy = _([-1,0,1]).reduce((concatenate), [])
      expect(copy).toEqual([-1,0,1]) 

  describe "range", ->
    it "excludes the end point!!", ->
      expect(_.range(-1, 1)).not.toEqual([-1,0,1])
      expect(_.range(-1, 1)).toEqual([-1,0])
      expect(_.range(-1, 2)).toEqual([-1,0,1])

  describe "intersection", ->
    it "should work", ->
      expect(_.intersection([1,2,3], [2,3])).toEqual([2,3])


# Reuse me, motherfucker!
# I'm waiting on https://github.com/jashkenas/underscore/pull/1367 to implement this for me.
intersectionOfObjects = (arrayA, arrayB, yourVeryOwnEquals = _.isEqual) -> 
  _.filter(arrayA, (needleElement) -> _.any(arrayB, (haystackElement) -> yourVeryOwnEquals(needleElement, haystackElement)))

# Move me into jasmine?
expectSetToIncludeSubset = (set, subset) ->
  expect(_.any(set, (x) -> _.isEqual(x, y))) for y in subset

CartesianR2 =
  crossProduct: (a, b) ->
    product = []
    for x in a
      for y in b
        product.push(CartesianR2.point(x, y))
    return product

  boundsOfRectangleContaining: (points) ->
    xs = _.pluck(points, "x")
    ys = _.pluck(points, "y")
    return { 
      bottomLeft: CartesianR2.point(_.min(xs), _.min(ys)),
      topRight: CartesianR2.point(_.max(xs), _.max(ys))
    }

  expands: (world) -> 
    return [] if world.length == 0
    bounds = CartesianR2.boundsOfRectangleContaining(world)
    return CartesianR2.crossProduct(
      _.range(bounds.bottomLeft.x - 1, bounds.topRight.x + 2)
      _.range(bounds.bottomLeft.y - 1, bounds.topRight.y + 2)
    )
      
  point: (x, y) -> { x: x, y: y }

describe "cross product", ->
  crossProductInR2 = (a, b) ->
    sum = []
    for x in a
      for y in b
        sum.push(CartesianR2.point(x,y))
    return sum

  it "works", ->
    expect(crossProductInR2([-1,0,1], [-1,0,1])).toEqual([CartesianR2.point(-1,-1), CartesianR2.point(-1,0), CartesianR2.point(-1,1), CartesianR2.point(0,-1), CartesianR2.point(0,0), CartesianR2.point(0,1), CartesianR2.point(1,-1), CartesianR2.point(1,0), CartesianR2.point(1,1)])

describe "2D Cartesian topology", ->
  describe "equality of points", ->
    it "should compare coordinates", ->
      expect(CartesianR2.point(0, 0)).toEqual(CartesianR2.point(0, 0))
      expect(CartesianR2.point(0, 0)).not.toEqual(CartesianR2.point(1, 0))
      expect(CartesianR2.point(0, 0)).not.toEqual(CartesianR2.point(0, 1))

  describe "intersection of points", ->
    it "doesn't handle objects", ->
      intersection = _.intersection([
        CartesianR2.point(0, 0),
        CartesianR2.point(1, 0),
        CartesianR2.point(0, 1),
        CartesianR2.point(1, 1)
      ], [
        CartesianR2.point(0, 0),
        CartesianR2.point(1, 1)
      ])

      # Sadly...
      expect(intersection).not.toEqual([
        CartesianR2.point(0, 0),
        CartesianR2.point(1, 1)
      ])
      # Because _.intersection() uses == instead of deep equals
      expect(intersection).toEqual([])

  describe "expands to at most 1 unit in all directions and dimensions past the most distant living cell", ->
    expands = CartesianR2.expands
    point = CartesianR2.point
    crossProduct = CartesianR2.crossProduct

    it "handles the empty universe", ->
      expect(CartesianR2.expands([])).toEqual([])

    it "expands for a single cell at the origin", ->
      expanded = CartesianR2.expands([CartesianR2.point(0, 0)])
      expected = CartesianR2.crossProduct([-1,0,1], [-1,0,1])
      expect(intersectionOfObjects(expected, expanded)).toEqual(expected)

    it "expands for a single cell not at the origin", ->
      expected = crossProduct([4,5,6], [7,8,9])
      expect(intersectionOfObjects(expands([point(5, 8)]), expected)).toEqual(expected)

    it "expands for two cells", ->
      expected = crossProduct(_.range(-15-1, (4+1)+1), _.range(-4-1, (10+1)+1))
      expanded = expands([point(-15, 10), point(4, -4)])
      expectSetToIncludeSubset(expanded, expected)

    it "expands for many cells", ->
      expected = crossProduct(_.range(-20-1, (9+1)+1), _.range(0-1, (22+1)+1))
      expanded = expands([point(-20, 20), point(-4, 0), point(9, 8), point(2, 12), point(-1, 22)])
      expectSetToIncludeSubset(expanded, expected)

    it "expands for two very-far-apart cells", ->
      expected = crossProduct(_.range(-50-1, (50+1)+1), _.range(-60-1, (60+1)+1))
      expanded = expands([point(-50, 60), point(50, -60)])
      expectSetToIncludeSubset(expanded, expected)

So I shouldn't use _.isEqual, but rather write it myself. Good to know. Thanks @jdalton for the tip.

Replacing _.isEqual with (a, b) -> (a.x is b.x && a.y is b.y) changed running time from 13 s to 100 ms. Thanks again, @jdalton.

Unfortunately, it's still pretty slow: the last test, using (-101..101) cross (-91..91) (37,149 elements), adds 30 seconds to the test run.

The bottleneck, so far, is the assertion expectSetToIncludeSubset(expanded, expected). I need something better.