Your program should consist of a single file named main.cpp. This is the file to submit through blackboard: please see the assignment sheet.
We consider an adaptation of the BULLS and COWS game where a player, called the code- breaker, tries to find the secret code of another player, called the codemaker, through a succes- sion of guesses.
You will assume that secret codes and guessed codes are formed of nine characters where each character is a 0 or a 1. Each time the codebreaker makes a guess the codemaker indicates the numbers of bulls and cows, where the bulls are the characters that are correctly guessed and the cows are the characters that appear in both codes but at different positions. For example, assume the secret code is 001100000. If the guessed code is 011011111 we get two bulls, in position zero and two, assuming the code positions are numbered from left to right starting from zero, and two cows, as the guessed code has correctly predicted an additional 0 and an additional 1.
In all versions of the game you should assume that players have at most seven guesses to break the code.
1. Program a version of the game where you are the codebreaker and the computer is the codemaker. An example of a possible run is shown in Figure 1.
2. Program a version of the game where the computer is the codebreaker and you are the codemaker. In this version you may assume that instead of entering the number of bulls and the number of cows by hand each time the computer makes a guess, you provide your program with your secret code for the sole purpose of computing these numbers. An example of a possible run is shown in Figure 2.
Note: there wont be any marks awarded for graphical interfaces, or the likes.
You can make your own decisions; the following sections are suggestions.
Suppose the codebreaker were to use nine 0s for its first guess and the codemaker were to reply 6 bulls and 0 cows. Then the codebreaker would deduce that the secret code contains six 0s and three 1s. From there on the codebreaker would never use a guess that does not have six 0s and three 1s. This idea can be generalised.
Suppose the computer keeps a list of all possible codes. After its first guess, if it hasnt chanced upon the actual secret code, it can remove from its list the codes that it knows cannot be the secret code.
To make things clear let us look at an example. To simplify the presentation consider a game with codes of length 4. The list of possible codes is:
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Suppose the secret code is 1000.
Assume the computers first guess is 0011 (which may be selected at random, or in anyway you see fit). The answer the computer gets is 1 bull and 2 cows. Therefore it can eliminate any code from the list of possible codes that when tested with the guess 0011 does not produce 1 bull and 2 cows. The codes left in the list are:
0100, 1000, 1101, 1110
The computer then selects 0100, the first of the remaining choices, as second guess. This gives 2 bulls and 2 cows when compared with the secret code 1000. The computer eliminates any remaining code from the list of possible codes that when tested with the guess 0100 does not produce 2 bulls and 2 cows. There is only one choice left:
1000
The computers third guess is 1000, the first of the remaining choices. This gives 4 bulls. The computer found the secret code in 3 guesses.
There is a simple way to implement the above strategy, without having to program the genera- tion of all codes. In our game we assume that the secret code is made of nine characters where each character is a 0 or a 1. This means there are 512 possible codes that could be indexed as 0th code 1st code, etc. up to 511th code.
nstead of using a list of codes you can create a vector of boolean, choice, of size 512. where choice [ i ] is false if the ith code has been eliminated and choice [ i ] is true if the ith code is still a possibility. To find what the ith code actually is you can use the function, index2code, below. There is no need to investigate how it works. Just use it as a black box. However. youll need to add the line # include < bitset >at the top of your program.
string index2code ( int i )
{
return bitset < 9>(i ) . to string ( ) ;
}
Starting the BULLS and COWS game
Enter 1 for you to break my code.
Enter 2 for me to break your code.
Enter anything else to quit.
Your choice> 1
trial 1/7. Your guess? 000000000
6 bulls and 0 cow
trial 2/7. Your guess? 111000000
7 bulls and 2 cows
trial 3/7. Your guess? 110100000
7 bulls and 2 cows
trial 4/7. Your guess? 011010000
7 bulls and 2 cows
trial 5/7. Your guess? 110010000
Moo!!! you found the secret code.
Enter 1 for you to break my code.
Enter 2 for me to break your code.
Enter anything else to quit.
Figure 1: The human tries to find the code.
Enter 1 for you to break my code.
Enter 2 for me to break your code.
Enter anything else to quit.
Your choice> 2
Please enter your secret code> 011001000
trial 1/7. My guess> 000011111
3 bulls and 4 cows
trial 2/7. My guess> 001100001
5 bulls and 4 cows
trial 3/7. My guess> 010100010
5 bulls and 4 cows
trial 4/7. My guess> 011000100
7 bulls and 2 cows
trial 5/7. My guess> 011001000
Yeeha! I won!
Enter 1 for you to break my code.
Enter 2 for me to break your code.
Enter anything else to quit.
Your choice> x
Press any key to continue . . .
Figure 2: The computer tries to find the code.