Check if items in 2d array form a rectangle

user3318542 0
Viewed 44

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!

enter image description here

multidimensional-array algorithm javascript
4 Answers

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.

trincot0

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))

IT goldman0

An idea that popped my mind was to create an algorithm that:

  1. Consumes inwards, or top-to-bottom, left-to-right (from all 4 sides recursively) all the "O" edges. A valid edge to consume must be made exclusively of "O" values.
  2. Once all of the four "edge consumers" are done (no more iterations are possible on all four sides) check if the remaining 2D array consists exclusively of "X" values.

Visually:

enter image description here

Example:

Here I use transpose, but you can create a trimHorizontal function if you want

const trim = a => {
  const t = a.findIndex(a=>a.some(x=>x));
  return t < 0 ? a : a.slice(t, a.findLastIndex(a=>a.some(x=>x))+1);
};
const transpose = a => a[0].map((_,i)=>a.map(r=>r[i]));
const hasRect = a => !trim(transpose(trim(a))).flat().some(v=>!v); 


console.log(hasRect([ 
  [0, 0, 0],
  [0, 0, 1],
]));          // true

console.log(hasRect([ 
  [0, 0, 0],
  [0, 1, 1],
  [0, 1, 1],
]));          // true

console.log(hasRect([
  [1, 0, 0],
  [0, 0, 1],
]));         // false

console.log(hasRect([
  [0, 1, 0],
  [0, 0, 0],
  [0, 1, 0],
]));         // false

Roko C. Buljan0

With a simple clamp helper that constrains a value to be between minimum and maximum values, you can simply calculate the minimum and maximum X- and Y-indices, and then use them to test whether every cell within those bounds has the value "x", with something like this:

const clamp = (min, max, x) => Math .max (min, Math .min (max, x))

const xRect = (vss) => {
  const minX = clamp (0, vss [0] .length, Math .min (...vss .map (vs => vs .indexOf ('x')) .filter (v => v > -1)))
  const minY = clamp (0, vss .length, vss .findIndex (v => v .includes ('x')))
  const maxX = clamp (0, vss [0] .length, Math .max (...vss .map (vs => vs .lastIndexOf ('x')) .filter (v => v > -1)))
  const maxY = clamp (0, vss .length, vss .length - [...vss] .reverse() .findIndex (v => v .includes ('x')) - 1)

  return vss .slice (minY, maxY + 1) .every (
    vs => vs .slice (minX, maxX + 1) .every (v => v == 'x')
  )
}

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'x', 'o'],
  ['x', 'o', 'x']
]))

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'x', 'o'],
  ['o', 'x', 'o']
]))

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'x', 'o'],
  ['x', 'x', 'o']
]))

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'o', 'o'],
  ['x', 'o', 'o']
]))

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'o', 'o'],
  ['o', 'o', 'o']
]))

console .log (xRect ([
  ['o', 'o', 'o'],
  ['x', 'o', 'x'],
  ['o', 'o', 'o']
]))

The calculations of those values is tedious but not difficult. Then we simply check if every value in every row of the subarray indicated by those minima and maxima has value "x".

Scott Sauyet0
Related