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 [email protected].
