Hashlife in Node.js using WeakMap and Set

cache.js

class Cache extends WeakMap {
  get (key) {
    // initialize to empty set
    if (!super.has(key)) {
      super.set(key, new Set())
    }

    return super.get(key)
  }
}

// cache factory for instance of universe
module.exports = function cache (Class, [dead]) {
  // weakly references canonical
  // nodes with quadrants as keys
  const caches = {
    nw: new Cache(),
    ne: new Cache(),
    sw: new Cache(),
    se: new Cache()
  }

  // takes 4 quadrants and returns canonicalized reference
  return function canoncial (Quadtree, dead, nw, ne, sw, se, level) {
    if (nw === dead && ne === dead && sw === dead && se === dead) {
      return dead
    }

    const quadrants = [
      this.nw.get(nw),
      this.ne.get(ne),
      this.sw.get(sw),
      this.se.get(se)
    ].sort((a, b) => a.size - b.size)

    const intersect = new Set(quadrants.shift())

    for (const candidate of intersect) {
      for (const quadrant of quadrants) {
        if (!quadrant.has(candidate)) {
          intersect.delete(candidate)
          break
        }
      }

      // existing canonicalized reference
      if (intersect.has(candidate)) {
        return candidate
      }
    }

    // create new canonicalized reference
    const node = new Quadtree(nw, ne, sw, se, level)

    for (const quadrant of quadrants) {
      quadrant.add(node)
    }

    return node
  }.bind(caches, Class, dead) // avoid scoped references
}

cell.js

module.exports = class Cell {
  constructor (value, level = 0) {
    this.value = value
    this.level = level
  }
}

index.js

const { readFileSync } = require('fs')
const parser = require('./parser')
// node . TetrisOTCAMP.mc
const { root } = parser(readFileSync(process.argv[2], 'utf8'))

// logs correct output
console.log(root.value)

console.log(root.padded.future.value)

parser.js

const universe = require('./universe')

