const seed = require('math-random-seed');
const clone = require('rfdc/default');
/**Clase Generadora de crucigramas mediante algoritmos genéticos */
class ConwordsGenerator {
/**Opciones por defecto (modificables)<br>ej: ConwordsGenerator.options.ancho = 50;
* @type {Object}
*/
static options = {
compilacion: null,
ancho: 24,
alto: 22,
espacioVacio: '·',
palabrasPorIteracion: 2,
solucionesPorIteracion: 33,
solucionesSeleccionadas: 22,
palabrasEnBorde: 0.9,
factorLargoMinimo: 1,
finishAt: 600,
fnPuntaje: (llenado, cruces, solas) => {
return (llenado * 4 + 2 * cruces) / (1 + solas * 4);
},
};
/**Este procedimiento agrupa las palabras por largo e indexa todas las palabras que tienen igual letra en cierta posicion, esto se hace para hacer mas rapido la generación de crucigramas.
* @param {Array} diccionarios - Array de diccionarios a compilar, donde cada diccionario es un array con la siguiente estructura:
* [
* [ 'palabra','descripcion','descripcion',... ]
* [ 'palabra','descripcion','descripcion',... ]
* ...
* ]
* En la carpeta diccionarios se encuentran algunos ejemplos de diccionarios.
* @param {Function} fnProgress - Funcion que se llama cada vez que se termina de procesar un porcentaje de las palabras, recibe como parametro el porcentaje procesado (0-100)
* @returns {Promise} - retorna una promesa que resuelve con la compilación.
*/
static async compilar(diccionarios, fnProgress) {
/**Funcion usada para esperar (Se usa en la web para no bloquear el hilo)
* @param {Number} delay - Tiempo en milisegundos a esperar
*/
const delay = async (delay) => {
return new Promise((resolve) => {
setTimeout(resolve, delay);
});
};
//Agrupa todas las palabras y descripciones en un solo array
const data = diccionarios.flatMap((d) => d);
let palabras = [];
let frases = [];
let mapaGrupos = new Map();
let p0 = 0;
//Recorre todas las palabras y las agrupa por largo
for (let linea of data) {
let percent = Math.round((data.indexOf(linea) / data.length) * 100);
if (p0 !== percent) {
p0 = percent;
if (fnProgress) {
fnProgress(percent);
await delay(100);
}
}
let set1 = [];
let set2 = [];
let idxMap = new Map();
linea.forEach((item) => {
//Descarta palabras de solo 1 letra
if (item.length > 1) {
if (item.match(/\s+/) === null) {
//Los textos sin espacios van a set1
set1.push(item);
let idx = palabras.indexOf(item);
if (idx === -1) {
palabras.push(item);
idx = palabras.length - 1;
}
idxMap.set(item, idx);
} else {
//Los textos con espacios van a set2
set2.push(item);
let idx = frases.indexOf(item);
if (idx === -1) {
frases.push(item);
idx = frases.length - 1;
}
idxMap.set(item, idx);
}
}
});
if (set1.length > 0 && set1.length + set2.length > 1) {
set1.forEach((item) => {
let itemIdx = idxMap.get(item);
let grupoItem = mapaGrupos.get(itemIdx);
grupoItem = grupoItem ? grupoItem : [[], []];
set1.forEach((item2) => {
if (item !== item2) {
grupoItem[0].push(idxMap.get(item2));
}
});
set2.forEach((item2) => {
grupoItem[1].push(idxMap.get(item2));
});
mapaGrupos.set(itemIdx, grupoItem);
});
}
}
const letras = {};
const largos = [];
const preguntas = [];
preguntas.length = palabras.length;
for (let idx = 0; idx < preguntas.length; idx++) {
preguntas[idx] = mapaGrupos.get(idx);
}
let maxLargo = 0;
palabras.forEach((palabra, idx) => {
let match = palabra.match(/[A-Z0-9ÁÉÍÓÚÜÑ]+/);
if (match !== null && match[0] === palabra && palabra.length > 1) {
if (palabra.length > maxLargo) {
maxLargo = palabra.length;
}
let largo = palabra.length;
if (largos[largo] === undefined) {
for (let i = 0; i <= largo; i++) {
if (largos[i] === undefined) {
largos[i] = [];
}
}
}
largos[largo].push(idx);
for (let i = 0; i < palabra.length; i++) {
let letra = '' + i + palabra[i];
if (letras[letra] === undefined) {
letras[letra] = [];
}
letras[letra].push(idx);
}
6;
}
});
//largos.length = maxLargo + 1;
//largos.splice(0, 1);
return { palabras, letras, largos, frases, preguntas };
}
/**Instancia un nuevo generador de crucigramas indicando las opciones de configuración
* Ejemplo de opciones: {ancho: 50, alto: 50, compilacion: miCompilacion}
*
* @param {Object} options - Opciones de configuración
* @param {Object} options.compilacion - Compilación de diccionarios (null por defecto, debe proveerse)
* @param {Number} options.ancho - Ancho del crucigrama (24 por defecto)
* @param {Number} options.alto - Alto del crucigrama (22 por defecto)
* @param {String} options.espacioVacio - Carácter del espacio no usado ('·' por defecto)
* @param {Number} options.palabrasPorIteracion - Cantidad de palabras agregadas en cada nueva iteración (2 por defecto)
* @param {Number} options.solucionesSeleccionadas - Cantidad de soluciones seleccionadas de la generación anterior para ser usadas en la siguiente iteración (22 por defecto)
* @param {Number} options.solucionesPorIteracion - Cantidad de soluciones generadas en iteración, a partir de las soluciones seleccionadas de la generación anterior (33 por defecto)
* @param {Number} options.palabrasEnBorde - Cantidad de palabras en los bordes [0, 1] (0.9 por defecto)
* @param {Number} options.factorLargoMinimo - Factor de disminución del largo minimo en las iteraciones: mientras sea mayor mas rapidamente el largo minimo de las palabras ira disminuyendo entre cada iteración (1 por defecto)
* @param {Number} options.finishAt - Cantidad maximo de intentos para encontrar una solucion, despues de alcanzado estos intentos esa solución se marca como finalizado y no se intentaran mas soluciones (600 por defecto)
* @param {Function} options.fnPuntaje - Es una función que asigna un puntaje al crucigrama y que depende del porcentaje de llenado, la cantidad de cruces de palabras y la cantidad de palabras solas (que no se cruzan con otras) ((llenado * 4 + 2 * cruces) / (1 + solas * 4) por defecto))
*/
constructor(options) {
if (!options.compilacion) {
throw new Error('Debe pasar la compilacion de diccionarios como parametro');
}
this.#configurar(ConwordsGenerator.options);
this.#configurar(options);
}
/**Genera la matriz inicial del crucigrama
* @param {Number} semilla - Semilla para generar la matriz del crucigrama (aleatorea por defecto)
* @returns {String} - Matriz del crucigrama (Si no se pasa semilla se genera una aleatorea)
*/
generar(semilla = this.#generateSerial()) {
let matriz = Array.from({ length: this.options.alto }).map(() => new Array(this.options.ancho).fill([this.options.espacioVacio, false, false]));
matriz.preguntas = new Set();
matriz.preguntasData = [];
matriz.ancho = this.options.ancho;
matriz.alto = this.options.alto;
this.semilla = '' + semilla;
this.random = seed(semilla);
return matriz;
}
/**
* Realiza una iteración de generación de crucigrama
* @param {*} matrices
* @returns retorna la matriz resultante de la iteración
*/
iterar(matrices) {
if (matrices.preguntas !== undefined) {
matrices = [matrices];
}
let soluciones = [];
for (let i = 0; i < this.options.solucionesPorIteracion; i++) {
let idx = Math.floor((matrices.length * i) / this.options.solucionesPorIteracion);
let matriz = matrices[idx];
let matrizClon = clone(matriz);
for (let palabra = 0; palabra < this.options.palabrasPorIteracion; palabra++) {
matrizClon = this.#generarPregunta(matrizClon);
}
soluciones.push(matrizClon);
}
return this.#seleccionarSoluciones(soluciones);
}
/**
* Completa los espacios no usados con palabras cortas
* @param {*} matrices
* @returns retorna la matriz completando los espacios vacios
*
* */
completar(matrices) {
//Vamos a comentar la mayor parte de este metodo
//Recorre las matrices
matrices.forEach((matriz) => {
let continua = true;
while (continua) {
let points = [];
//Recorre las filas
for (let x = 0; x < this.options.ancho; x++) {
//Recorre las columnas
for (let y = 0; y < this.options.alto; y++) {
//Si en x,y hay un espacio vacio
if (matriz[y][x][0] === this.options.espacioVacio) {
//busca el espacio mas grande de una palabra horizontal que pase por x,y
//tambien debe chequear que no haya una palabra horizontal, sobre o bajo la palabra que estamos buscando
let x1 = x,
x2 = x,
chocoX1 = false,
chocoX2 = false,
sigue = true;
while (sigue) {
//lega al borde izquierdo
if (x1 < 0) {
x1 = 0;
sigue = false;
chocoX1 = false;
//choca con una palabra horizontal
} else if (matriz[y][x1][2]) {
sigue = false;
x1++;
x1++;
chocoX1 = false;
//choca con una palabra vertical
} else if (matriz[y][x1][1]) {
sigue = false;
chocoX1 = true;
// esta bajo una palabra horizontal
} else if (y > 0 && matriz[y - 1][x1][0] !== this.options.espacioVacio) {
sigue = false;
x1++;
chocoX1 = false;
// esta sobre una palabra horizontal
} else if (y < this.options.alto - 1 && matriz[y + 1][x1][0] !== this.options.espacioVacio) {
sigue = false;
x1++;
chocoX1 = false;
}
if (sigue) {
x1--;
}
}
sigue = true;
while (sigue) {
//llega al borde derecho
if (x2 >= this.options.ancho) {
x2 = this.options.ancho - 1;
sigue = false;
chocoX2 = false;
//choca con una palabra horizontal
} else if (matriz[y][x2][2]) {
sigue = false;
x2--;
x2--;
chocoX2 = false;
//choca con una palabra vertical
} else if (matriz[y][x2][1]) {
sigue = false;
chocoX2 = true;
// esta bajo una palabra horizontal
} else if (y > 0 && matriz[y - 1][x2][0] !== this.options.espacioVacio) {
sigue = false;
x2--;
chocoX2 = false;
// esta sobre una palabra horizontal
} else if (y < this.options.alto - 1 && matriz[y + 1][x2][0] !== this.options.espacioVacio) {
sigue = false;
x2--;
chocoX2 = false;
}
if (sigue) {
x2++;
}
}
if ((chocoX1 || chocoX2) && x1 < x2) {
points.push({ x: x1, y: y, size: x2 + 1 - x1, horizontal: true });
if (chocoX1) {
for (let size = 2; size <= x2 + 1 - x1; size++) {
points.push({ x: x1, y: y, size: x2 + 1 - x1, horizontal: true });
}
}
}
//busca el espacio mas grande de una palabra vertical que pase por x,y
//tambien debe chequear que no haya una palabra vertical al lado la palabra que estamos buscando
let y1 = y,
y2 = y,
chocoY1 = false,
chocoY2 = false;
sigue = true;
while (sigue) {
//llega al borde superior
if (y1 < 0) {
y1 = 0;
sigue = false;
chocoY1 = false;
//choca con una palabra vertical
} else if (matriz[y1][x][1]) {
sigue = false;
y1++;
y1++;
chocoY1 = false;
//choca con una palabra horizontal
} else if (matriz[y1][x][2]) {
sigue = false;
chocoY1 = true;
// esta a la izquierda de una palabra vertical
} else if (x > 0 && matriz[y1][x - 1][0] !== this.options.espacioVacio) {
sigue = false;
y1++;
chocoY1 = false;
// esta a la derecha de una palabra vertical
} else if (x < this.options.ancho - 1 && matriz[y1][x + 1][0] !== this.options.espacioVacio) {
sigue = false;
y1++;
chocoY1 = false;
}
if (sigue) {
y1--;
}
}
sigue = true;
while (sigue) {
//llega al borde inferior
if (y2 >= this.options.alto) {
y2 = this.options.alto - 1;
sigue = false;
chocoY2 = false;
//choca con una palabra vertical
} else if (matriz[y2][x][1]) {
sigue = false;
y2--;
y2--;
chocoY2 = false;
//choca con una palabra horizontal
} else if (matriz[y2][x][2]) {
sigue = false;
chocoY2 = true;
// esta a la izquierda de una palabra vertical
} else if (x > 0 && matriz[y2][x - 1][0] !== this.options.espacioVacio) {
sigue = false;
y2--;
chocoY2 = false;
// esta a la derecha de una palabra vertical
} else if (x < this.options.ancho - 1 && matriz[y2][x + 1][0] !== this.options.espacioVacio) {
sigue = false;
y2--;
chocoY2 = false;
}
if (sigue) {
y2++;
}
}
if ((chocoY1 || chocoY2) && y1 < y2) {
points.push({ x: x, y: y1, size: y2 + 1 - y1, horizontal: false });
}
}
}
}
points.sort((a, b) => {
return b.size - a.size;
});
//console.log(points);
continua = false;
for (let point of points) {
let matches = new Set();
if (point.horizontal) {
if (matriz[point.y][point.x][0] !== this.options.espacioVacio) {
matches.add('' + 0 + matriz[point.y][point.x][0]);
}
if (matriz[point.y][point.x + point.size - 1][0] !== this.options.espacioVacio) {
matches.add('' + (point.size - 1) + matriz[point.y][point.x + point.size - 1][0]);
}
} else {
if (matriz[point.y][point.x][0] !== this.options.espacioVacio) {
matches.add('' + 0 + matriz[point.y][point.x][0]);
}
if (matriz[point.y + point.size - 1][point.x][0] !== this.options.espacioVacio) {
matches.add('' + (point.size - 1) + matriz[point.y + point.size - 1][point.x][0]);
}
}
let palabras = this.options.compilacion.largos[point.size];
if (palabras !== undefined) {
palabras = palabras.filter((palabra) => this.ignored.has(palabra) === false);
palabras = palabras ? palabras : [];
for (let match of matches) {
let palabrasMatch = this.options.compilacion.letras[match];
if (palabrasMatch !== undefined) {
palabras = palabras.filter((p) => palabrasMatch.includes(p));
} else {
palabras = [];
}
}
palabras = palabras.filter((p) => !matriz.preguntas.has(p));
if (palabras.length > 0) {
let pos = Math.floor(Math.random() * palabras.length);
let idx = palabras[pos];
let palabra = this.options.compilacion.palabras[idx];
let x = point.x,
y = point.y;
for (let i = 0; i < palabra.length; i++) {
matriz[y][x][0] = palabra[i];
if (point.horizontal) {
matriz[y][x][2] = true;
x++;
} else {
matriz[y][x][1] = true;
y++;
}
}
continua = true;
matriz.preguntas.add(idx);
matriz.preguntasData.push({ idx, palabra, horizontal: point.horizontal ? 1 : 0, x: point.x, y: point.y });
break;
}
}
}
}
});
return this.#seleccionarSoluciones(matrices);
}
/** Formatea el crucigrama para ser mostrado por consola
* @param {Array} matriz - Matriz del crucigrama
* @param {Boolean} preguntas - Indica si se muestran las preguntas (false por defecto)
* @param {Number} layer - 0 por defecto
* @param {Number} solucionesVisibles - Indica la cantidad de soluciones visibles (1 por defecto)
* @returns {String} - Matriz del crucigrama formateada
*/
toString(matrices, preguntas = false, layer = 0, solucionesVisibles = 1) {
if (matrices.preguntas !== undefined) {
matrices = [matrices];
}
let textos = [];
let alto = 0;
let mt = [...matrices];
mt.length = solucionesVisibles;
mt.forEach((matriz) => {
if (matriz) {
let s = ' ';
for (let x = 0; x < this.options.ancho; x++) {
s = s + Math.trunc(x / 10) + ' ';
}
s = s + '\n ';
for (let x = 0; x < this.options.ancho; x++) {
s = s + (x % 10) + ' ';
}
s = s + '\n\n';
for (let y = 0; y < this.options.alto; y++) {
s = s + (y < 10 ? '0' : '') + y + ' ';
for (let x = 0; x < this.options.ancho; x++) {
s = s + (layer > 0 ? (matriz[y][x][layer].toUpperCase() ? '#' : '·') : matriz[y][x][0].toUpperCase()) + ' ';
}
s = s + '\n';
}
let lineas = s.split('\n');
if (lineas.length > alto) {
alto = lineas.length;
}
textos.push(lineas);
}
});
function pad(s, n) {
try {
let x = s.length < n ? pad(s + ' ', n) : s.substring(0, n);
return x;
} catch (error) {
return '.';
}
}
let ss = '';
for (let i = 0; i < alto; i++) {
for (let j = 0; j < textos.length; j++) {
ss += pad(textos[j][i] ? textos[j][i] : '', Math.max(26, this.options.ancho * 2 + 5));
}
ss = ss + '\n';
}
if (preguntas) {
mt.forEach((matriz) => {
for (let orientacion of [1, 0]) {
let s = '\n' + (orientacion ? 'HORIZONTAL:' : 'VERTICAL:') + '\n';
for (let y = 0; y < this.options.alto; y++) {
for (let x = 0; x < this.options.ancho; x++) {
let pregunta = matriz.preguntasData.find((p) => p.x === x && p.y === y && p.horizontal === orientacion);
if (pregunta) {
let preg = clone(this.options.compilacion.preguntas[pregunta.idx]);
preg[0] = preg[0].filter((idx) => idx !== pregunta.idx);
preg[0] = preg[0].map((idx) => this.options.compilacion.palabras[idx]);
preg[1] = preg[1].map((idx) => this.options.compilacion.frases[idx]);
let options = [...preg[0], ...preg[1]];
preg = options[Math.floor(this.random() * options.length)];
pregunta.pregunta = preg;
pregunta.horizontal = pregunta.horizontal === 1;
delete pregunta.idx;
s = s + `${(x < 10 ? '0' : '') + x}${(y < 10 ? '0' : '') + y}:${pregunta.palabra}: ${preg}\n`;
}
}
}
ss = ss + s;
}
});
}
const matriz = matrices[0];
ss = `${ss}\nRESUMEN (${this.semilla})\n-------------------\nTAMAÑO: ${this.options.ancho}x${this.options.alto}\nHASH: ${matriz.hash}\nCRUCES: ${matriz.cruces}\nPALABRAS SOLAS: ${matriz.solas}\nLLENADO: ${matriz.llenado} ${matriz.llenado ? Math.round((100 * matriz.llenado) / this.options.ancho / this.options.alto) : ''}%\nSCORE: ${matriz.puntaje}`;
return ss;
}
/**
* Retorna la matriz del crucigrama en formato JSON
* @param {*} matriz
* @returns matriz en formato JSON
*/
getJSON(matriz) {
if (matriz.preguntas === undefined) {
matriz = matriz[0];
}
const pregs = clone(matriz.preguntasData);
for (let orientacion of [1, 0]) {
for (let y = 0; y < this.options.alto; y++) {
for (let x = 0; x < this.options.ancho; x++) {
let pregunta = pregs.find((p) => p.x === x && p.y === y && p.horizontal === orientacion);
if (pregunta) {
let preg = clone(this.options.compilacion.preguntas[pregunta.idx]);
preg[0] = preg[0].filter((idx) => idx !== pregunta.idx);
preg[0] = preg[0].map((idx) => this.options.compilacion.palabras[idx]);
preg[1] = preg[1].map((idx) => this.options.compilacion.frases[idx]);
let options = [...preg[0], ...preg[1]];
preg = options[Math.floor(this.random() * options.length)];
pregunta.pregunta = preg;
pregunta.horizontal = pregunta.horizontal === 1;
delete pregunta.idx;
}
}
}
}
return pregs;
}
/** Indices de palabras ignoradas,que no se usaran en la proxima generación.<br>
* Para limpiar se debe ejecutar: generador.ignored.clear() */
ignored = new Set();
////////////////////////////////////////////////////////////////////////////////
/** Ignora un set de palabras */
#ignoreWords(words) {
words.forEach((w) => this.ignored.add(w));
}
/** Sobreescribe las opciones */
#configurar(options) {
options = options || {};
this.options = {
...this.options,
...options,
};
}
#ordenarPreguntas(matrices) {
const matricesClonadas = clone(matrices);
for (let matriz of matricesClonadas) {
for (let i = 1; i < matriz.preguntasData.length; i++) {
for (let j = 0; j < i; j++) {
if (
matriz.preguntasData[i].y * this.options.ancho + matriz.preguntasData[i].x - matriz.preguntasData[i].horizontal * 0.5 < //
matriz.preguntasData[j].y * this.options.ancho + matriz.preguntasData[j].x - matriz.preguntasData[j].horizontal * 0.5
) {
let aux = matriz.preguntasData[i];
matriz.preguntasData[i] = matriz.preguntasData[j];
matriz.preguntasData[j] = aux;
aux = matriz.preguntas[i];
matriz.preguntas[i] = matriz.preguntas[j];
matriz.preguntas[j] = aux;
}
}
}
}
return matricesClonadas;
}
/**
* Elimina las palabras que no se cruzan con ninguna otra
* @param {*} matrices
* @returns {Array}
*/
#palabrasSolas(matrices) {
return matrices.map((matriz) => {
let solasIdx = new Set();
matriz.preguntasData.forEach((pregunta1) => {
let subCruces = 0;
matriz.preguntasData.forEach((pregunta2) => {
if (pregunta1.palabra !== pregunta2.palabra && pregunta1.horizontal !== pregunta2.horizontal) {
if (pregunta1.horizontal) {
if (pregunta1.x <= pregunta2.x && pregunta1.x + pregunta1.palabra.length > pregunta2.x) {
if (pregunta1.y >= pregunta2.y && pregunta1.y < pregunta2.y + pregunta2.palabra.length) {
subCruces++;
}
}
} else {
if (pregunta1.y <= pregunta2.y && pregunta1.y + pregunta1.palabra.length > pregunta2.y) {
if (pregunta1.x >= pregunta2.x && pregunta1.x < pregunta2.x + pregunta2.palabra.length) {
subCruces++;
}
}
}
}
});
if (subCruces === 0) {
solasIdx.add(pregunta1);
}
});
return solasIdx;
});
}
/**
* A partir de un array de soluciones, las evalua y retorna las mejores soluciones (cantidadRetornada)
* */
#seleccionarSoluciones(soluciones, cantidadRetornada = this.options.solucionesSeleccionadas) {
soluciones.forEach((matriz) => {
matriz.hash = this.#hashCode(
matriz.preguntasData.reduce((p, c) => {
return p + c.palabra + '_' + c.horizontal + '_' + c.x + '_' + c.y;
}, '')
);
let cruces = this.#getCruces(matriz);
matriz.cruces = cruces[0];
matriz.solas = cruces[1];
matriz.llenado = this.#getLlenado(matriz);
matriz.puntaje = this.options.fnPuntaje(matriz.llenado, matriz.cruces, matriz.solas);
});
let solucionesNoRepetidasIdx = [];
let solucionesNoRepetidas = [];
soluciones.forEach((matriz) => {
if (!solucionesNoRepetidasIdx.includes(matriz.hash)) {
solucionesNoRepetidasIdx.push(matriz.hash);
solucionesNoRepetidas.push(matriz);
}
});
solucionesNoRepetidas.sort((a, b) => b.puntaje - a.puntaje);
solucionesNoRepetidas.length = Math.min(solucionesNoRepetidas.length, cantidadRetornada);
return solucionesNoRepetidas;
}
/**Elimina los acentos */
#normalizarLetra(letra) {
return letra.replace('á', 'a').replace('é', 'e').replace('í', 'i').replace('ó', 'o').replace('ú', 'u').replace('ü', 'u');
}
/**Metodo privado que genera una semilla aleatoria, indicando otra semilla y el largo de la semilla*/
#generateSerial(random = seed(), serialLength) {
const TAMAÑO_SEMILLA_X_DEFECTO = 8;
const CARACTERES_SEMILLA = '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ';
serialLength = serialLength || TAMAÑO_SEMILLA_X_DEFECTO;
let randomSerial = '';
for (let i = 0; i < serialLength; i = i + 1) {
let randomNumber = Math.floor(random() * CARACTERES_SEMILLA.length);
randomSerial += CARACTERES_SEMILLA.substring(randomNumber, randomNumber + 1);
}
return randomSerial;
}
#generarPregunta(matrizClon) {
let intento = 0;
while (true) {
if (matrizClon.finish) {
return matrizClon;
} else {
intento++;
if (intento === this.options.finishAt) {
if (this.options.palabrasEnBorde && !matrizClon.borde) {
matrizClon.borde = true;
intento = 0;
} else {
matrizClon.finish = true;
return matrizClon;
}
}
// 0: vertical, 1: horizontal
let horizontal = Math.floor(this.random() * 2);
let largo = Math.max(
Math.max(
//
2,
Math.min(this.options.ancho, this.options.alto, Math.trunc(this.options.compilacion.largos.length / 3) - 1) - Math.floor(matrizClon.preguntasData.length * this.options.factorLargoMinimo)
),
Math.floor(this.random() * Math.min(horizontal === 1 ? this.options.ancho : this.options.alto, this.options.compilacion.largos.length))
);
let palabras = this.options.compilacion.largos[largo];
palabras = palabras.filter((palabra) => this.ignored.has(palabra) === false);
let x,
y,
matches = [];
if (this.options.palabrasEnBorde && !matrizClon.borde) {
x = horizontal //
? Math.floor(this.random() * (this.options.ancho - largo)) //
: Math.floor(this.random() * 2) * (this.options.ancho - 1);
y = horizontal //
? Math.floor(this.random() * 2) * (this.options.alto - 1)
: Math.floor(this.random() * (this.options.alto - largo));
} else {
x = horizontal //
? Math.floor(this.random() * (this.options.ancho - largo)) //
: Math.floor(this.random() * this.options.ancho);
y = horizontal //
? Math.floor(this.random() * this.options.alto)
: Math.floor(this.random() * (this.options.alto - largo));
}
let ok = true;
if (
//falla si al inicio o al final de la palabra esta ocupado
(horizontal && x > 0 && matrizClon[y][x - 1][0] !== this.options.espacioVacio) ||
(horizontal && x < this.options.ancho - largo && matrizClon[y][x + largo][0] !== this.options.espacioVacio) ||
(!horizontal && y > 0 && matrizClon[y - 1][x][0] !== this.options.espacioVacio) ||
(!horizontal && y < this.options.alto - largo && matrizClon[y + largo][x][0] !== this.options.espacioVacio)
) {
ok = false;
}
let vecinoAdjacente = new Set();
let vecinoCruce = new Set();
if (ok) {
//recorre las filas
for (let i = 0; i < largo; i++) {
//falla: si la palabra es horizontal e intersecta con otra palabra horizontal
if (horizontal && matrizClon[y][x + i][1 + horizontal]) {
ok = false;
break;
}
//falla: si la palabra es vertical e intersecta con otra palabra vertical
if (!horizontal && matrizClon[y + i][x][1 + horizontal]) {
ok = false;
break;
}
if (ok) {
let match;
if (horizontal) {
if (y > 0) {
match = this.#getPreguntasPorPosicion(matrizClon, x + i, y - 1);
match.forEach((p) => {
vecinoAdjacente.add(p.idx);
});
}
if (y < this.options.alto - 1) {
match = this.#getPreguntasPorPosicion(matrizClon, x + i, y + 1);
match.forEach((p) => {
vecinoAdjacente.add(p.idx);
});
}
match = this.#getPreguntasPorPosicion(matrizClon, x + i, y);
match.forEach((p) => vecinoCruce.add(p.idx));
} else {
if (x > 0) {
match = this.#getPreguntasPorPosicion(matrizClon, x - 1, y + i);
match.forEach((p) => {
vecinoAdjacente.add(p.idx);
});
}
if (x < this.options.ancho - 1) {
match = this.#getPreguntasPorPosicion(matrizClon, x + 1, y + i);
match.forEach((p) => {
vecinoAdjacente.add(p.idx);
});
}
match = this.#getPreguntasPorPosicion(matrizClon, x, y + i);
match.forEach((p) => vecinoCruce.add(p.idx));
}
if (horizontal && matrizClon[y][x + i][0] !== this.options.espacioVacio) {
matches.push('' + i + matrizClon[y][x + i][0]);
}
if (!horizontal && matrizClon[y + i][x][0] !== this.options.espacioVacio) {
matches.push('' + i + matrizClon[y + i][x][0]);
}
}
}
}
if ([...vecinoAdjacente].filter((m) => !vecinoCruce.has(m)).length > 0) {
ok = false;
}
if (ok) {
if (matches.length > 0) {
let _palabras = [];
palabras.forEach((palabra) => {
let ok = true;
for (let match of matches) {
let palabrasMatch = this.options.compilacion.letras[match];
if (palabrasMatch === undefined || (palabrasMatch !== undefined && !palabrasMatch.includes(palabra))) {
ok = false;
break;
}
}
if (ok) {
_palabras.push(palabra);
}
});
palabras = _palabras;
} else if (this.options.palabrasEnBorde && matrizClon.borde) {
ok = false;
}
if (ok && palabras.length > 0) {
let idx = undefined;
let count = 0;
while (idx === undefined || matrizClon.preguntas.has(idx)) {
idx = palabras[Math.floor(this.random() * palabras.length)];
count++;
if (count === 100) {
ok = false;
break;
}
}
if (ok) {
let palabra = this.options.compilacion.palabras[idx];
for (let i = 0; i < largo; i++) {
let letra = this.#normalizarLetra(palabra.charAt(i));
if (horizontal) {
matrizClon[y][x + i][0] = letra;
matrizClon[y][x + i][1 + horizontal] = true;
}
if (!horizontal) {
matrizClon[y + i][x][0] = letra;
matrizClon[y + i][x][1 + horizontal] = true;
}
}
matrizClon.preguntas.add(idx);
matrizClon.preguntasData.push({ idx, palabra, horizontal, x, y });
if (this.options.palabrasEnBorde && !matrizClon.borde) {
let total = (this.options.ancho + this.options.alto) * 2;
let llevo = matrizClon.preguntasData.map((p) => p.palabra).join('').length;
//console.log(total, llevo, total - llevo);
matrizClon.borde = llevo / total > this.options.palabrasEnBorde;
}
return matrizClon;
}
}
}
}
}
}
#hashCode(str) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
const char = str.charCodeAt(i);
hash = (hash << 5) - hash + char;
hash = hash & hash;
}
return hash;
}
/**Retorna los espacios llenados del crucigrama */
#getLlenado(matriz) {
return Math.trunc(
Math.trunc(
matriz.reduce((acc, fila) => {
let length = fila.filter((x) => {
return x[0] !== this.options.espacioVacio;
}).length;
return acc + length;
}, 0)
)
);
}
/**Retorna la cantidad de cruces del crucigrama y la contidad de preguntas solas */
#getCruces(matriz) {
let cruces = 0;
let solas = 0;
matriz.solasIdx = new Set();
matriz.preguntasData.forEach((pregunta1) => {
let subCruces = 0;
matriz.preguntasData.forEach((pregunta2) => {
if (pregunta1.palabra !== pregunta2.palabra && pregunta1.horizontal !== pregunta2.horizontal) {
if (pregunta1.horizontal) {
if (pregunta1.x <= pregunta2.x && pregunta1.x + pregunta1.palabra.length > pregunta2.x) {
if (pregunta1.y >= pregunta2.y && pregunta1.y < pregunta2.y + pregunta2.palabra.length) {
subCruces++;
}
}
} else {
if (pregunta1.y <= pregunta2.y && pregunta1.y + pregunta1.palabra.length > pregunta2.y) {
if (pregunta1.x >= pregunta2.x && pregunta1.x < pregunta2.x + pregunta2.palabra.length) {
subCruces++;
}
}
}
}
});
if (subCruces === 0) {
solas++;
matriz.solasIdx.add(pregunta1);
}
cruces += subCruces;
});
return [cruces, solas];
}
/**Retorna las preguntas en una cordenada */
#getPreguntasPorPosicion(matriz, x, y) {
let found = [];
matriz.preguntasData.forEach((pregunta, idx) => {
if (
(pregunta.horizontal && pregunta.x <= x && pregunta.x + pregunta.palabra.length > x && pregunta.y === y) || //
(!pregunta.horizontal && pregunta.y <= y && pregunta.y + pregunta.palabra.length > y && pregunta.x === x)
) {
found.push(pregunta);
}
});
return found;
}
}
module.exports = ConwordsGenerator;