// This function returns the number of hints required to
// determine the order of the cards.
// Parameter int c[n] specifies n cards which are provided
// in an unknown order. Each card is represented as a 10-bit field
// with two bits set, one representing the color of the card and the
// other representing the value. The low 5 bits (value 1-16) indicate
// the color, and the next 5 bits (value 32-512) indicate the value.
// The function requires an array int bits[1024] where bits[i] contains
// the number of bits set in the value i.
//
// This works on the principle that there must be at least one hint which
// distinguishes any pair of cards. If there is not, those two cards could
// be switched and the hints would not indicate a difference.
int minHints(int *c, int n)
{
int pairs[300];
int p = 0;
int i, j;
int min = 8;
for(i = 1; i < n; ++i)
for(j = 0; j < i; ++j)
pairs[p++] = c[i] ^ c[j];
for(i = 0; i < 1024; ++i)
if (bits[i] < min)
{
for(j = 0; j < p; ++j)
if ((i & pairs[j]) == 0) break;
if (j == p) min = bits[i];
}
return min;
}
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].
