Find Rectangles

findRectangles.js

const image = [
  [0, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1, 1],
  [0, 1, 1, 0, 0, 0, 1],
  [1, 0, 1, 0, 0, 0, 1],
  [1, 0, 1, 1, 1, 1, 1],
  [1, 0, 1, 0, 0, 1, 1],
  [1, 1, 1, 0, 0, 1, 1],
  [1, 1, 1, 1, 1, 1, 0],
];

function findRectangles(image) {
  const coordinates = getCoordinatesForValue(image, 0);
  const rectangles = groupCoordinatesIntoRectangles(coordinates);
  return reduceRectangleCoordinates(rectangles);
}

function getCoordinatesForValue(image, value) {
  const coordinates = [];
  for (let rowIndex = 0; rowIndex < image.length; rowIndex++) {
    for (let columnIndex = 0; columnIndex < image[rowIndex].length; columnIndex++) {
      if (image[rowIndex][columnIndex] === value) {
        coordinates.push([rowIndex, columnIndex]);
      }
    }
  }
  return coordinates;
}

function groupCoordinatesIntoRectangles(coordinates) {
  const rectangles = [];
  if (coordinates.length) {
    rectangles.push([[coordinates[0][0], coordinates[0][1]]]);
  }
  for (let coordIndex = 1; coordIndex < coordinates.length; coordIndex++) {
    const coordinate = coordinates[coordIndex];
    let isPartOfRectangleIndex = false;
    for (let rectIndex = 0, rectLength = rectangles.length; rectIndex < rectLength; rectIndex++) {
      if (isCoordinatePartOfRectangle(rectangles[rectIndex], coordinate)) {
        isPartOfRectangleIndex = rectIndex;
        break;
      }
    }
    if (isPartOfRectangleIndex !== false) {
      rectangles[isPartOfRectangleIndex].push(coordinate);
    } else {
      rectangles.push([coordinate]);
    }
  }
  return rectangles;
}

function reduceRectangleCoordinates(rectangles) {
  return rectangles.reduce((coordinates, rectangle) => {
    coordinates.push(`${rectangle[0]}, ${rectangle[rectangle.length - 1]}`);
    return coordinates;
  }, []);
}

function isCoordinatePartOfRectangle(rectangle, coordinate) {
  for (let coordIndex = 0; coordIndex < rectangle.length; coordIndex++) {
    if (rectangle[coordIndex][1] === coordinate[1] && rectangle[coordIndex][0] === coordinate[0] - 1) { // matching y
      return true;
    }
    if (rectangle[coordIndex][0] === coordinate[0] && rectangle[coordIndex][1] === coordinate[1] - 1) { // matching x
      return true;
    }
  }
  return false;
}

console.log(findRectangles(image).join('\n'));

// 0,0, 0,0
// 2,0, 2,0
// 2,3, 3,5
// 3,1, 5,1
// 5,3, 6,4
// 7,6, 7,6