// parses Golly macrocell file format
module.exports = function parser (pattern) {
  if (/^[1-3] /m.test(pattern)) {
    throw new Error('multi-state patterns not supported')
  }

  const lines = pattern.split(/[\r\n]+/g).filter(Boolean)
  const rulestring = lines.find(line => /^#R/.test(line)) || '#R S23/B3'
  const quadtrees = lines.filter(line => /^[\.\*\$\d]/.test(line))

  const { macrocell, cell: [dead, live] } = universe(rulestring.replace(/^#R/, ''))
  const leaf = Array.from({ length: 8 }, () => Array(8).fill(dead))
  const nodes = [dead]

  function create (level = 3, row = 0, column = 0) {
    const half = 2 ** (level - 1)

    if (half === 1) {
      return macrocell(
        leaf[row][column],
        leaf[row][column + half],
        leaf[row + half][column],
        leaf[row + half][column + half],
        level
      )
    }

    return macrocell(
      create(level - 1, row, column),
      create(level - 1, row, column + half),
      create(level - 1, row + half, column),
      create(level - 1, row + half, column + half),
      level
    )
  }

  for (const quadtree of quadtrees) {
    if (/^\d/.test(quadtree)) {
      const [match, level, nw, ne, sw, se] = quadtree.match(/^(\d+) (\d+) (\d+) (\d+) (\d+)$/)

      if (Math.max(nw, ne, sw, se) >= nodes.length) {
        throw new Error('malformed macrocell pattern')
      }

      // create and index macrocell
      nodes.push(macrocell(nodes[nw], nodes[ne], nodes[sw], nodes[se], Number(level)))
    } else {
      // reset leaf
      for (const row of leaf) {
        row.fill(dead)
      }

      // populate leaf
      for (let row = 0, column = 0, index = 0; index < quadtree.length; index++) {
        switch (quadtree[index]) {
        case '$':
          column = 0
          row++
          break
        case '*':
          leaf[row][column] = live
        case '.':
          column++
        }
      }

      // create and index leaf
      nodes.push(create())
    }
  }

  return { macrocell, cell: [dead, live], root: nodes.pop() }
}

quadtree.js

const Cell = require('./cell')
// should this just store caches as member properties?
// might be more efficient than using WeakMap
// but not sure if cyclical references prevent GC
module.exports = class Quadtree extends Cell {
  constructor (nw, ne, sw, se, level) {
    super(nw.value + ne.value + sw.value + se.value, level)

    this.nw = nw
    this.ne = ne
    this.sw = sw
    this.se = se
  }
}

universe.js

// plan to implement step logic myself eventually
// maybe using K-map boolean optimization?
const parse = require('cellular-automata-rule-parser')

const cache = require('./cache')
const Cell = require('./cell')
const Quadtree = require('./quadtree')

// factory for creating independent universe
module.exports = function universe (rulestring) {
  const rule = parse(rulestring)
  const step = rule.process.bind(rule)
  const dead = new Cell(0)
  const live = new Cell(1)
  const cell = [dead, live]

  // for optimization, allow dead cell to represent dead quadrant at any level
  Object.assign(dead, { future: dead, nw: dead, ne: dead, sw: dead, se: dead })

  // canonicalized quadtrees
  const macrocell = cache(class extends Quadtree {
    // please bear with me
    get future () {
      const { level, nw, ne, sw, se } = this

      let nwf, nef, swf, sef

      // note that level 0 and 1 cannot be reached
      if (level === 2) {
        // reduce 4x4 to 2x2 by 1 step in the future

        const { nwnw, nwne, nwsw, nwse } = {
          nwnw: nw.nw.value,
          nwne: nw.ne.value,
          nwsw: nw.sw.value,
          nwse: nw.se.value
        }

        const { nenw, nene, nesw, nese } = {
          nenw: ne.nw.value,
          nene: ne.ne.value,
          nesw: ne.sw.value,
          nese: ne.se.value
        }

        const { swnw, swne, swsw, swse } = {
          swnw: sw.nw.value,
          swne: sw.ne.value,
          swsw: sw.sw.value,
          swse: sw.se.value
        }

        const { senw, sene, sesw, sese } = {
          senw: se.nw.value,
          sene: se.ne.value,
          sesw: se.sw.value,
          sese: se.se.value
        }

        // cellular-automata-rule-parser returns 0 or 1
        // so map that to canonicalized dead or live cell respectively
        nwf = cell[step(nwse, [nwnw, nwne, nenw, nwsw, nesw, swnw, swne, senw])]
        nef = cell[step(nesw, [nwne, nenw, nene, nwse, nese, swne, senw, sene])]
        swf = cell[step(swne, [nwsw, nwse, nesw, swnw, senw, swsw, swse, sesw])]
        sef = cell[step(senw, [nwse, nesw, nese, swne, sene, swse, sesw, sese])]
      } else {
        // reduce 2^Nx2^N to 2^(N-1)x2^(N-1) by 2^(N-2) steps into the future

        const nnf = macrocell(nw.ne, ne.nw, nw.se, ne.sw, level - 1).future
        const wwf = macrocell(nw.sw, nw.se, sw.nw, sw.ne, level - 1).future
        const ccf = macrocell(nw.se, ne.sw, sw.ne, se.nw, level - 1).future
        const eef = macrocell(ne.sw, ne.se, se.nw, se.ne, level - 1).future
        const ssf = macrocell(sw.ne, se.nw, sw.se, se.sw, level - 1).future

        nwf = macrocell(nw.future, nnf, wwf, ccf, level - 1).future
        nef = macrocell(nnf, ne.future, ccf, eef, level - 1).future
        swf = macrocell(wwf, ccf, sw.future, ssf, level - 1).future
        sef = macrocell(ccf, eef, ssf, se.future, level - 1).future
      }

      const value = macrocell(nwf, nef, swf, sef, level - 1)

      // memoize property getter to property access
      // not sure how much this benefits performance
      Object.defineProperty(this, 'future', {
        value,
        configurable: true,
        writable: true
      })

      return value
    }

    get padded () {
      const { level } = this

      const nw = macrocell(dead, dead, dead, this.nw, level)
      const ne = macrocell(dead, dead, this.ne, dead, level)
      const sw = macrocell(dead, this.sw, dead, dead, level)
      const se = macrocell(this.se, dead, dead, dead, level)

      return macrocell(nw, ne, sw, se, level + 1)
    }
  }, cell)

  return { macrocell, cell }
}