0
227
VistasCompruebe si los elementos en la matriz 2d forman un rectángulo
Estoy buscando una fórmula de JavaScript simple que calcule si la X que el usuario escribe en un cuadro forma un rectángulo o un cuadrado.
He intentado un bucle para hacer esto, pero creo que lo he hecho demasiado complejo.
Básicamente he almacenado los datos así (typescript)
public proposedArray: Array<Array<boolean>> = [];
He esbozado un diagrama a continuación en lo que serían opciones válidas/no válidas. ¿Alguien puede ayudarme por favor?
¡Gracias!
3 Respuestas
Responde la pregunta0
Si toma la matriz como una cadena de varias líneas, como:
ooooo
ooxxo
ooxxo
ooooo
... entonces puedes usar esta expresión regular para hacer la validación:
^(o*\n)*(o*x+)o*\n(\2o*\n)*[o\n]*$
Las o finales se ignoran, por lo que las líneas no tienen que tener la misma longitud para seguir detectando un rectángulo.
Aquí hay un fragmento donde la entrada se toma de un elemento <textarea> . Edite el texto para ver el resultado:
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>
Si ya tiene la matriz bidimensional, entonces, por supuesto, primero puede transformar esa matriz en una cadena de varias líneas y luego realizar la prueba de expresiones regulares.
0
Con un simple asistente de clamp que restringe un valor para que esté entre los valores mínimo y máximo, simplemente puede calcular los índices X e Y mínimo y máximo, y luego usarlos para probar si cada celda dentro de esos límites tiene el valor "x" , con algo como esto:
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']
]))
Los cálculos de esos valores son tediosos pero no difíciles. Luego, simplemente verificamos si cada valor en cada fila del subarreglo indicado por esos mínimos y máximos tiene el valor "x" .
0
Una idea que me vino a la mente fue crear un algoritmo que:
- Consume hacia adentro, o de arriba a abajo, de izquierda a derecha (desde los 4 lados recursivamente) todos los bordes
"O". Un borde válido para consumir debe estar hecho exclusivamente de valores"O". - Una vez que haya terminado con los cuatro "consumidores de borde" (no es posible realizar más iteraciones en los cuatro lados), verifique si la matriz 2D restante consta exclusivamente de valores
"X".
Visualmente:
Ejemplo:
Aquí uso la transposición, pero puedes crear una función trimHorizontal si quieres
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