Generate a bracelet of length n using set of given colors - javascript

Question

I was asked to solve the following problem.

Generate Bracelet of length n using set of given colors

Conditions

• No two adjacent items should have same colors ex.; R R
• Should not repeat any three beads pattern in bracelet.
  ex.; R G B Y R G B,
  ex2.; R G R G R

Input - colors = ["R", "G", "B", "Y"], n = 8
Output - ["R", "G", "B", "Y", "R", "G", "R", "Y"]
In case, if it could not able to form bracelet of length n, it should return false.

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

Then the next obvious question came up is "can you optimise?"

I am still wondering what could be best approach to solve this problem.
Please enlighten me to solve this in better way.
Any leads or solutions will be much appreciated.

Answer 1

What is important in this kind of exercise is the algorithm. The post focuses on it. The code (C++) at the end is only provided to illustrate the solution, and to prove that the algorithm has been tested effectively.

There are many possible sequences satisfying the constraints.
For a given number k of different letters, it is easy to show that each solution must be shorter or equal to k*(k-1)^2 + 2.

Therefore, the problem is to be able to generate a particular maximum length sequence in a systematic manner.

The proposed method is incremental: having generated a correct sequence with k letters, we generate a sequence by adding one letter.

for that, we add two sequences to the one generated at the previous step

1. If the new letter is z, and for each letter a of the previous sequence, we add "za"

2. For each pair ab constituted by two letters of the previous sequence, we add "zab".

In order to avoid imitations between the two added parts, the triples "zab" added must be interleaved.

To check the procedure, the following code finally checks that the generated sequence satisfy the constraints (after complete generation, only to validate the procedure).

The following code is in C++ (sorry, don't know javascript).

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>

//  Check if the bracelet follows the rule
bool check_bracelet (const std::string &guirlande) {
    
    int n = guirlande.size();
    for (int i = 0; i < n-1; ++i) {
        if (guirlande[i] == guirlande[i+1]) {
            std::cout << "character repeated: " << guirlande[i] << std::endl;
            return false;
        }
    }
    std::set<std::string>  collect;
    for (int i = 0; i < n-2; ++i) {
        std::string s = {guirlande[i], guirlande[i+1], guirlande[i+2]};
        auto search = collect.find (s);
        if (search != collect.end()) {
            std::cout << "triplet found twice: " << s << std::endl;
            return false;
        }
        collect.insert(s);
    }
    return true;
}


//  Generate a bracelet of the maximum size = 2 + k*(k-1)^2 

std::string bracelet (const std::vector<std::string> &colors) {
    std::string guirlande;
    int k = colors.size();
    if (k == 0) return "";
    if (k == 1) return {colors[0]};
    guirlande = colors[0] + colors[1] + colors[0] + colors[1];
    
    for (int step = 2; step < k; ++step) {
        //for (int i = step-1; i >= 0; --i) {
        for (int i = 0; i < step; ++i) {
            guirlande += colors[step] + colors[i];
        }
        
        //for (int i = 0; i < step - 1; ++i) {
            //for (int j = i+1; j < step; ++j) {
        std::string temp;
        for (int i = step-1; i >= 1; --i) {
            //for (int j = i-1; j >= 0; --j) {
            for (int j = 0; j < i; ++j) {
                guirlande += colors[step] + colors[i] + colors[j];
                //guirlande += colors[step] + colors[j] + colors[i];
                temp += colors[step] + colors[j] + colors[i];
            }
        }
        guirlande += temp;
    }
    
    return guirlande;
}

int main() {
    std::vector<std::string> colors = {"a", "b", "c", "d", "e"};
    auto ans = bracelet (colors);
    int k = colors.size();
    int nmax = k*(k-1)*(k-1) + 2;
    if (k <= 1) nmax = 1;
    std::cout << "number of letters = " << k << std::endl;
    std::cout << ans << std::endl;
    std::cout << "size max = " << nmax << " and we get a size of " << ans.size() << std::endl;
    auto check = check_bracelet (ans);
    if (check) std::cout << "Checked!\n";
    
    return 0;
}

Answer 2

One approach would be to check at every position which colors are allowed and then choose one (or for building multiple bracelets, choose all) which can still be placed, and continuing to the next position.

This implementation uses a recursive generator function, so that we can choose to get the first result, or the first n results, or all of them in some wrapper functions.

We then write a wrapper function (makeBracelet) to get the first (or false), which seems to be what you're looking for.

We also write a wrapper function (allBracelets) which depends on the helpers cycles and combineCycles to note that since they are loops, "ABCDE" is probably the same bracelet as "BCDEA". We use the helpers to combine these cycles into a single representative. (We also do the reverse "EDCBA".)

Finally, using the helper partialShuffle (which does the beginning of a Fisher- Yates Shuffle) to write a randomBracelets function to choose a fixed number of distinct random bracelets out of the whole list.

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 check for allowed colors by filtering the colors to make sure we don't match the previous color, or if we're at the end that we don't match the first one, or that we don't match any of a running list of triplets. We recur adding our allowed character and adding the most recent triplet to the list of disallowed triplets.

If bracelets are not cyclic, then we can remove the call to combineCycles in allBracelets. If they are cyclic but unidirectional ("ABCDE" is different from "EDCBA"), then you can toggle which line is commented inside combineCycles.

An interesting variation would be to do the cycle-testing inside the generator function -- and prevent multiple essentially identical bracelets from showing up. It doesn't sound hard, but I'm out of time now.

Finally, partialShuffle is elegant, but could run into recursion limits, and might be better replaced with an iterative version if you're ever going to want to randomly select thousands of bracelets.