Here is a fairly simple way to find a solution. Make a list of each pair of the n cards which have been selected. This list can include up to 300 pairs. Represent each card as a 10-bit value where each bit represents one particular color or value. Thus, each card will have two bits set. Each pair is the bitwise XOR (^) of the values of the card, indicating which hints will distinguish those two cards. Now try all 1024 possible combinations of hints by iterating i from 0 to 1023. If the bitwise AND (&) of i with any value in the pair list is zero, that combination of hints would not distinguish those cards. So a valid combination of hints has a non-zero bitwise AND with all values in the pairs list. Find the value of i with the fewest bits which meets this condition.
Don On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote: > > One of my friend posted this question to me and I am unable to get > anywhere. Could you guys please help > > A game of cards has 5 colors and 5 values. Thus a total of 25 cards are > possible. Player 1 will choose n cards and tell you exactly , what all > cards he has. Then he will spread cards in front of you with face downwards > in random fashion. > So you know the card values but not the ordering. Player 1 will provide > you 2 types of hints , he can tell you what all cards have some color or he > can tell you what all cards have some value. you need to tell the ordering > of cards with the help of these hints. > challenge is to find out minimum number of hints to be provided by player > 1 so that you are able to make it for all cards. > > e.g. say player chosen n=5 cards > and tells you the values > > B1 Y1 W1 G1 R1 > > he can either tell you that what all cards are 1 (in this case all cards) > or can tell you different color like leftmost is color 'B" and next after > 'Y' and so on. So minimun hints in this case is 4 > > > another example > if n=4 > G4 R3 R4 B3 > > Here he can tell you the card 1st and 3rd are of values 4 and cards 2 and > 3 are of color 'R'. This will be sufficient to infer the card values. so > answer is 2 > > > I am not interested in code , please suggest plain simple algorithms, if > possible with arguments that why it is correct ? > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
