percolationSpeedtest.js

class Percolation {
  constructor(UnionFind, SquareGrid) {}

  init(gridSize) {
    // init union-find
    this.uf = new UnionFind(gridSize ** 2 + 2);

    // init top virtual node
    let top = 0;
    for (let i = 1; i <= gridSize; i++) {
      this.uf.union(top, i);
    }

    // init bottom virtual node
    let bottom = gridSize ** 2 + 1;
    for (let i = 1; i <= gridSize; i++) {
      this.uf.union(bottom, bottom - i);
    }

    // init grid
    this.grid = new SquareGrid(gridSize);
  }

  open(row, col) {
    this.grid.setCell(row, col, 1);

    let adjacent = this.grid.getAdjacent(row, col);
    for (let cell of adjacent) {
      let [cellRow, cellCol] = cell;

      if (this.isOpen(...cell)) {
        this.uf.union(
          row * this.grid.size + col + 1,
          cellRow * this.grid.size + cellCol + 1
        );
      }
    }
  }

  isOpen(row, col) {
    return this.grid.getCell(row, col) === 1;
  }

  percolate() {
    return this.uf.connected(0, this.grid.size ** 2 + 1);
  }
}

class SquareGrid {
  constructor(size, canvasWidth, canvasHeight) {
    this.size = size;
    this.matrix = [...Array(size)].map(() => Array(size).fill(0));
  }

  getAdjacent(row, col) {
    let dir = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0]
    ];

    let adjacent = [];
    for (let d of dir) {
      let [dy, dx] = d;

      if (row + dy in this.matrix && col + dx in this.matrix[row + dy]) {
        adjacent.push([row + dy, col + dx]);
      }
    }
    return adjacent;
  }

  getRandom() {
    // returns [randRow, randCol]
    return [(Math.random() * this.size) | 0, (Math.random() * this.size) | 0];
  }

  setCell(row, col, value) {
    (this.matrix[row] || {})[col] = value;
  }

  getCell(row, col) {
    return (this.matrix[row] || {})[col];
  }

  traverse(fn) {
    for (let i = 0; i < this.matrix.length; i++) {
      for (let j = 0; j < this.matrix[0].length; j++) {
        fn(i, j);
      }
    }
  }
}

class UnionFind {
  constructor(n) {
    this.id = [...Array(n)].map((_, i) => i);
    this.sz = [...Array(n)].map(_ => 1);
  }

  _root(i) {
    while (i !== this.id[i]) i = this.id[i];
    return i;
  }

  union(j, k) {
    let jroot = this._root(j);
    let kroot = this._root(k);

    if (jroot === kroot) return;

    if (this.sz[jroot] > this.sz[kroot]) {
      this.id[kroot] = jroot;
      this.sz[jroot] += this.sz[kroot];
    } else {
      this.id[jroot] = kroot;
      this.sz[kroot] += this.sz[jroot];
    }
  }

  connected(k, m) {
    return this._root(k) === this._root(m);
  }
}

// speedtest logics
function run(gridSize) {

    // measures running time
    console.time('Percolated in')

    // injection is used for debugging
    percolation = new Percolation(UnionFind, SquareGrid);
    percolation.init(gridSize);

    // while it does not percolate keep opening new sites
    while(!percolation.percolate()) {
        percolation.open(...percolation.grid.getRandom());
    }
    console.timeEnd('Percolated in')
}

run(200)