# Tough interview question. Inputs welcome

A Bhattacharya

Ranch Hand

Posts: 125

posted 8 years ago

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?

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

Ranch Hand

Posts: 628

posted 8 years ago

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

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

Helping hands are much better than the praying lips

Gagan Indus

Ranch Hand

Posts: 346

posted 8 years ago

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 neededGagan (/^_^\) 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>

Gagan Indus

Ranch Hand

Posts: 346

posted 8 years ago
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>

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.

Ramboo's reply seems could do the trick.

A Bhattacharya

Ranch Hand

Posts: 125

posted 8 years ago

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 ]

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

Ranch Hand

Posts: 628

A Bhattacharya

Ranch Hand

Posts: 125

posted 8 years ago

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 ]

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