How to arrange beads in a necklace so that rules are met | Formula

Question

I am trying to solve the following problem programatically:

It is the wedding day of Samantha, the beautiful princess of Byteland. Her fiance Moore is planning to gift her an awesome ruby necklace. Moore has currently b -blue rubies, g -green rubies, r-red rubies and y -yellow rubies. He has to arrange the rubies next to each other in a straight line to make the necklace. But, there are a couple of rules to be followed while making this necklace:

•           A blue ruby should be followed by either a blue ruby or a red ruby

•           A green ruby should be followed by either a green ruby or a yellow ruby

•           A red ruby should be followed by either a green ruby or a yellow ruby

•           A yellow ruby should be followed by either a blue ruby or a red ruby

•           If it is possible, we should always start a necklace with a blue or a red ruby


Can you tell what is the maximum possible length of the necklace that Moore can make. The length of a necklace is the number of rubies in it.

I am not a maths major, so request a hint here.

Answer 1

Let $f(r,b,g,y)$ be the longest necklace you can make given $r,b,g,y$ beads of each color. To compute this, let's define some helper functions:

• $B(r,b,g,y)$ is the longest necklace whose first bead is blue.
• $G(r,b,g,y)$ is the longest necklace whose first bead is green.
• $R(r,b,g,y)$ is the longest necklace whose first bead is red.
• $Y(r,b,g,y)$ is the longest necklace whose first bead is yellow.

Note that $f(r,b,g,y)$ is the maximum of these functions.

Using the given rules, you can compute each of these functions recursively in terms of each other. For example,

$$ B(r,b,g,y) = 1+ \max(B(r,b-1,g,y),R(r,b-1,g,y)) $$ since a blue ruby is followed by a blue or red one, and one $b$lue bead has been used up.

You would also need to come up with the base cases of the recursion. Furthermore, this will be quite slow unless you use memoization or dynamic programming, which is beyond the scope of this site.

Answer 2

The first 4 coloring rules mean the necklace must be of this form:

[($0$ or more blues)($1$ red)($0$ or more greens)($1$ yellow)] repeated any number of times

From this the answer can be directly derived:

• If $r \ge 1,$ then (1) all blues can be used, (2) all greens can be used, (3) the number of reds used $= \max(r, y+1)$, (4) the number of yellows used $=\max(r, y)$. Max total length $=b + \max(r,y+1) + g + \max(r,y)$.

• If $r = 0$ and $b> 0$, then the 5th requirement means we can only make a pure blue necklace. Max total length $=b$.

• If $r =0$ and $b=0$, then all greens can be used, followed by 1 yellow. Max total length $=g + \max(1, y)$.