Generar una pulsera de longitud n utilizando un conjunto de colores dados – JavaScript
Se me pidió resolver el siguiente problema.
Generar una pulsera de longitud n utilizando un conjunto de colores dados
Condiciones
– Ningún par de elementos adyacentes debe tener los mismos colores, por ejemplo: R R
– No se debe repetir ningún patrón de tres cuentas en la pulsera, por ejemplo: R G B Y R G B,
por ejemplo 2: R G R G R
Entrada – colors = [“R”, “G”, “B”, “Y”], n = 8
Salida – [“R”, “G”, “B”, “Y”, “R”, “G”, “R”, “Y”]
En caso de que no sea posible formar una pulsera de longitud n, debería devolver “false”.
Luego se me ocurrió la siguiente solución
function generateBracelet(colors, n) {
const bracelet = [colors[0]];
const threeBeads = {};
const cLen = colors.length;
let j = 1;
while (n > bracelet.length) {
let bLen = bracelet.length;
if (bracelet[bLen - 1] === colors[j]) {
console.log("hasSameAdjecent");
j++;
j === cLen && (j = 0);
continue;
}
const newThree = bracelet.slice(bLen - 2, bLen).join("") + colors[j];
console.log(newThree);
if (Object.keys(threeBeads).length && threeBeads[newThree]) {
console.log("hasThree");
j++;
j === cLen && (j = 0);
continue;
}
bracelet.push(colors[j]);
bLen = bracelet.length;
bLen >= 3 && (threeBeads[bracelet.slice(bLen - 3, bLen).join("")] = 1);
j++;
j === cLen && (j = 0);
}
console.log(threeBeads);
return bracelet;
}
console.log(generateBracelet(["R", "G", "B", "Y"], 8));
//["R", "G", "B", "Y", "R", "G", "Y", "R"]
Luego la siguiente pregunta obvia fue “¿puede optimizar?”
Sigo preguntándome cuál sería el mejor enfoque para resolver este problema.
Por favor, ilumíname para resolverlo de una mejor manera.
Cualquier pista o solución será muy apreciada.
davy.ai
Un enfoque posible para optimizar esta solución podría ser utilizar un algoritmo de retroceso (backtracking).
Comienza seleccionando la primera cuenta en la pulsera. Luego, para cada color que no sea igual a la cuenta anterior, agrégalo a la pulsera y verifica si la pulsera cumple las condiciones. Si lo hace, agrega recursivamente la siguiente cuenta hasta alcanzar la longitud deseada. Si no es así, elimina la última cuenta agregada y prueba con el siguiente color.
Utilizando este enfoque, puedes evitar crear un objeto threeBeads y reducir el número de iteraciones.
Aquí tienes una implementación de este enfoque en JavaScript:
Ten en cuenta que esta implementación devuelve todas las soluciones válidas en lugar de solo la primera, por lo que puedes modificarla según tus necesidades. Además, es posible que no sea la solución más eficiente para valores grandes de
n
ycolors
, pero debería funcionar correctamente para entradas más pequeñas.