Recursive region check

readme.md

HackerRank problem

You're given 2 grids filled with 1 and 0 values (in the form of an array of strings), adjacent 1s are considered regions, your task is to count the matching regions in both grids, adjacent means up, down, left or right, diagonal 1s are not considered part of the region.

Solution

In the Recursive-region-check.js we loop through the grids searching for the start of a region (searching for a 1), then we recursively check if the adjacent cells are part of the region and if it matches with the other grid, then we replace with 0 be it because it matched and we counted it, or didn't match but we already evaluated all the cells of the region in both grids.

Recursive-region-check.js

function recursiveRegionCheck(x, y, grid1, grid2) {
  let result = true;

  if (!(+grid1[y][x] === 1 && +grid2[y][x] === 1)) {
    result = false;
  }

  grid1[y][x] = 0;
  grid2[y][x] = 0;

  // Left (Probably unnecesary since we're looping from left to right)
  if (x > 0 && (+grid1[y][x - 1] === 1 || +grid2[y][x - 1] === 1)) {
    result = recursiveRegionCheck(x - 1, y, grid1, grid2) && result;
  }
  
  // Right
  if (
    x < grid1[y].length - 1 &&
    (+grid1[y][x + 1] === 1 || +grid2[y][x + 1] === 1)
  ) {
    result = recursiveRegionCheck(x + 1, y, grid1, grid2) && result;
  }
  
  // top
  if (y > 0 && (+grid1[y - 1][x] === 1 || +grid2[y - 1][x] === 1)) {
    result = recursiveRegionCheck(x, y - 1, grid1, grid2) && result;
  }
  
  // bottom
  if (
    y < grid1.length - 1 &&
    (+grid1[y + 1][x] === 1 || +grid2[y + 1][x] === 1)
  ) {
    result = recursiveRegionCheck(x, y + 1, grid1, grid2) && result;
  }

  return result;
}

function countMatches(grid1, grid2) {
  // Write your code here
  let regionCount = 0;

  grid1 = grid1.map((row) => row.split(""));
  grid2 = grid2.map((row) => row.split(""));

  for (let y = 0; y < grid1.length; y++) {
    for (let x = 0; x < grid1[y].length; x++) {
      if (+grid1[y][x] === 0 && +grid2[y][x] === 0) {
        continue;
      }

      if (recursiveRegionCheck(x, y, grid1, grid2)) {
        regionCount++;
      }
    }
  }

  return regionCount;
}