Create a customized bracelet with a specified number of colors in JavaScript

Question

Create a customized bracelet with a specified number of colors in JavaScript

I encountered an interesting challenge recently.

The task was to create a bracelet of length n using a set of specified colors, following certain conditions:

No two adjacent beads should have the same color (e.g., R R).
A pattern of three consecutive beads should not be repeated in the bracelet (e.g., R G B Y R G B, R G R G R).

Given input - colors = ["R", "G", "B", "Y"], n = 8
Expected output - ["R", "G", "B", "Y", "R", "G", "R", "Y"]
If it is not possible to form a bracelet of length n, the function should return false.

After pondering on the problem, I came up with the following solution:

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"]

This led to the inevitable question: "Is there a way to optimize this solution?"

I am still contemplating the best approach to tackle this problem.
Any suggestions or alternative solutions would be greatly appreciated.

javascript arrays algorithm

Answer 1

Answer №1

One method to consider is evaluating each position for allowable colors and then selecting one (or all, for multiple bracelets) that can still be positioned, and proceeding to the following position.

This solution utilizes a recursive generator function, allowing us to opt for obtaining the initial result, the first n results, or all outcomes through some wrapper functions.

In addition, we create a wrapping function (makeBracelet) to retrieve the first (or false), which aligns with your requirements.

We also establish another wrapping function (allBracelets) that relies on the auxiliary functions cycles and combineCycles to highlight that since they form loops, "ABCDE" is likely equivalent to "BCDEA". We utilize these helpers to merge these cycles into a single representation. (We also carry out the reverse operation with "EDCBA".)

Lastly, by employing the helper function partialShuffle (which initiates a Fisher-Yates Shuffle), we craft a randomBracelets function for choosing a specified number of distinct random bracelets from the entire collection.

function * bracelet (n, cs, current = [], triplets = []) {
  if (current .length >= n) {
    yield current .join ('')
  } else {
    const allowed = cs .filter (c => 
      c != current .at (-1)
      && (current .length != n - 1 || c !== current[0]) 
      && ! triplets .includes (`${current .at (-2)}${current .at (-1)}${c}`)
    )
    for (let c of allowed) { 
      yield * bracelet (n, cs, current .concat (c),
        current .length > 1 
          ? triplets .concat (`${current .at (-2)}${current .at (-1)}${c}`) 
          : triplets
      )
    }
  }
}


const makeBracelet = (n, cs) => 
  bracelet (8, ['R', 'G', 'B', 'Y']) .next () .value || false


const cycles = (xs) => 
  Array .from (xs, (_, n) => xs .slice (-n)  .concat (xs .slice (0, -n)))

const combineCycles = (xss) =>
  [... new Set (Object .values (xss .reduce (
    (a, xs) => xs in a ? a : [...cycles (xs), ...cycles ([...xs] .reverse () .join (''))] .reduce ((a, x) => ((x in a) || (a[x] = xs), a), a)
    // (a, xs) => xs in a ? a : cycles (xs) .reduce ((a, x) => ((x in a) || (a[x] = xs), a), a)
    , {}
  )))]

const allBracelets = (n, cs) =>
  combineCycles ([...bracelet (n, cs)])
  // [...bracelet (n, cs)]

