# Tough interview question. Inputs welcome

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?

**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

Gagan (/^_^\) SCJP2 SCWCD IBM486 <br />Die-hard JavaMonk -- little Java a day, keeps you going.<br /><a href="http://www.objectfirst.com/blog" target="_blank" rel="nofollow">My Blog</a>

Ramboo's reply seems could do the trick.

Gagan (/^_^\) SCJP2 SCWCD IBM486 <br />Die-hard JavaMonk -- little Java a day, keeps you going.<br /><a href="http://www.objectfirst.com/blog" target="_blank" rel="nofollow">My Blog</a>

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 ]

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 ]

Gabriel

Software Surgeon