Thread: Necklace (combinatorics)

Necklace maker 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


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

Input Format
The first line contains an integer representing b.
The second line contains an integer representing g.
The third line contains an integer representing r.
The fourth line contains an integer representing y.

Constraints
0 <= b, g, r, y <= 3000
At least one of b, g, r, y is greater than 0

Output Format
A single integer which is the answer to the problem.

Well the first part of this is a maths problem, not a programming problem.

Do you understand enough maths to solve the simple cases on paper?

What data structures have you considered that might help?

FWIW, combinatorics usually means a clever algorithm, not a brute force search of some impossibly large data structure.

One straightforward way would be to solve it recursively, and of course, memoise the sub-problems or solve it bottom-up dynamically.

Originally Posted by Avinash2408

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

I would start by writing the rules in the form of
A yellow ruby can be proceeded by ...

And, if you can use recursive functions; I would think about how to solve it that way.

Tim S.

I would also solve the problem for 1 each of each color and see what that gives you.

Tim S.

One recursive solution, that basically considers all possible arrangements, would look something like this:

Your parameters should include the last color used and the number of rubies left for each color.

Based on the last ruby's color, you decide which color is next, call the function recursively by updated parameters, and return a maximum among options.

Yes, you start with pencil and paper and say 2 of each colour and practice making longest chains.
From your practice, you start to develope ideas of how you solve the problem with an algorithm.

Only then can you think about code.

Code:

Transition graph:
   _
  | |
  '-B-->R
    ^  /|
    | / |
    |/  +
    Y<--G-,
        |_|


  Number of        Longest
  B   R   G   Y    necklace
 10   0   0   0    10
  0  10   0   0     1
  0   0  10   0    10
  0   0   0  10     1
 10  10  10  10    40
  5  10  10  10     ?
 10   5  10  10   ...   interesting
 ...

I take it the plus sign "+" is a down arrow.

Tim S.

Originally Posted by john.c

Code:

Transition graph:
   _
  | |
  '-B-->R
    ^  /|
    | / |
    |/  +
    Y<--G-,
        |_|


  Number of        Longest
  B   R   G   Y    necklace
 10   0   0   0    10
  0  10   0   0     1
  0   0  10   0    10
  0   0   0  10     1
 10  10  10  10    40
  5  10  10  10     ?
 10   5  10  10   ...   interesting
 ...