Number of Islands [Interesting Idea - WIP] Update all pointers

carry_pointer.js

let toggleLog = false;
 toggleLog = true;
let log = false;
// log = true;

const parents = {};
let numKeys = 0;

class UnionSet {
    // End result: At each cell, check adjacent, if it's visited, set parent to it's parent
    constructor (grid) {
        this.nodes = {};
        // this.tree = {};
        this.grid = grid;
        
        this.rows = grid.length;
        this.cols = grid[0].length;
        
        this.islands = 0;
        
        grid.forEach((gridRow, row) => {
            gridRow.forEach((elem, col) => {
                // Only "add" if it is a valid element
                if (toggleLog && row === 3 && col === 1) log = true;
                if (log && elem === "1") console.log('-', row, ',', col);
                if (elem === "1") this.add(row, col);
                // if (elem === "1") console.log('after adding', JSON.stringify(this.nodes))
            });
        });
    }
    
    get numIslands () {
        return this.islands;
    }
    
    get length () {
        return Object.keys(this.nodes).length;
    }
    
    add (row, col) {
        const key = this.key(row, col);
        const node = {};
        this.nodes[key] = node;
        
        this.islands++; // Increment this by default, decrement when joining
        
        // TODO [optimize]: Generalize this with below
        // Initialize the parent pointer scheme on first node
        // Don't check adjacents
        if (this.length === 1) {
            // TODO modify {node : key} to just key, will not have to change it explicitly
            const parent = { pointer: { node: key } }; // Initially, it should point to itself
            node.parent = parent;
            parents[key] = true;
            numKeys++;
            return true;
        }
        
        const adjRows = [1, 0, -1, 0];
        const adjCols = [0, 1, 0, -1];
        
        let joined = false;
        
                    if (log) this.logParentKeys();
        
        for (let i = 0; i < 4; i++) {
            const adjRow = adjRows[i] + row;
            const adjCol = adjCols[i] + col;
            
            if (adjRow >= 0 && adjRow < this.rows && adjCol >= 0 && adjCol < this.cols) {
                const adjKey = this.key(adjRow, adjCol);
                const adjNode = this.nodes[adjKey];
                if (log && adjNode) console.log(' ! adjExists', adjKey, adjNode.parent);
                if (adjNode) joined = this.join(adjNode, node);
                if (joined) {
                    joined = false;
                    numKeys--;
                    this.logParentKeys();
                    console.log('after removing keys', numKeys);
                    console.log('node', node, key);
                    console.log('adjNode', adjNode, adjKey);
                    if (log) this.logParentKeys();
                }
                if (log && adjNode) console.log(' == join result', node.parent, adjNode.parent);
                // No adjNode means it hasn't been visited yet, or was 0
            }
        }
        
        // If there were no joins
        if (!node.parent) {
            const parent = { pointer: { node: key } }; // Initially, it should point to itself
            parent[key] = true;
            node.parent = parent;
            numKeys++;
            parents[key] = true;
            return true;
        }
        
        
    }
    
    logParentKeys () {
        
        console.log('logging parent keys');
        const keys = Object.values(this.nodes).map(node => {
            return node.parent && node.parent.pointer.node || null;
        }).filter(val => val != null);
        
        console.log((new Set(keys)).size, new Set(keys));
    }
    
    // lNode will always exist, since this function isn't entered without it
    // rNode will at least be a new node
    join (lNode, rNode) {
        if (log) console.log('joining', lNode);
        if (log) console.log(' + with', rNode);
        
        // Assume left node will always have a pointer since it's previously visited
        // Set all child parentPointers to the same one as the parent
        
        // If it's a new node, just attach to adjacent
        if (!rNode.parent) { 
            // If we did this for non-new nodes, all the children nodes'
            // parents wouldn't get updated, so we can only do this for new ones
            // Re-assigning the parent, would detatch the refernece.
            rNode.parent = lNode.parent;
            if (log) console.log(' -- new, numislands decreased', this.islands);
            
            this.islands--; // Joining, so decrease islands
            return false;
        }
        
        // If they share the same parent, do nothing
        if (log && rNode.parent.pointer.node === lNode.parent.pointer.node) console.log(' << already share same parent');
        if (rNode.parent.pointer === lNode.parent.pointer) return false;
        
        if (log) console.log(' -- merging', this.islands);
        console.log('removing key', rNode.parent.pointer);
        
        // - Always attach right to left
        // - Update the parent pointer of right to point to same node
        // - The reason we don't assign parent directly because the parent
        //   is a reference to an object, which is shared by it's children.
        // - If we update the pointer of that parent object, since all the 
        //   children share the same object, the pointer will now be equal
        //   for all children when we modify the parent's parent pointer.
        rNode.parent.pointer = lNode.parent.pointer;
        
        this.islands--; // Joining, since pointers are different
        return true;
    }
    
