Check if items in 2d array form a rectangle

Question

I am looking for a simple JavaScript formula that will calculate whether the X that the user types in a box forms either a rectangle or a square.

I have attempted a loop to do this but I think I have made this way too complex.

Basically I have stored the data like this (typescript)

public proposedArray: Array<Array<boolean>> = [];

I have sketched a diagram below in what would be valid/invalid options. Can anyone please help me?

Thanks!

Answer 1

If you take in the matrix as a multi-line string, like:

ooooo
ooxxo
ooxxo
ooooo

...then you can use this regular expression for making the validation:

^(o*\n)*(o*x+)o*\n(\2o*\n)*[o\n]*$

Trailing o are ignored, so the lines do not have to have the same length to still detect a rectangle.

Here is a snippet where the input is taken from a <textarea> element. Edit the text to see the result:

const isRectangle = (grid) => 
    /^(o*\n)*(o*x+)o*\n(\2o*\n)*[o\n]*$/.test(grid + "\n");

// I/O handling

const input = document.querySelector("textarea");
input.addEventListener("input", refresh);
function refresh() {
    const text = input.value.toLowerCase();
    document.querySelector("span").textContent = isRectangle(text);
}
refresh();

<textarea rows=10>
ooooo
ooxoo
ooxxo
ooooo
</textarea><br>
Is rectangle: <span></span>

If you already have the 2-dimensional matrix, then you can of course first transform that matrix to such a multiline string and then perform the regex-test.

Answer 2

Yes loops sounds the naive option. Looping until found a "true". Then caculate width and height, and expect all cells withing range to be "true" as well. If that is so, then expect no more "trues" having cleared the ones we found.

var mat = [
  [0, 0, 0],
  [1, 1, 0],
  [1, 1, 0]
];



function has_square(mat) {
  var found_square = false;
  for (var i = 0; i < mat.length; i++) {
    for (var j = 0; j < mat[i].length; j++) {
      var value = mat[i][j]
      if (value) {
        if (found_square) {
          // not allowed 2 squares
          return false;
        }
        var w = 1;
        for (var k = j + 1; k < mat[i].length; k++) {
          if (!mat[i][k]) {
            break;
          }
          w++;
        }
        var h = 1;
        for (var l = i + 1; l < mat.length; l++) {
          if (!mat[l][j]) {
            break;
          }
          h++;
        }

        // now expect all to be true in [i,j] - [i+h, j+w]
        for (var y = 0; y < h; y++) {
          for (var x = 0; x < w; x++) {
            if (!mat[i + y][j + x]) {
              return false;
            }
            // clear values
            mat[i + y][j + x] = 0
          }
        }
        found_square = true;
      }

    }
  }
  return found_square;
}

console.log(has_square(mat))