Tough interview question. Inputs welcome

[A Bhattacharya]

You are asked to design 10 flags with vertical stripes using three colors: blue, orange, yellow. You are asked not to have two neighboring stripes of the same color. You are also asked not to have yellow and orange stripes next to each other as it doesn't look nice. Your goal to minimize the number of stripes I need to use. So, you can make 3 different one-striped flags. You can make 4 different two-striped flags: blue-yellow, blue-orange, yellow-blue, orange-blue. You can make 6 different three-striped flags: blue-yellow-blue, yellow-blue-yellow, orange-blue-orange, blue-orange-blue, orange-blue-yellow, yellow-blue-orange. That is, you can make 13 different flags using 3 stripes at most.
Your task is, given the number of flags and the details of colors that may not be adjacent to each other (a color always has atleast one forbidden neighbor namely itself),return the minimum number of stripes you need to design the given number of different flags using at most that amount of stripes.

My original bruteforce solution was to go level by level increasing the number of stripes used one at a time, and after each level completion checking if the total number of flags has been reached. But this approach takes hours on the computer to execute when the number of flags is huge, say 10^17. It is required that the solution be found in 2 seconds. My feeling is that we need to find some kind of series progression that will vary from input to input. Once the series is found we condense it into a formula and use it to solve the problem. I tried with some sample inputs but no luck finding any such series (even for the example given above). Any clues?

[Rambo Prasad]

I think you should solve something like the equation below...
N1-Number of color choices.(3)
N2-Number of color which cannot co exist(2)

N1P1+N1P2+..+.N1Pn - (N2P1+N2P2+..+..N2PN2)>=10

Solve this equation to find n

[Gagan Indus]

Ok here is my try -- would something like this work?

N == total number of available colors
F == total number of colors that can't be next to each other
C == total number of flags needed

set count = 0;
for s=1 until count < C
  count += N * power(N, s-1) ;  // total flags possible with stripes s
  if (s>1)
    count -= power(N, s-2) * F * (F-1) ; // decrement forbidden flags
  end if
end for
 
return s;
 

[Gagan Indus]

Never mind i read your question again and it appears you already tried what i was suggesting.

Ramboo's reply seems could do the trick.

[A Bhattacharya]

I can't understand either of your answers.
In the given example, the forbidde combinations are BB, OO, OY, YY, YO which are 5 in number.
For 3 stripes, we have a total of n*n*n = 27 permutations of which we need to eliminate the invalid ones.
From the 5 invalid combinations given, we need to construct invalid combinations with 3 stripes.
From BB we get: BBB, OBB, BBO, YYB, BBY
From OO we get: BOO, OOB, OOO, YOO, OOY
From OY we get: BOY, OYB, OOY*,OYO, YOY, OYY
From YY we get: BYY, YYB, OYY*,YYO,YYY
From YO we get: BYO, YOB, OYO*,YOO*,YYO*,YOY*

The ones marked * are those that already have been counted; so we get 21 invalid ones. Hence only 27-21=6 are valid ones with 3 stripes.
Can you explain how your formula is working along these lines?
[ May 12, 2008: Message edited by: A Bhattacharya ]

[Rambo Prasad]

Bhattacharya,

My solution is wrong...I didn't take into consideration the repetition of colors...

Can the flag have more than 3 strips or is 3 the max
[ May 12, 2008: Message edited by: Rambo Prasad ]

[A Bhattacharya]

Yes it can have more than 3; the question is to find teh minimum no of stripes required to be able to form the required no of flags, in this example 10. I was demonstrating (as an intermediate step in the solution) how we might find the flags that can be formed using 3 stripes.

[Gabriel Claramunt]

Hmm... graphs are a fundamental tool for most of Computer Science problems (or they're my hammer )
One possible solution is create a graph where the nodes are the stripe colors and the arcs are the allowed pair combinations. Now the problem is to find the shortest n paths (=number of flags) visiting each node one time at most (i.e using each color zero or one time).
I need to assume that you have a known number of colors and the order matters (i.e. YB is a different flag than BY).
If flags can have 1 stripe (just one color in the whole flag) you start counting the paths of size 1 (will be the number of nodes), otherwise, start with the paths of length 2.
Doesn't seem to be expensive as the number of colors is low, but probably more optimizations can be done (i.e. the longest path from a node will give [sumatory of path length] different flags).
What do you guys think?


(I realized you can repeat colors as long as they're not adjacent... this removes the condition that each vertex must be visited only once at most... doesn't seem to affect the algorithm, though)
[ May 15, 2008: Message edited by: Gabriel Claramunt ]