Styjun

It is very similar to this Number of Islands JavaScript challenge https://codereview.stackexchange.com/questions/201530/count-number-of-islands-2d-grid.

Given two grids where each cell of the grids contains either a '0' or a '1'. If two cells share a side then they are adjacent. Cells that contain '1' form a connected region(or island as commonly called) if any cell of that region can be reached by moving through the adjacent cells that contain '1'. Overlay the first grid onto the second and if a region of the first grid completely matches a region of the second grid, the regions are matched. Count total number of such matched regions in the second grid

Here's an example:

Grid 1
0 0 1
0 1 1
1 0 0

Grid 2
0 0 1
0 1 1
1 0 1

Grid 1 forms two regions at point (0,2), (1,1), (1,2) and (2,0)

Grid 2 forms two regions at point (0, 2), (1,1),(1,2),(2,2) and (2,0)

Region (2,0) is the only matching region so the answer here is 1.

This below is what I have done. My function countMatches() returns the number of connected regions in each grid, but what I want is to compare any connected region in grid 1 with that of grid 2 and return the number of matches i.e number of exact connected regions present in both. This result will be a single integer.

Also here is a codepen link to it - https://codepen.io/Baystef/pen/OqBJzG

JavaScript
function countMatches(grid1, grid2) 
 let gridOne = grid1.filter(n => typeof(n) !== 'number');
 let gridTwo = grid2.filter(n => typeof(n) !== 'number');

 //this only gives number of connected region in each grid, but what i want to get is number of islands that match perfectly when the grids are overlayed.
 return `We have $countIslands(gridOne) island(s) in grid 1 and $countIslands(gridTwo) island(s) in grid 2`


function countIslands(grid) 
 let markIsland = function (grid, x, y, visited) ;

 let visited = [];

 for (let i = 0; i < grid.length; i++) 
 visited[i] = [];
 

 let count = 0;

 for (let x = 0; x < grid.length; x++) 
 for (let y = 0; y < grid[x].length; y++) 
 if (!visited[x][y] && grid[x][y] === '1') 
 count++;
 markIsland(grid, x, y, visited);
 
 visited[x][y] = true;
 
 

 return count;

Sample grid input:-

const grid1_1 = [
 4,
 ['0', '1', '0', '0'],
 ['1', '0', '0', '1'],
 ['0', '0', '1', '1'],
 ['0', '0', '1', '1']
]
const grid2_1 = [
 4,
 ['0', '1', '0', '1'],
 ['1', '0', '0', '1'],
 ['0', '0', '1', '1'],
 ['0', '0', '1', '1']
]

const grid1_2 = [
 3,
 ['0', '0', '1'],
 ['0', '1', '1'],
 ['1', '0', '0']
]
const grid2_2 = [
 3,
 ['0', '0', '1'],
 ['0', '1', '1'],
 ['1', '0', '1']
]

The first line of each grid contains an integer which is the size of the grid array i.e 4 means it's a 4 X 4 grid.

If I run the function countMatches(grid1_1, grid2_1) it should return 2.

Reason is grid1_1 has 3 connected regions(islands) which are positions (0,1) , (1,0) and (1,3),(2,2),(2,3),(3,2),(3,3)

grid2_1 also has 3 connected regions(islands) at positions (0,1), (1,0) and (0,3),(1,3),(2,2),(2,3),(3,2),(3,3)

Regions (0,1), (1,0) are the only two regions that exist in grid1_1 and grid2_1 exclusively and that's why the function should return 2.

You could get the count of islands first and then check the second array against the array with numbered islands.

This approach uses a simplified data set and an array with the length of the island count.

As result all truthy values of the matches array are counted and retuned.

Examples:

 a b congruent islands/matching areas
------- ------- --------------------------------
0 1 0 0 0 1 0 1
2 0 0 3 1 0 0 1
0 0 3 3 0 0 1 1
0 0 3 3 0 0 1 1 3/islands 1 2 3

0 1 0 2 0 1 0 0
3 0 0 2 1 0 0 1
0 0 2 2 0 0 1 1
0 0 2 2 0 0 1 1 2/islands 1 3

0 0 1 0 0 1
0 1 1 0 1 1
2 0 0 1 0 1 2/islands 1 2

0 0 1 0 0 1
0 1 1 0 1 1
2 0 1 1 0 0 1/islands 2

function getIslands(array) 

 function test(array, i, j, count) 
 if (array[i] && array[i][j] === -1) 
 array[i][j] = count;
 test(array, i - 1, j, count);
 test(array, i + 1, j, count);
 test(array, i, j - 1, count);
 test(array, i, j + 1, count);
 return true;
 
 

 var count = 1,
 islands = array.map(a => a.map(v => -v));
 islands.forEach((a, i, aa) => a.forEach((_, j) => test(aa, i, j, count) && count++));
 return islands, count: count - 1 ;


function countMatches(array1, array2) 
 var islands = getIslands(array1),
 matches = Array.from( length: islands.count + 1 ).fill(true);

 islands.islands.forEach((a, i) => a.forEach((v, j) => matches[v] = matches[v] && array2[i][j] && v));
 islands.islands.forEach(a => console.log(...a));
 console.log('');
 array2.forEach(a => console.log(...a));
 console.log('islands', ...matches.filter(Boolean));
 return matches.reduce((s, b) => s + !!b, 0);


console.log(countMatches([[0, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]], [[0, 1, 0, 1], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]]));
console.log(countMatches([[0, 1, 0, 1], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]], [[0, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1]]));
console.log(countMatches([[0, 0, 1], [0, 1, 1], [1, 0, 0]], [[0, 0, 1], [0, 1, 1], [1, 0, 1]]));
console.log(countMatches([[0, 0, 1], [0, 1, 1], [1, 0, 1]], [[0, 0, 1], [0, 1, 1], [1, 0, 0]]));

.as-console-wrapper max-height: 100% !important; top: 0;