Run results for: Find Island

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.125 Safari/537.36

Browser: Chrome 84

Operating system: Mac OS X 10.15.5

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
num1	214587.9 Ops/sec
num2	129832.3 Ops/sec

Tests:

num1
const L = true; const W = false; const world = [ [L, W, L, W, L, L], [L, L, L, W, L, W], [L, W, W, W, L, L], [W, W, W, W, W, L], [W, L, L, L, W, L], [W, W, W, W, W, L], [W, W, W, W, L, L], [W, W, W, W, L, L], ]; const height = world.length; const width = world[0].length; // Each island gets a number 1 or more. // Some islands are the same number. const idMap = {}; const idCounts = {}; const totalCounts = {}; let maxIslandId = 0; function newId() { const id = ++maxIslandId; idMap[id] = id; idCounts[id] = 0; totalCounts[id] = 0; return id; } const cellIdMap = Array.from(new Array(height), () => new Array(width).fill(0)); function getIdOfCell(y, x) { if (y < 0 || x < 0) return 0; return cellIdMap[y][x]; } // Assign Ids to the grid. for (let y = 0; y < height; ++y) { for (let x = 0; x < width; ++x) { if (world[y][x] === W) continue; const topId = getIdOfCell(y - 1, x); const leftId = getIdOfCell(y, x - 1); if (topId && leftId && topId !== leftId) { // Two islands become one. Left wins. idMap[topId] = leftId; } const id = leftId || topId || newId(); cellIdMap[y][x] = id; // Count island. ++idCounts[id]; } } const finalIdMemo = {}; function getMappedId(id) { if (id in finalIdMemo) { return finalIdMemo[id]; } let mappedId = id; while (mappedId !== idMap[mappedId]) { mappedId = idMap[mappedId]; } const finalId = mappedId; // Store the mapping result for faster // future calculation. mappedId = id; do { finalIdMemo[mappedId] = finalId; mappedId = idMap[mappedId]; } while (mappedId !== idMap[mappedId]); return finalId; } // Total island counts for (const id in idCounts) { totalCounts[getMappedId(id)] += idCounts[id]; }
num2
const L = true; const W = false; const world = [ [L, W, L, W, L, L], [L, L, L, W, L, W], [L, W, W, W, L, L], [W, W, W, W, W, L], [W, L, L, L, W, L], [W, W, W, W, W, L], [W, W, W, W, L, L], [W, W, W, W, L, L], ]; const height = world.length; const width = world[0].length; const visitedSet = new Set(); let largestIsland = []; let currentIsland = []; function traverseIsland(world, x, y) { var _a, _b, _c, _d; const toVisitStack = [[x, y]]; const currentIsland = []; while (toVisitStack.length) { const [currentX, currentY] = toVisitStack.shift(); currentIsland.push([currentX, currentY]); if (currentX === 0 || currentY === 0 || currentY === width - 1 || currentX === height - 1) { return []; } if (!visitedSet.has(`${currentX},${currentY + 1}`) && ((_a = world === null || world === void 0 ? void 0 : world[currentX]) === null || _a === void 0 ? void 0 : _a[currentY + 1])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX},${currentY - 1}`) && ((_b = world === null || world === void 0 ? void 0 : world[currentX]) === null || _b === void 0 ? void 0 : _b[currentY - 1])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX + 1},${currentY}`) && ((_c = world === null || world === void 0 ? void 0 : world[currentX + 1]) === null || _c === void 0 ? void 0 : _c[currentY])) { toVisitStack.push([currentX, currentY + 1]); } if (!visitedSet.has(`${currentX - 1},${currentY}`) && ((_d = world === null || world === void 0 ? void 0 : world[currentX - 1]) === null || _d === void 0 ? void 0 : _d[currentY])) { toVisitStack.push([currentX, currentY + 1]); } visitedSet.add(`${currentX},${currentY + 1}`); visitedSet.add(`${currentX},${currentY - 1}`); visitedSet.add(`${currentX + 1},${currentY}`); visitedSet.add(`${currentX - 1},${currentY}`); } return currentIsland; } for (let x = 1; x < height - 1; x++) { for (let y = 1; y < width - 1; y++) { const hasVisited = visitedSet.has(`${x},${y}`); visitedSet.add(`${x},${y}`); if (!hasVisited) { if (world[x][y]) { const currentIsland = traverseIsland(world, x, y); if (currentIsland.length > largestIsland.length) { largestIsland = currentIsland; } } } } }

Run results for: Find Island

num1

num2