const partialShuffle = (n) => (xs, i = Math.floor (Math .random () * xs .length)) =>
  n <= 0 || n > xs .length || xs .length == 0
    ? []
    : [xs[i], ... partialShuffle (n - 1) ([... xs .slice (0, i), ... xs .slice (i + 1])]

const randomBracelets = (n, cs, count) => 
  partialShuffle (count) (allBracelets (n, cs))

console .log ('Colors: ["R", "G", "B", "Y"]:')

console .log ('One length-8 bracelet:', makeBracelet (8, ['R', 'G', 'B', 'Y']))

console .log ('Count length-8 bracelets:', allBracelets (8, ['R', 'G', 'B', 'Y']) .length)

console .log ('Ten random length-8 bracelets:', randomBracelets (8, ['R', 'G', 'B', 'Y'], 10))

console .log ('All length-5 bracelets:', allBracelets (5, ['R', 'G', 'B', 'Y']))

.as-console-wrapper {max-height: 100% !important; top: 0}

We validate acceptable colors by filtering them to ensure we don't repeat the previous color, exclude matching the initial one at the end, or encounter any identified triplet patterns. By recursively incorporating our permitted characters and updating the list of disallowed triplets, we proceed.

If bracelets lack cyclic properties, the invocation of combineCycles within allBracelets can be omitted. In case they exhibit cyclic but unidirectional characteristics ("ABCDE" differs from "EDCBA"), modifying the commented line inside

combineCycles</code enables toggling between scenarios.</p>
<p>An intriguing adaptation involves integrating cycle-testing within the generator function to prevent redundant bracelets. While feasible, it awaits further exploration at a later time.</p>
<p>Finally, although elegant, the <code>partialShuffle

function may risk reaching recursion limits, warranting consideration for an iterative alternative if contemplating selections among vast numbers of bracelets.

Answer 2

One method to consider is evaluating each position for allowable colors and then selecting one (or all, for multiple bracelets) that can still be positioned, and proceeding to the following position.

This solution utilizes a recursive generator function, allowing us to opt for obtaining the initial result, the first n results, or all outcomes through some wrapper functions.

In addition, we create a wrapping function (makeBracelet) to retrieve the first (or false), which aligns with your requirements.

We also establish another wrapping function (allBracelets) that relies on the auxiliary functions cycles and combineCycles to highlight that since they form loops, "ABCDE" is likely equivalent to "BCDEA". We utilize these helpers to merge these cycles into a single representation. (We also carry out the reverse operation with "EDCBA".)

Lastly, by employing the helper function partialShuffle (which initiates a Fisher-Yates Shuffle), we craft a randomBracelets function for choosing a specified number of distinct random bracelets from the entire collection.

function * bracelet (n, cs, current = [], triplets = []) {
  if (current .length >= n) {
    yield current .join ('')
  } else {
    const allowed = cs .filter (c => 
      c != current .at (-1)
      && (current .length != n - 1 || c !== current[0]) 
      && ! triplets .includes (`${current .at (-2)}${current .at (-1)}${c}`)
    )
    for (let c of allowed) { 
      yield * bracelet (n, cs, current .concat (c),
        current .length > 1 
          ? triplets .concat (`${current .at (-2)}${current .at (-1)}${c}`) 
          : triplets
      )
    }
  }
}


const makeBracelet = (n, cs) => 
  bracelet (8, ['R', 'G', 'B', 'Y']) .next () .value || false


const cycles = (xs) => 
  Array .from (xs, (_, n) => xs .slice (-n)  .concat (xs .slice (0, -n)))

const combineCycles = (xss) =>
  [... new Set (Object .values (xss .reduce (
    (a, xs) => xs in a ? a : [...cycles (xs), ...cycles ([...xs] .reverse () .join (''))] .reduce ((a, x) => ((x in a) || (a[x] = xs), a), a)
    // (a, xs) => xs in a ? a : cycles (xs) .reduce ((a, x) => ((x in a) || (a[x] = xs), a), a)
    , {}
  )))]

const allBracelets = (n, cs) =>
  combineCycles ([...bracelet (n, cs)])
  // [...bracelet (n, cs)]

const partialShuffle = (n) => (xs, i = Math.floor (Math .random () * xs .length)) =>
  n <= 0 || n > xs .length || xs .length == 0
    ? []
    : [xs[i], ... partialShuffle (n - 1) ([... xs .slice (0, i), ... xs .slice (i + 1])]

const randomBracelets = (n, cs, count) => 
  partialShuffle (count) (allBracelets (n, cs))

console .log ('Colors: ["R", "G", "B", "Y"]:')

console .log ('One length-8 bracelet:', makeBracelet (8, ['R', 'G', 'B', 'Y']))

console .log ('Count length-8 bracelets:', allBracelets (8, ['R', 'G', 'B', 'Y']) .length)

console .log ('Ten random length-8 bracelets:', randomBracelets (8, ['R', 'G', 'B', 'Y'], 10))

console .log ('All length-5 bracelets:', allBracelets (5, ['R', 'G', 'B', 'Y']))

.as-console-wrapper {max-height: 100% !important; top: 0}

We validate acceptable colors by filtering them to ensure we don't repeat the previous color, exclude matching the initial one at the end, or encounter any identified triplet patterns. By recursively incorporating our permitted characters and updating the list of disallowed triplets, we proceed.

If bracelets lack cyclic properties, the invocation of combineCycles within allBracelets can be omitted. In case they exhibit cyclic but unidirectional characteristics ("ABCDE" differs from "EDCBA"), modifying the commented line inside

combineCycles</code enables toggling between scenarios.</p>
<p>An intriguing adaptation involves integrating cycle-testing within the generator function to prevent redundant bracelets. While feasible, it awaits further exploration at a later time.</p>
<p>Finally, although elegant, the <code>partialShuffle

function may risk reaching recursion limits, warranting consideration for an iterative alternative if contemplating selections among vast numbers of bracelets.

Answer 3

Answer №2

One crucial aspect of this exercise is the algorithm, as emphasized in the post. The C++ code included at the end serves purely to showcase the solution and demonstrate the effectiveness of the algorithm testing process.

There exist numerous valid sequences that meet the specified constraints.
Given a number k representing different letters, it can be shown that the length of each solution cannot exceed k*(k-1)^2 + 2.

Hence, the challenge lies in generating a specific sequence of maximum length systematically.

The suggested approach involves an incremental method: starting with a correct sequence containing k letters, we proceed by adding one additional letter.

To achieve this, two new sequences are appended to the previous step's generated sequence:

If the new letter is z, for each letter a from the previous sequence, we append "za".
For every pair ab formed by two letters from the prior sequence, we add "zab".

To prevent overlap between the two added parts, the resulting "zab" triplets must be interleaved throughout.

To validate the method, the provided C++ code ensures that the generated sequence adheres to the constraints (verification conducted after complete generation).

The following snippet demonstrates the output of the code:

number of letters = 5
ababcacbcbacabdadbdcdcadcbdbadacdbcdabeaebecededaedbedcecaecbebaeadebdecdeacebceab
size max = 82 and we get a size of 82
Checked!

#include <iostream>
#include <vector>
#include <string>
#include <set>

// Function to verify bracelet compliance with rules
bool check_bracelet (const std::string &guirlande) {
    // Implementation details omitted for brevity
}

// Generate a bracelet of maximum size = 2 + k*(k-1)^2 
std::string bracelet (const std::vector<std::string> &colors) {
    // Implementation details omitted for brevity
}

int main() {
    // Main function logic - includes test data for demonstration purposes
}

Answer 4

One crucial aspect of this exercise is the algorithm, as emphasized in the post. The C++ code included at the end serves purely to showcase the solution and demonstrate the effectiveness of the algorithm testing process.

There exist numerous valid sequences that meet the specified constraints.
Given a number k representing different letters, it can be shown that the length of each solution cannot exceed k*(k-1)^2 + 2.

Hence, the challenge lies in generating a specific sequence of maximum length systematically.

The suggested approach involves an incremental method: starting with a correct sequence containing k letters, we proceed by adding one additional letter.

To achieve this, two new sequences are appended to the previous step's generated sequence:

If the new letter is z, for each letter a from the previous sequence, we append "za".
For every pair ab formed by two letters from the prior sequence, we add "zab".

To prevent overlap between the two added parts, the resulting "zab" triplets must be interleaved throughout.

To validate the method, the provided C++ code ensures that the generated sequence adheres to the constraints (verification conducted after complete generation).

The following snippet demonstrates the output of the code:

number of letters = 5
ababcacbcbacabdadbdcdcadcbdbadacdbcdabeaebecededaedbedcecaecbebaeadebdecdeacebceab
size max = 82 and we get a size of 82
Checked!

#include <iostream>
#include <vector>
#include <string>
#include <set>

// Function to verify bracelet compliance with rules
bool check_bracelet (const std::string &guirlande) {
    // Implementation details omitted for brevity
}

// Generate a bracelet of maximum size = 2 + k*(k-1)^2 
std::string bracelet (const std::vector<std::string> &colors) {
    // Implementation details omitted for brevity
}

int main() {
    // Main function logic - includes test data for demonstration purposes
}

Create a customized bracelet with a specified number of colors in JavaScript

Answer №1

Answer №2

Similar questions

Altering the context of 'this' with the bind method in JavaScript

Incorporate PHP form and display multiple results simultaneously on a webpage with automatic refreshing

There seems to be an issue with rendering or redirecting in Jade files, the routes folder, and server/app.js

Is the form being submitted with the href attribute?

Why does this code show that 'Array' is not the same as 'Array<T>'?

How to deactivate or modify the href attribute of an anchor element using jQuery

Creating Functions with HTML, CSS, and Javascript

Recover Checkmark Status from Data

Issue with Empty Date Time Format in Vue2 Date-Picker

Monitor Socket IO for client disconnection events

Guidance on invoking the navigate function from a component displayed at the highest level of rendering

Refreshing canvas with new javascript content following an ajax request

I've encountered a peculiar error that is new to me while using bootstrap and javascript. Can anyone shed light on what this error signifies?

Creating a conditional npm script that depends on the output of another: a step-by-step guide

Displaying errors above the table. Executing ng-repeat in AngularJS

Pager.js utilizing Deferred Bindings

Using Angular's ng-switch directive within a select dropdown option

Google's geolocation.getCurrentPosition function fails to function properly on mobile devices after the page is refreshed

Error in the Syntax of Project Image Slider

Sending form data to a CFC asynchronously in Coldfusion