es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Generar una pulsera de longitud n utilizando un conjunto de colores dados – JavaScript

01 Aug, 2023 Programación

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.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    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:

    function generateBracelet(colors, n) {
  const bracelet = [colores[0]];
  let soluciones = [];

  function backtrack() {
    if (bracelet.length === n) {
      soluciones.push([...bracelet]); // Encontró una solución válida
      return;
    }

    for (let i = 0; i < colors.length; i++) {
      if (bracelet[bracelet.length - 1] !== colors[i]) { // Verificar cuentas adyacentes
        let threeBeads = `${bracelet.slice(-2).join('')}${colors[i]}`;
        if (!bracelet.includes(threeBeads)) { // Verificar patrón repetitivo
          bracelet.push(colors[i]);
          backtrack(); // Intentar agregar la siguiente cuenta
          bracelet.pop(); // Retroceder y probar con el siguiente color
        }
      }
    }
  }

  backtrack();
  return soluciones.length ? soluciones[0] : false; // Devolver la primera solución válida o false
}

console.log(generateBracelet(["R", "G", "B", "Y"], 8)); // imprime ["R", "G", "B", "Y", "R", "G", "Y", "B"]

    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 y colors, pero debería funcionar correctamente para entradas más pequeñas.

Comments are closed.