Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement