30 replies to this topic

[EventHorizon]

I'm not going to get the minimum, but let's try a starting guess.

Spoiler for Hmm.

First, guess black for all. This tells you the number of black and red cards.

Then guess black for the first half and red for the second half. This lets you determine how many blacks and reds are in the second half of the deck, and consequently how many are in the first half of the deck.

Example: Let's suppose we get (total black) correct the first time. There are that many black cards in the whole deck.

Then we get Y correct. This equals the number of black cards in the first half (call that B1) + the number of red cards in the second half. The number of red cards in the second half must equal 13 - B2, where B2 is the number of black cards in the second half of the deck. So we have Y = B1 + 13 - B2, and (total black) = B1 + B2. This gives us:

(total black) + Y = 2B1 + 13

B1 = [(total black) + Y - 13]/2

Then we can get B2 (and R1 and R2).

That's four questions so far.

Using a similar trick can get us the number of blacks in the first and second "quarters" of the deck. (First 6 and 7 cards). Repeating it again can get us the number of blacks in the third and fourth quarters (Last 6 and 7 cards).

Hmm... all these odd numbers look bad. A 14/12 initial split is probably better. A single question can identify the colors of one pair of cards using this kind of technique, but can't get the colors of three cards, as far as I can tell.

I'm guessing the answer's around 13-15, but I wonder if there's some sneaky combination of staggered tests (test even cards, test first half, test first and third quarters, etc) that somehow gives an answer with certainty.

Spoiler for Does that really help the worst case scenario?

Lets say there are 4 cards to guess, and there are 2 red and 2 black.



It still ends up with a worst case scenario of #ofcards + 1 guesses, which is the same as the approach given by Time Out. Yes, the average case is improved, but the worst case is unchanged.

Or did I misinterpret your approach?

If this is what you thought of, I thought of it first thing too

[EventHorizon]

Spoiler for

14... and once I figure out how/why it works, I'll let you know. (cmon computer, tell me the method, not just a bunch of numbers!)

This isn't necessarily the limit, but the result of a greedy search that took 14 guesses to resolve to a single guessed possibility (assuming the response given to a guess was always the one that left the most possibilities). So it might be 15, but probably not 16. Unless a greedy search doesn't produce the best strategy, which is entirely possible, then it might be 12 or 13. So I guess I'm saying 14+/-2.

[phil1882]

i belive witchofsecrets solution works better for a larger number of cards.

Spoiler for

lets take the example of 6 cards, with a solution of 100011.
000000 3 so 3 red, 3 black
000111 4 so 2 of the red guesses are correct.
001011 4 so the bottom half is correct, only need the top half solved
010011 4
100011 correct in 5 guesses.
with 26 i belive it will take 16 guesses tops to get a solution using this method.
also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

[phil1882]

Spoiler for solution in 9?

looking further at witchofsecrets method, i belive i have derived a method that solves it in 9 guesses 60% of the time, with a 40% chance of requireing 10. to demonstrate this idea further, lets take the case of 32 colors to guess.
the hardest string i can find is... 10010110011010010110100110010110
which can be gotten in 10 guesses.
00000000000000001111111111111111 16
00000000111111110000000011111111 16
00001111000011110000111100001111 16
00110011001100110011001100110011 16
01010101010101010101010101010101 16
10011001100110011001100110011001 16
01011010010110100101101001011010 16
and so on.
in general, the number of trials nessicary is 2*log(2) n.

[Assassin.MTS]

this is my first Post in the forum

Spoiler for first try

I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops   I don't find a good answer... but I thing there is something right in this way   

[EventHorizon]

i belive witchofsecrets solution works better for a larger number of cards.

Spoiler for

lets take the example of 6 cards, with a solution of 100011.
000000 3 so 3 red, 3 black
000111 4 so 2 of the red guesses are correct.
001011 4 so the bottom half is correct, only need the top half solved
010011 4
100011 correct in 5 guesses.
with 26 i belive it will take 16 guesses tops to get a solution using this method.
also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

Spoiler for problems I see

