0
225
ViewsCheck if items in 2d array form a rectangle
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!
3 answers
Answer question0
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.
0
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".
0
An idea that popped my mind was to create an algorithm that:
- 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. - 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:
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