Guessing game within 7 attempts

I am trying to write a program according to the following description:

The user picks the number and tells the computer whether its guesses are too high or too low until the computer guesses it right.
Done correctly, the program should be able to determine the number within 7 guesses (assuming the human doesn't cheat).
(Hint: binary search – try exactly halfway between the possible numbers left).

Provide test values and expected results for your program.

How can I make the computer "guess" correctly within 7 attempts.

My code is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include <time.h>
#include <iostream>
using namespace std;

int main()
{ 
 int min,max;
 cout<<"To begin guessing game, enter maximum and minimum game parameters (positive integers).\n";
 cout<<"Enter minimum value : ";
 cin>>min;
 cout<<"Enter maximum value : ";
 cin>>max;
 cout<< "Choose a number between "<<min<< " and "<<max<<" : ";
 int userNum;
 cin>>userNum; 
 int compGuess;
 srand(time(NULL));
 compGuess = rand() % max + min;//computer produces random number between min and max and stores in variable b

    
        while (userNum != compGuess)
        {
            cout<<"Computer guesses "<<compGuess;
            cout<<endl;
            cout<<"Is your number higher? (enter y for yes or n for no) : ";
            char c;
            cin>>c;
            bool d;
                if (c=='y')
                    {
                        d=true;
                        min=compGuess;
                    }
                else  
                    {
                        d=false;
                        max=compGuess;
                    }
                    
                if (d)
                    {
                        compGuess=(compGuess+max)/2;
                    }
                else
                    {
                        compGuess=(min+compGuess)/2;  
                    }
        }   
        cout<< "Your number is "<<compGuess;   
        
}        


I left my final code as follows leaving the user input range:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <time.h>
#include <iostream>
using namespace std;

int main()
{
 int min, max;
 cout << "\tTo begin guessing game,\n\tenter maximum and minimum game parameters\n\t(must be positive integers).\n\n";
 cout << "\tEnter minimum value : ";
 cin >> min;
 cout << "\tEnter maximum value : ";
 cin >> max;
 cout << "\tChoose a number between (and including) " << min << " and "<< max << " : ";
    max++;
 int userNum;
 cin >> userNum;
 cout << endl;
 int compGuess, guessCount = 1;
 compGuess = ( max + min ) / 2;

    
        while ( userNum != compGuess )
        {
            cout << "\t\tComputer guesses " << compGuess;
            cout << endl;
            cout << "\tIs your number higher? (y/n) : ";
            char userYesOrNo;
            cin >> userYesOrNo;
            bool numTest;
                if ( userYesOrNo == 'y' )
                    {
                        numTest = true;
                        min     = compGuess;
                    }
                else
                    {
                        numTest = false;
                        max     = compGuess;
                    }
                    
                if (numTest)
                    {
                        compGuess = ( compGuess + max ) / 2;
                    }
                else
                    {
                        compGuess = ( min + compGuess ) / 2;
                    }
            cout << endl;
            guessCount++;
        }
    cout << "\tYour number is " << compGuess << endl;
    cout << "\tcomputer guessed on attempt " << guessCount;
    
    
    cout << endl;
    cout << endl;
        
}


Sample outputs are as follows:


        To begin guessing game,
	enter maximum and minimum game parameters
	(must be positive integers).

	Enter minimum value : 0
	Enter maximum value : 100
	Choose a number between (and including) 0 and 100 : 0

		Computer guesses 50
	Is your number higher? (y/n) : n

		Computer guesses 25
	Is your number higher? (y/n) : n

		Computer guesses 12
	Is your number higher? (y/n) : n

		Computer guesses 6
	Is your number higher? (y/n) : n

		Computer guesses 3
	Is your number higher? (y/n) : n

		Computer guesses 1
	Is your number higher? (y/n) : n

	Your number is 0
	computer guessed on attempt 7



	To begin guessing game,
	enter maximum and minimum game parameters
	(must be positive integers).

	Enter minimum value : 0
	Enter maximum value : 100
	Choose a number between (and including) 0 and 100 : 100

		Computer guesses 50
	Is your number higher? (y/n) : y

		Computer guesses 75
	Is your number higher? (y/n) : y

		Computer guesses 88
	Is your number higher? (y/n) : y

		Computer guesses 94
	Is your number higher? (y/n) : y

		Computer guesses 97
	Is your number higher? (y/n) : y

		Computer guesses 99
	Is your number higher? (y/n) : y

	Your number is 100
	computer guessed on attempt 7



	To begin guessing game,
	enter maximum and minimum game parameters
	(must be positive integers).

	Enter minimum value : 0
	Enter maximum value : 100
	Choose a number between (and including) 0 and 100 : 50

	Your number is 50
	computer guessed on attempt 1



	To begin guessing game,
	enter maximum and minimum game parameters
	(must be positive integers).

	Enter minimum value : 0
	Enter maximum value : 100
	Choose a number between (and including) 0 and 100 : 31

		Computer guesses 50
	Is your number higher? (y/n) : n

		Computer guesses 25
	Is your number higher? (y/n) : y

		Computer guesses 37
	Is your number higher? (y/n) : n

	Your number is 31
	computer guessed on attempt 4



	To begin guessing game,
	enter maximum and minimum game parameters
	(must be positive integers).

	Enter minimum value : 0
	Enter maximum value : 100
	Choose a number between (and including) 0 and 100 : 87

		Computer guesses 50
	Is your number higher? (y/n) : y

		Computer guesses 75
	Is your number higher? (y/n) : y

		Computer guesses 88
	Is your number higher? (y/n) : n

		Computer guesses 81
	Is your number higher? (y/n) : y

		Computer guesses 84
	Is your number higher? (y/n) : y

		Computer guesses 86
	Is your number higher? (y/n) : y

	Your number is 87
	computer guessed on attempt 7
Last edited on
Don't prompt the user for the number. The user should just tell you if you're high, low or correct.

The number of guesses required depends on how big the range is. I suspect that somewhere else in the assignment it says the number is between 1 and 100.

Lines 41-48 could be simply compGuess = (min+max)/2;

Beware of off-by-one errors. If the number is higher than your guess then min should be compGuess+1, not compGuess. This assumes that min is the smallest possible value.
After testing your code, I am understanding where your problem lies.

This is an Algorithm complexity situation where 7 attempts is the maximum guesses within a sized array.

If n is sized 127, the number of guesses will log2 (6) plus 1, therefore 7.

Based on the power of 2, the computer will have to either increase its guesses based on the maximum limit set by the user.

You can learn more in detail about Binary Search Complexity here:

https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search
Hello linchukbb,

Let us start with this.

1. The user picks the number and tells the computer whether its guesses are too high or too low
until the computer guesses it right.

2. Done correctly, the program should be able to determine the number within 7 guesses
(assuming the human doesn't cheat).
  • The seven guesses tells me that the number range is between 1 and 100 inclusive.
  • This could also be any range of 100 numbers.

3. (Hint: binary search – try exactly halfway between the possible numbers left).
 
4. Provide test values and expected results for your program.


To point 1. No where does it say that you need to get from the user the number to guess or the min or max range. Keep it simple. if you want the user to enter the number to guess that is fine it can be used in the program. For now set the min and max values and use a range that works with the 7 guesses.

For point 2. I agree with dhayden.

dhayden wrote:

The number of guesses required depends on how big the range is. I suspect that somewhere else in the assignment it says the number is between 1 and 100.


Since you are limited to 7 guesses that tells me that the range is 100 numbers and most people who do this type of program use 1 - 100. Get the program to work with this first before you start doing something different.

The one thing I have not tried is 100 numbers in a different range, but I think it should work. Say 101 to 200. OK I tried it. 101 - 200 works the same.

Point 3. Is a hint on what you are suppose to learn.

I take point 4. to mean do something on paper. Doing this first can help to understand how to write the program.

Looking at your original code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <time.h>
#include <iostream>

using namespace std;

int main()
{
    int min, max;

    cout << "To begin guessing game, enter maximum and minimum game parameters (positive integers).\n";

    cout << "Enter minimum value : ";
    cin >> min;

    cout << "Enter maximum value : ";
    cin >> max;

    cout << "Choose a number between " << min << " and " << max << " : ";

    int userNum;
    cin >> userNum;

    int compGuess;

    srand(time(NULL));

    compGuess = rand() % max + min;  A//computer produces random number between min and max and stores in variable b


    while (userNum != compGuess)
    {
        cout << "Computer guesses " << compGuess;
        cout << endl;

        cout << "Is your number higher? (enter y for yes or n for no) : ";

        char c;
        cin >> c;

        bool d;

        if (c == 'y')
        {
            d = true;
            min = compGuess;
        }
        else
        {
            d = false;
            max = compGuess;
        }

        if (d)
        {
            compGuess = (compGuess + max) / 2;
        }
        else
        {
            compGuess = (min + compGuess) / 2;
        }
    }

    cout << "Your number is " << compGuess;
}

I added some blank lines and the indentation has changed, so pay attention to that. The blank lines make it easier to read and spot problems. The proper indentation makes it easier to follow the flow.

I have found that changing the IDE to use spaces instead of the tab makes the indentation less exaggerated when posting here.

"time.h" is a C header file. With a C++ program you should be using "ctime". If "rand" and "srand" compile with out any problem then "iostream" may be including "cstdlib" and you do not realize it. It i better to include both "ctime" and "cstdlib" to be safe as not all compilers and header files are the same.

That being said "cstdlib", "ctime", "rand" and "srand" should not be in your program in the first place. Using "rand" to pick the first guess tends to defeat the purpose of the binary search concept that you are meant to learn.

As a start I have changed you program to this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cctype>     // <--- "std::tolower()" and "std::toupper()" + more.
//#include <ctime>    // <--- For time functions. Both of these are not needed.
//#include <cstdlib>  // <--- For "srand" and "rand".
#include <string>     // <--- Used for testing. Comment or remove when finished. Keep if you like.

int main()
{
    constexpr int TOTAL_GUESSES{ 7 };

    int min{}, max{ 101 };
    int numOfGuesse{ 1 };
    int numToGuess{};
    int compGuess{ 50 };

    std::cout << "\n Choose a number between " << min + 1 << " and " << max - 1 << " : ";

    std::cin >> numToGuess;

    while (numToGuess != compGuess && numOfGuesse <= TOTAL_GUESSES)
    {

I changed the variable names a bit. This is not to say that you need to make the changes, but to show what a good variable name can do for the program.

Line 9 is defined as a constant because that should never change. Unless you change it and recompile the program.

In line 11 "min" is defined and initialized to zero and "max to 101. This will start you off properly and avoid the "off-by-one errors" that dhayden spoke of.

Line 12 is initialized to 1 because by the time you enter the while loop the computer has already made its first guess.

Line 13 is initialized to zero. This is not necessary because of line 18, but it is a good habit to get into.

Line 14 is initialized to the computers first guess. Since the idea of the program is how a binary search works (50) is the half way point to start with. This is also why line 12 starts at 1 and not zero.

If you run this code you will see why line 16 has the "+ 1" and "- 1".

The (&&) and rhs of the while condition is just in case, but should never become false if the rest of the while loop works right.

Inside the while loop you have:
1
2
3
4
5
6
7
8
9
cout << "Computer guesses " << compGuess;
cout << endl;

cout << "Is your number higher? (enter y for yes or n for no) : ";

char c;
cin >> c;

bool d;

Line 1 is fine, but could be written as: cout << "Computer guesses " << compGuess << '\n';. This makes line 2 unnecessary asd the "\n" should flush the output buffer. Using the "endl" comes with overhead to call that function and to many could slow down the program. You are more likely to see this in a larger program with many"endl"s.

Line 4. Do not over complicate things. The 2 choices are "h" (high) or "l" (low). That is what you should be working with.

Line 6. Single letter variable names should be avoided. In this case the "c" works, but "ch" is more often used to represent a single character.

"bool d". I would ask what "d" means, but since it does not need to be used it does not matter.

The first if statement is the next problem:
if (ch == 'y'). This works, but cross your fingers and hope the user follows directions and enters only a lower case letter.

if (ch == 'y' || ch == 'Y'). Better choice to check for both cases.

if (std::tolower(ch) == 'y'). An alternative to change the case before the check. This needs the header file "cctype".

Then all you need is:
1
2
3
4
5
6
7
8
if (...)  //<--- for 'y'
else if (...)   //<--- for 'n'
else
{
    std::cout << "\n     Invalid choice!\n";

    continue;
} 

The "continue" will skip anything after the else and go the the while condition.
Inside the if and else if you will need to change the value of "min" or "max" and add 1 to the "numOfGuesses". Finding the next computer guess can be doe after the else block.

The second set of if/else statements are not needed. This is just more work than you need.

Andy
Hello linchukbb,

A couple of test runs from my program:

 Choose a number between 1 and 100 : 42

 Computer's first guess is: 50

 Is this number higher or lower? (h/l) : h

 Computer's second guess is: 25

 Is this number higher or lower? (h/l) : l

 Computer's third guess is: 37

 Is this number higher or lower? (h/l) : l

 Computer's forth guess is: 43

 Is this number higher or lower? (h/l) : h

 Computer's fifth guess is: 40

 Is this number higher or lower? (h/l) : l

 Computer's sixth guess is: 41

 Is this number higher or lower? (h/l) : l

  The computer guess is 42. And it took 7 tries to guess this.




 Choose a number between 1 and 100 : 100

 Computer's first guess is: 50

 Is this number higher or lower? (h/l) : l

 Computer's second guess is: 75

 Is this number higher or lower? (h/l) : l

 Computer's third guess is: 88

 Is this number higher or lower? (h/l) : l

 Computer's forth guess is: 94

 Is this number higher or lower? (h/l) : l

 Computer's fifth guess is: 97

 Is this number higher or lower? (h/l) : l

 Computer's sixth guess is: 99

 Is this number higher or lower? (h/l) : l

  The computer guess is 100. And it took 7 tries to guess this.




 Choose a number between 1 and 100 : 25

 Computer's first guess is: 50

 Is this number higher or lower? (h/l) : h

  The computer guess is 25. And it took 2 tries to guess this.


Sorry I added a little extra to the program. Did this mostly for testing, but could be useful.

Andy
So it turns out the instructions were simply incomplete and the range was indeed supposed to be 1-100 and not input by the user. I got it figured out
Topic archived. No new replies allowed.