First, since it is not a power of 2, you get a little more information from the second guess by virtue of the fact that the response cannot evenly divide the colors (this is where this method happens to get the extra guess reduction).

Second, since you chose the string beforehand, you are simply showing a special case and not the worst case scenario. For instance, for the guess of 010011, if the response was 2, it would leave 2 possibilities. This would require 1 more guess for the worst case (in this branch of possibilities).

These are the possibilities before that guess 001110, 001101, 100011, 010011. So the bottom half was not necessarily correct at that point.

Edit:

Spoiler for Also

Looking at equivalence classes, it's easy to see that the first guess will give the same amount of useful information regardless of what is guessed. So stick with 0's, since it gives a simple human-readable answer (ie, x number of this color).

Edited by EventHorizon, 01 June 2012 - 02:16 AM.

[EventHorizon]

i belive witchofsecrets solution works better for a larger number of cards.

Spoiler for

lets take the example of 6 cards, with a solution of 100011.
000000 3 so 3 red, 3 black
000111 4 so 2 of the red guesses are correct.
001011 4 so the bottom half is correct, only need the top half solved
010011 4
100011 correct in 5 guesses.
with 26 i belive it will take 16 guesses tops to get a solution using this method.
also, i think starting off guessing half red, half black, will reduce the number of necessary guesses by 1.

Spoiler for A little more to say on this one

As WitchOfSecrets initially explained, he had separate tests for determining "the number of blacks in the first and second 'quarters' of the deck" and "the third and fourth quarters." So he had tests like 0000111100000000 and 0000000000001111. This initial formulation was what I responded to initially.

Spoiler for solution in 9?

looking further at witchofsecrets method, i belive i have derived a method that solves it in 9 guesses 60% of the time, with a 40% chance of requireing 10. to demonstrate this idea further, lets take the case of 32 colors to guess.
the hardest string i can find is... 10010110011010010110100110010110
which can be gotten in 10 guesses.
00000000000000001111111111111111 16
00000000111111110000000011111111 16
00001111000011110000111100001111 16
00110011001100110011001100110011 16
01010101010101010101010101010101 16
10011001100110011001100110011001 16
01011010010110100101101001011010 16
and so on.
in general, the number of trials nessicary is 2*log(2) n.

Spoiler for Thoughts on this method

WitchOfSecrets did mention staggered tests, which is what your approach consists of. This does, in fact, improve upon the worst case of Time Out's solution. It does, however, make things a little hard to see why they are working.

The result of this is how you've handled the tests after the alternating one (ie 0101010101010101010101). Running your trials through my code, I see that the initial trials nearly cut the search space in thirds. The ones after the alternating trial aren't quite as useful. They only cut out about a third in the worst case. So, it seems, any gains you've made in the first half, are given up in the second. It seems to me that you'll end up around Time Out's worst case (perhaps a little better).

Looking strictly at the search space after each guess, the first half of your approach is not optimal. It's not bad, but not optimal. It is, however, easy to replicate.

Like I said previously, removing the 0000000000000000 guess does not buy you anything. It just makes things harder to visualize.

Hopefully you don't think I'm being too harsh here. It's just thought and observations before and after testing the method with my code. And speaking of code... here it is for those who know c++.

Spoiler for Code

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>
#include <vector>

using namespace std;

int numcards=26;
unsigned int mask=0;

