Questions about my Bracketing Search Solution

[Aeon221]

This is my response to the four star difficulty version of the Bracketing Search problem described here: http://www.cplusplus.com/forum/articles/12974/

/* As should be pretty obvious, the method I'm using to solve for the hidden number doesn't hold up well for numbers above, say, 95 or below, say, 5, and possibly does poorly with others -- although the numbers between 5 and 95 that I tested the program had no trouble finding in the requisite six guesses. So, since that isn't a coding problem (and I think I've got the code down pretty well here, although optimization suggestions are ALWAYS appreciated) I feel like I'm allowed to ask.

I'm thinking adding in a test to the guess_higher/guess_lower functions to change the guess amount if a certain threshold is reached would be a good idea (such as if (guess < 5 && guess > 95) use standard, else if (guess <= 5) use this else if (guess >= 95) use that), but I'm not quite sure what exactly to switch it to, since both 95 and 5 are six guesses down the road.
*/

I've "commented out" the above because I've managed to fix the guessing code to solve for 95++ or 5-- by changing step four and adding a step five in guess_lower and guess_higher. I'm still looking for optimization suggestions, because this is a heck of a lot of code for something that feels like it should be simpler!

Thanks for the help!

#include <iostream>

using namespace std;

void game_start();
void guess_manager(int a);
void endgame_quit();
void endgame_win(int a);
int how_many(int a);
void guess_higher(int a);
void guess_lower(int a);



int main()
{
	game_start();
}

void game_start()
{
	cout << "Please think of a number between 1 and 100 for me to guess!" << endl;
	cout << "I will guess it in 7 or fewer guesses!" << endl;
	cout << "You can lie if you want to, but then you might as well not even play!" << endl;
	
	guess_manager(50);
}


void guess_manager(int a)
{
	char tell;
	for (;;)
	{
		cout << "\n\nIs the number " << a << "?\n\n";
		cout << "Please enter (without brackets):";
                cout << "\n\n[c] if correct \n[h] if your number is higher";
                cout << "\n[l] if your number is lower";                
                cout <<  "\n[q] to quit" << endl;
		cin >> tell;

		if (tell == 'c')
			endgame_win(a);
		else if (tell == 'h')
			guess_higher(a);
		else if (tell == 'l')
			guess_lower(a);
		else if (tell == 'q')
			endgame_quit();
	}
}

void endgame_quit()
{
	cout << "Ok, see ya!" << endl;
	exit(1);
}

void endgame_win(int a)
{
	int c = how_many(1);
	char play;
	cout << "\n\nI guessed your number was " << a << " and I was right!" << endl;
	cout << "It took me " << c-1 << " guesses to figure it out!" << endl;
	cout << "Would you like to play again? y/n: ";
	cin >> play;

	for (;;) {
	if (play == 'y')
	{
		how_many(0);
		game_start();
	}
	else if (play == 'n')
		endgame_quit();
	else 
	{
		cout << "Say again? [y] to play again, [n] to quit: ";
		cin >> play;
	}
	} 
}

int how_many(int a)
{
	static int c=0;
	if (a == 1)
		c++;
	else if (a == 0)
		c=0;
	return (c);
}


void guess_higher(int a)
{
	int c = how_many(1);

	if (c == 1)
		guess_manager(a+25);
	else if (c == 2)
		guess_manager(a+13);
	else if (c == 3)
		guess_manager(a+7);
	else if (c == 4)
		guess_manager(a+3);
	else if (c >= 5)
		guess_manager(a+1);
}

void guess_lower (int a)
{
	int c = how_many(1);
	
	if (c == 1)
		guess_manager(a-25);
	else if (c == 2)
		guess_manager(a-13);
	else if (c == 3)
		guess_manager(a-7);
	else if (c == 4)
		guess_manager(a-3);
	else if (c >=5)
		guess_manager(a-1);
}

}

edit: fixed some hscroll breaking code

[jsmith]

From the looks of it, you've got the gist of the solution, but there is a much simpler way to code it.

Essentially, you know to go half-way between the range of numbers in which the answer lies.
When the program starts, it knows the answer is in the range [ 1...100 ], so it guesses
( 100 + 1 ) / 2 == 50, ie, splitting the range in half. Now if the actual number is higher, say, then
you add 25 to your initial guess because you know the range is [ 51...100 ], or exactly 50 numbers.
But you can arrive at 75 also by doing ( 51 + 100 ) / 2, which is the same pattern as you'd use to
compute 50. Likewise, you can continue this pattern until you guess correctly or the range becomes
empty (in which case the user cheated or lied).

See if you can modify your code to use the above logic. It will shorten it significantly.

[Aeon221]

So you're suggesting that rather than using the two guess functions, I should do something along the lines of:

guessfunc() {
int guess = 50
char a


do {
cout << guess << "h, l, c, q"
cin >> a

if (a == 'h')
cout << (100 + guess)/2
else if (a == 'l')
cout << (guess)/2
else if (a == 'c')
cout << guess << "was right"
} while (a != q) 
}

Correct?

I guess that would make way more sense, yeah, but I'm still pretty excited about my first use of a static variable and, really, the whole how_many function was an absolute rush when I thought it up.

[jsmith]

Sort of. Read my reply again. It implies that you need to keep track of the range of possible answers. For
that, you'll need two variables... one that holds the lowest value and one that holds the highest. You have
to update those values each time a guess is made.

(Ok, static variables are nothing to get excited over.)