    key (row, col) {
        return `${row}-${col}`;
    }
}

var numIslands = function(grid) {
    if (grid.length === 0 || grid[0].length === 0) return 0;
    
    let unionSet = new UnionSet(grid);
    return unionSet.numIslands;
};

path_compress_and_union_find.js

class DJS {
    constructor (grid) {        
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.values = [];
        this.count = 0;
        
        this.parents = [];
        this.ranks = [];
        
        grid.forEach((rowVal, row) => {
            this.values.push([]);
            rowVal.forEach((value, col) => {
                let element = { value, rank: 0, parent: undefined };
                if (value === '1') {
                    element.parent = element;
                    this.count++;
                }
                this.values[row].push(element)
            });
        });
    }
    
    find (element) {
        if (element.parent !== element)
            element.parent = this.find(element.parent);
        return element.parent;  // do this if it's a "leader", aka it's own parent
    }
    
    union (firstNode, secondNode) {
        // Assume non flattened values
        let first = this.find(firstNode);
        let second = this.find(secondNode);
        
        // This return check is purely for keeping track of count to reduce another loop at the end
        if (first === second) return;
        this.count--;
        
        if (first.rank < second.rank) {
            first.parent = second;
        } else if (first.rank > second.rank) {
            second.parent = first;
        } else {
            first.parent = second;            
            second.rank++;
        }
        
    }
    
    isValidIndex (row, col) {
        if (row < 0 || col < 0 || row >= this.rows || col >= this.cols) return undefined;
        return this.values[row][col];
    }
    
    findIslands () {
        this.values.forEach((rowVal, row) => {
            rowVal.forEach((element, col) => {
                // can "optimize by keeping visited"
                if (element.value === '1') {
                    let up = this.isValidIndex(row - 1, col);
                    if (up && up.value === '1') this.union(element, up);
                    let down = this.isValidIndex(row + 1, col);
                    if (down && down.value === '1') this.union(element, down);
                    let left = this.isValidIndex(row, col -1);
                    if (left && left.value === '1') this.union(element, left);
                    let right = this.isValidIndex(row, col + 1);
                    if (right && right.value === '1') this.union(element, right);
                }
            })
        });
        
        return this.count;
    }
}


/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid || !grid[0]) return [];
    
    let djs = new DJS(grid);
    return djs.findIslands();
};

path_compression_only.js

class UnionSet {
    // End result: At each cell, check adjacent, if it's visited, set parent to it's parent
    constructor (grid) {
        this.nodes = {};
        this.grid = grid;
        
        this.rows = grid.length;
        this.cols = grid[0].length;
        
        this.islands = 0;
        
        grid.forEach((gridRow, row) => {
            gridRow.forEach((elem, col) => {
                // Only "add" if it is a valid element
                if (elem === "1") this.add(row, col);
            });
        });
    }
    
    get numIslands () {
        return this.islands;
    }
    
    add (row, col) {
        const key = this.key(row, col);
        const node = {};
        node.parent = node;
        this.nodes[key] = node;
        
        this.islands++; // Increment this by default, decrement when joining
        
        const adjRows = [1, 0, -1, 0];
        const adjCols = [0, 1, 0, -1];
        
        for (let i = 0; i < 4; i++) {
            const adjRow = adjRows[i] + row;
            const adjCol = adjCols[i] + col;
            
            if (adjRow >= 0 && adjRow < this.rows && adjCol >= 0 && adjCol < this.cols) {
                const adjKey = this.key(adjRow, adjCol);
                const adjNode = this.nodes[adjKey];
                if (adjNode) this.join(adjNode, node);
            }
        }
    }
    
    parent (node) {
        const isRoot = node.parent === node;
        if (isRoot) return node;
        
        node.parent = this.parent(node.parent);
        return node.parent;
    }
    
    join (fNode, rNode) {
        let lParent = this.parent(fNode);
        let rParent = this.parent(rNode);
        
        if (lParent === rParent) return null;
        
        rParent.parent = lParent;
        this.islands--;
    }
    
    key (row, col) {
        return `${row}-${col}`;
    }
}

var numIslands = function(grid) {
    if (grid.length === 0 || grid[0].length === 0) return 0;
    
    let unionSet = new UnionSet(grid);
    return unionSet.numIslands;
};