int getCorrect(int a, int b)
{
	//MIT HackMEM method for counting bits
	unsigned int n = (~(a ^ <img src='http://brainden.com/forum/public/style_emoticons/<#EMO_DIR#>/cool.png' class='bbc_emoticon' alt='B))' /> & mask;
	register unsigned int tmp;
	tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
	return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

void printbin(int byte)
{
		for (int i = 0; i < numcards; i++)
	{
				if (byte & (1 << i))
						printf("1");
				else
						printf("0");
	}
}

vector <int> *pruneit(int guess, int goal, vector <int> *poss)
{
	vector <int> *newposs = new vector<int>;
	for(int i = 0; i < poss->size(); i++)
	{
		if (getCorrect(guess,poss->at(i)) == goal)
		{
			newposs->push_back(poss->at(i));
		}
	}
	delete poss;
	return newposs;
}

int getintfrombin()
{
	char buffer[64];
	memset(buffer,0,sizeof(char)*64);
	cin >> buffer;
	int thenum = 0;
	for(int i = 0; i < numcards; i++)
	{
		if (buffer[i] == '1')
		{
			thenum += 1<<i;
		}  
	}  
	return thenum;
}



int main(int argc, char *argv[])
{
	
	if (argc > 1)
	{
		numcards = atoi(argv[1]);
	}
	
	mask = (1<<(numcards)) - 1;


	vector <int> *poss = new vector <int>;
	vector<int> guesses;
	vector<int> responses;
	int totals[numcards+1];
	
	
	int command;
	while (1)
	{
		if (guesses.size() > 0)
		{
			cout << endl;
			cout << "Guess/Response List" << endl;
			for(int i = 0; i < guesses.size(); i++)
			{
				printbin(guesses.at(i));
				cout << "  (" << guesses.at(i) << ") - " << responses.at(i) << endl;
			}
		}
		if (poss->size() > 0)
		{
			cout << "Possibilities left == " << poss->size() << endl;
		}
	  
		cout << "0 - Reset." << endl;
		cout << "1 - Check guess." << endl;
		cout << "2 - Check binary guess." << endl;
		cout << "3 - Find best guess." << endl;
		cout << "4 - Enter guess and response." << endl;
		cout << "5 - Enter binary guess and response." << endl;
		cout << "6 - List Possibilities." << endl;
		cout << "7 - Convert bin to int." << endl;
		cout << "8 - Find best guess in remaining items." << endl;
		cout << "Enter Command: ";
		cin >> command;
		
		
		
		if (command == 0)
		{
			responses.clear();
			guesses.clear();
			poss->clear();
		}
		
		if ((command == 1) || (command == 2))
		{
			if (guesses.size() == 0)
			{
				cout << "Sorry, make an initial guess first (all initials equivalent).";
				continue;
			}
			
			int i;
			if (command == 1)
			{  
				cout << "Enter guess: ";
				cin >> i;
			}
			else
			{
				cout << "Enter guess in binary: ";
				i = getintfrombin();
			}
			
			
			
			memset(totals,0,sizeof(int)*(numcards+1));
			for(int j = 0; j < poss->size(); j++)
			{
				totals[getCorrect(i,poss->at(j))]++;
			}

		   	   cout << "guess = ";
		   	   printbin(i);
		   	   cout << "  (" << i << ")" << endl;
		   	   for(int j = 0; j < numcards+1; j++)
		   	   {
			   	   cout << "response " << j << " = " << totals[j] << endl;
		   	   }
		}
		
		if (command == 3)
		{
			if (guesses.size() == 0)
			{
				cout << "Sorry, make an initial guess first (all initials equivalent).";
				continue;
			}
			
			int limit;
			cout << "Enter limit (0 for no limit): ";
			cin >> limit;
			if (limit > (1<<numcards)) limit = (1<<numcards);
			if (limit==0) limit = (1<<numcards);
			
			
			int best = 1<<numcards;
			int i;
			int besti=0;
			for(i = 0; i < limit; i++)
			{
			  
				cout << "\r" << i;
				memset(totals,0,sizeof(int)*(numcards+1));
				
				for(int j = 0; j < poss->size(); j++)
				{
					totals[getCorrect(i,poss->at(j))]++;
				}
				int max = totals[0];
				for(int j = 1; j < numcards+1; j++)
				{
					max = max > totals[j] ? max : totals[j];
				}
				
				if (max < best)
				{
					best = max;
					cout << endl << "guess = ";
					printbin(i);
					cout << "  vvvvvvvvvvvvvvvvv" << endl;
					for(int j = 0; j < numcards+1; j++)
					{
						cout << "response " << j << " = " << totals[j] << endl;
					}
					cout << "guess = ";
					printbin(i);
					cout << "  ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl;
					cout << "new best!!!" << endl;
					besti=i;
				}
				//else if (max==best)
				//{
				//	cout << "\rguess = ";
				//	printbin(i);
				//	cout << " (" << i << ") is equivalent." << endl;
				//}
			}
			
			i = besti;
			memset(totals,0,sizeof(int)*(numcards+1));
				
			for(int j = 0; j < poss->size(); j++)
			{
				totals[getCorrect(i,poss->at(j))]++;
			}
			cout << endl << "guess = ";
			printbin(i);
			cout << "  vvvvvvvvvvvvvvvvv" << endl;
			for(int j = 0; j < numcards+1; j++)
			{
				cout << "response " << j << " = " << totals[j] << endl;
			}
			cout << "guess = ";
			printbin(i);
			cout << "  ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl;
			
		}
		
		if ((command == 4) || (command == 5))
		{
			int guess,goal;
			if (command == 4)
			{  
				cout << "Enter guess: ";
				cin >> guess;
			}
			else
			{
				cout << "Enter guess in binary: ";
				guess = getintfrombin();
			}

			cout << "Enter response: ";
			cin >> goal;
			
			guesses.push_back(guess);
			responses.push_back(goal);
			
			if (poss->size() > 0)
			{
				poss = pruneit(guess,goal,poss);
			}
			else
			{
				for(int i = 0; i < 1<<numcards; i++)
				{
					if (getCorrect(guess,i) == goal)
					{
						poss->push_back(i);
					}
				}
			}
		}
		
		if (command == 6)
		{
			if (guesses.size() == 0)
			{
				cout << "Sorry, make an initial guess first (all initials equivalent).";
				continue;
			}
			
			for(int i = 0; i < poss->size(); i++)
			{
				printbin(poss->at(i));
				cout << "  (" << poss->at(i) << ")" << endl;
			}
			cout << endl;
		}
		
		if (command == 7)
		{
			cout << "Enter binary: ";
			int thenum = getintfrombin();
			
			cout << "The number is " << thenum << endl;
		}
		
		
		if (command == 8)
		{
			if (guesses.size() == 0)
			{
				cout << "Sorry, make an initial guess first (all initials equivalent).";
				continue;
			}
			
			int best = 1<<numcards;
			int i,k;
			for(k = 0; k < poss->size(); k++)
			{
				i = poss->at(k);
			  
				cout << "\r" << (poss->size()-k);
				memset(totals,0,sizeof(int)*(numcards+1));
				
				for(int j = 0; j < poss->size(); j++)
				{
					totals[getCorrect(i,poss->at(j))]++;
				}
				int max = totals[0];
				for(int j = 1; j < numcards+1; j++)
				{
					max = max > totals[j] ? max : totals[j];
				}
				
				if (max < best)
				{
					best = max;
					cout << endl << "guess = ";
					printbin(i);
					cout << "  vvvvvvvvvvvvvvvvv" << endl;
					for(int j = 0; j < numcards+1; j++)
					{
						cout << "response " << j << " = " << totals[j] << endl;
					}
					cout << "guess = ";
					printbin(i);
					cout << "  ^^^^^^^^^^^^^^^^^" << "(" << i << ")" << endl;
					cout << "new best!!!" << endl;
				}
			}
		}
		
	}

	return 0;
}

Spoiler for Info on code

First off, you can choose a number of cards up to 31 (haven't really tested past 26). I could probably get it working for 32, but... meh. You give the number of cards as a command line argument. If nothing is given, it does 26.

You need to give an initial guess/trial first, this is so that it doesn't need to have a vector of 2^cards length to start off.

And I'll give some use cases once I get back from some volleyball.

this is my first Post in the forum

Spoiler for first try

I thought of first trial in a period of 1 and 0 like 10101010101010101010101010 and each time reverse the order of 2bits starting from the beginning if the difference between the previous answer and the last one is +2 that mean those 2bit become in a correct order... if it is -2 the 2bit was in correct order before the reverse... that give us 14 trials... but if it is 0 that mean the 2bit are of the same color... and that send me back to 27 trials... Ooops I don't find a good answer... but I thing there is something right in this way

Welcome to the Den

[EventHorizon]

Spoiler for For those interested, more info on the code

The binary representations are done in reverse order, so the least significant bit is on the left. I didn't put in any bounds checking, for the most part, so if you try to break the code or enter something it's not expecting, it will likely crash or hang or something (so ctrl+c it if that happens).

Most commands won't work until you've entered the first guess (either command 4 or 5).

You enter a number of cards on the command line (perhaps I should have made a menu option for it too... oh well), and then it brings you to a menu. You enter a number corresponding to the command you want.

Entering a 0 resets everything.

Entering 1 and then an integer will show what distribution of possible color sequences is produced by that guess (binary representation of that integer) from the remaining possibilities.

Entering 2 and then a binary string of 1's and 0's (autofills with 0's if you don't enter a long enough string) will do the same as command 1, but for the binary representation.

Entering 3 will search through all possible guesses and find the one that has the flattest distribution (the smallest maximum). This guess then minimizes the worst case scenario because there are fewer possibilities (ie locally greedy search, which may not necessarily be globally optimal). This can be quite slow with a lot of cards (but gets faster will less cards or less remaining possibilities). I could speed this up significantly if I use equivalency classes, but that's a lot of extra complexity to find them and use them... so maybe later.

Entering 4 and an integer or 5 and a binary string followed by the desired response will cause it to restrict the pool of possible strings to the ones that result in that response when the given guess is made.

Entering 6 will list all sequences that could still be correct given the guesses and responses made.

Entering 7 will convert a binary string to an integer. This is a remnant from before I made entering binary strings work.

Entering 8 will restrict the possible guesses to the sequences that could still be correct, and it will find the one will the flattest distribution under that restriction.

And that's about it. ctrl+c to quit since I didn't put a quit option in.

If anyone actually tests it out or uses it, let me know what you think and if you want me to add an option or change something.

Edit: Also... I have no idea how it happened, but a b was capitalized (or maybe even more errors introduced) in the line "unsigned int n = (~(a ^ B)) & mask;" in the getCorrect method. I didn't notice any other strange capitalizations introduced, but they may be there.

Edited by EventHorizon, 01 June 2012 - 09:11 AM.

[phil1882]

event horizon:

Spoiler for

no i don't think you're being harsh, think your calling it as you see it. i don't doubt your math, but have you actually put the two first trails
00000000000000000000000000000000
and
00000000000000001111111111111111
into your code to see how much search space each one reduces?
I'm pretty sure the second one slightly more optimal. it gives the extra information of where the 1's are likely to be.
i didn't write a programming approach, so getting as many cut down by a third as i did is i believe fairly good.

Edited by phil1882, 01 June 2012 - 12:14 PM.

[EventHorizon]

event horizon:

Spoiler for

no i don't think you're being harsh, think your calling it as you see it. i don't doubt your math, but have you actually put the two first trails
00000000000000000000000000000000
and
00000000000000001111111111111111
into your code to see how much search space each one reduces?
I'm pretty sure the second one slightly more optimal. it gives the extra information of where the 1's are likely to be.
i didn't write a programming approach, so getting as many cut down by a third as i did is i believe fairly good.

Spoiler for First guesses

First guesses are all equivalent in the amount of information they give.

Just verified it with the code (at least with those two). Both leave 12870 possibilities when the reponse is 8 correct when used with a 16 card deck.

Guessing 000000000 at the first is the same as guessing 000000111111 with the second half of all strings in the search space flipped 0's for 1's. Since after that operation, the search space is the same, there is no real difference between any guess. There is always an operation to make it equivalent to any other.

All guesses by themselves produce the same distribution over the whole search space, it is the combination of them that lets us figure things out. Not only that, but the order of guesses obviously doesn't matter, so an optimality proof would involve this basic distribution and how it overlaps with itself to single out lone possibilities.

Just to point it out, this distribution produced by a guess is the Nth layer of Pascal's triangle, where N is the number of cards in the deck being guessed. (eg, 12870 = 16!/8!8! = 16 choose 8 = middle element of 8th layer of Pascal's triangle)


Also, something is either optimal (ie, the best), or it is not. Something cannot be more optimal than some other optimal thing. It's sorta like saying more best. I had a professor who harped on that, and it has sorta become my pet peeve too. So, instead just say better.