[an error occurred while processing this directive]

Stanford CS 106B: 21 Questions

Assignment by Marty Stepp and Victoria Kirst. Based on a problem by Stuart Reges of U of Washington.

This problem focuses on implementing a question game using binary trees. This is an individual assignment. Write your own solution and do not work in a pair/group on this program.

Files and Links:

icon
Project Starter ZIP
(open 21questions.pro)
icon
Turn in:
icon
Demo JAR
icon
Homework Survey
icon
output logs:

Problem Description:

In this problem you will implement a yes/no guessing game called "21 Questions." This problem can be thought of as an enhanced version of the "20 Questions" problem you solved in a previous assignment, where this version uses your new knowledge of binary trees to make the game more interesting. You can certainly use your own code from the previous assignment to help you write this problem, though this new version is different enough that your code will need significant modifications.

Specifically, this version of the game has the following new major features:

As before, each round of the game begins by you (the human player) thinking of an object. The computer will try to guess your object by asking you a series of yes-or-no questions. Eventually the computer will have asked enough questions that it thinks it knows what object you are thinking of, so it will make a final guess about what your object is. If this guess is correct, the computer wins; if not, you win. For example, the computer might decide to ask the following series of questions to figure out what the player is thinking of: 

Is it an animal? y
Can it fly? n
Does it have a tail? y
Does it squeak? n
Are you thinking of: lion? y
Hooray, I win!
log of execution, single game, computer wins (partial)

In the previous version of this game that you implemented, you did not store the game's questions and answers in any particular data structure; you read the input from a file line-by-line to play the game. In this version of our game, the computer keeps track of a binary tree whose nodes represent the game's questions and answers. Every node's data is a string representing the text of the question or answer. A "question" node contains a left "yes" subtree and a right "no" subtree. An "answer" node is a leaf in the tree. The idea is that this tree can be traversed to ask the human player a series of questions. (Like before, though the game is called "21 Questions," our game will not limit the tree to a height of 21; any number of questions will be allowed.)

For example, in the tree below, the computer would begin the game by asking the player, "Is it an animal?" If the player says "yes," the computer goes left to the "yes" subtree and then asks the user, "Can it fly?" If the user had instead said "no," the computer would go right to the "no" subtree and then ask the user, "Does it have wheels?"

This pattern continues until the game reaches a leaf "answer" node. Upon reaching an answer node, the computer asks whether that answer is the correct answer. If so, the computer wins. 

yes = left                           root                               no = right
                                      |
                                      |
                              Q:Is it an animal?
                          ____/                \____
                     ____/                          \____
                    /                                    \
       Q:Can it fly?                                   Q:Does it have wheels?
      /           \                                   /                      \
    /              \                                 /                        \
A:bird       Q:Does it have a tail?         Q:Does it have an engine?          Q:Is it nice?
               /              \               /               \                  /        \
              /                \             /                 \                /          \
     Q:Does it squeak?       A:spider      A:car             A:bicycle        A:SL        A:teacher
     /            \
    /              \
  A:mouse         A:lion
diagram of binary tree of game questions and answers (questions.txt)

In this version of the game, the computer expands its set of possible answers (with the human's help) each time it loses a game. Specifically, if the computer's answer guess is incorrect, you the human player must tell it a new question it can ask to help it do better in future games. For example, suppose in the preceding log that the player was not thinking of a lion, but of an elephant. The game log would look like this: 

Is it an animal? y
Can it fly? n
Does it have a tail? y
Does it squeak? y
Are you thinking of: lion? n
Drat, I lost. What was your object? elephant
Type a Y/N question to distinguish elephant from lion: Does it have a trunk?
And what is the answer for elephant? yes
log of execution, single game, computer loses and grows its tree (partial)

The computer takes the new information from the lost game and uses it to grow its tree of questions and answers. You must replace the old incorrect answer node with a new question node that has the old incorrect answer and new correct answer as its children. For example, after the game represented by the preceding log, the computer's overall game tree would be the following: 

yes = left                           root                               no = right
                                      |
                                      |
                              Q:Is it an animal?
                          ____/                \____
                     ____/                          \____
                    /                                    \
       Q:Can it fly?                                   Q:Does it have wheels?
      /           \                                   /                      \
    /              \                                 /                        \
A:bird       Q:Does it have a tail?         Q:Does it have an engine?          Q:Is it nice?
               /              \               /               \                  /        \
              /                \             /                 \                /          \
     Q:Does it squeak?       A:spider      A:car             A:bicycle        A:SL        A:teacher
     /            \
    /              \
  A:mouse         Q:Does it have a trunk?
                   /                  \
                  /                    \
                 A:elephant           A:lion
diagram of question tree after "elephant" is added

In the previous version of this problem you wrote a free-standing function to play the question game. Since this version has a more complex state and game flow, you will instead write your code in a class named QuestionTree. You will use a provided structure QuestionNode to represent each node of the question tree. You are also provided with a main client program that handles user interaction and calls your tree's member functions to play games.

Your question tree uses input files in the same format as the prior version of this problem, such as the example below. The order in which the lines are stored represents a preorder traversal of the question binary tree. 

Q:Is it an animal?
Q:Can it fly?
A:bird
Q:Does it have a tail?
Q:Does it squeak?
A:mouse
A:lion
A:spider
Q:Does it have wheels?
Q:Does it have an engine?
A:car
A:bicycle
Q:Is it nice?
A:section leader
A:teacher
input file questions.txt
Q:Is it an animal?
|
y-- Q:Can it fly?
|   |
|   y-- A:bird
|   |
|   n-- Q:Does it have a tail?
|       |
|       y-- Q:Does it squeak?
|       |   |
|       |   y-- A:mouse
|       |   |
|       |   n-- A:lion
|       |
|       n-- A:spider
|
n-- Q:Does it have wheels?
    |
    y-- Q:Does it have an engine?
    |   |
    |   y-- A:car
    |   |
    |   n-- A:bicycle
    |
    n-- Q:Is it nice?
        |
        y-- A:section leader
        |
        n-- A:teacher
indented version of questions.txt
(actual input files will not be indented!)

Implementation Details:

Your QuestionTree must have the following public members listed in the table below. Any function that traverses your binary tree must do so recursively; absolutely no loops are allowed on this problem in any part of your code. You will find that some of the member functions below do not have the parameters you'll need to implement the desired recursive behavior. In such cases you should not change our required function headers, but you may add extra "helper" functions as needed to help you implement the behavior. Any member functions you add, along with all private member variables, must be declared private.

In the previous version of this problem, a single function performed two duties simultaneously: You were reading the game's question-and-answer data from a file, and also playing the game with the user. In this version of the problem, those two tasks are split into two member functions: readData and playGame.

In the old version of the problem, you sometimes wanted to "skip" around in the data to get to the next question to ask. That is no longer the case in this version of the problem. You do not need any "skipping" function because you can move left/right in your tree to get to the next question or answer. Note that no loops are allowed in any of the members below.

QuestionTree member Description 
QuestionTree()

In this constructor you should initialize your question tree. At first the tree contains only a single node storing the answer "computer". In other words, if you were to create a question tree and then immediately begin playing the game, the computer would ask the following question: 

Are you thinking of: computer?

~QuestionTree()

In this destructor you should free all dynamically allocated memory for your tree and its question nodes. 

getGamesLost()

In this member function you should return the number of games the computer has lost during this session. Initially 0 games have been played and won. A game is lost when the computer asks the user, "Are you thinking of: ___?" and the user says "no". 

getGamesWon()

In this member function you should return the number of games the computer has won during this session. Initially 0 games have been played and won. A game is won when the computer asks the user, "Are you thinking of: ___?" and the user says "yes". 

playGame()

In this member function you should play one complete game of 21 Questions with the user, walking your question tree from its root to an answer leaf node by asking a series of Yes/No questions. This function must be written recursively and must not use any loops.

You will find that this function is somewhat similar to the playQuestionGame function you wrote in the previous version of this problem, but since your data is now stored in a binary tree instead of being read directly from the file, your logic and code flow will change somewhat.

Also note that if the computer loses the game, you must prompt for a new question and answer node and modify your question tree as appropriate. That behavior is part of the responsibility of this function. Note that the user can type any text they like for their new question and answer; the user won't type the Q: or A: prefixes, and the new question they type need not end with a question mark; you should accept whatever text they enter, including a blank string.

Yes/no prompts: As with the last version of this problem, ask yes-or-no questions using the function getYesOrNo from simpio.h.

After the game is over, the provided main program will prompt the user whether or not to play again; this is not part of your playQuestionGame function. Leave this functionality to the provided program and don't implement that part yourself. 

readData(input)

In this member function you should read question tree data from the given input stream (istream&). The file format matches that described earlier in this document. You must read the file's data and turn it into a binary tree of question nodes as drawn earlier in this document, so that subsequent calls to the playGame member function will use this data for the series of questions to ask the player. This function must be written recursively and must not use any loops.

Assume valid input: You may assume that the input file exists, is readable, and is in the proper format described in this spec, with no blank lines or extraneous/invalid data. Assume that each question will have exactly two children representing its "yes" and "no" options. You may assume that each line of the file begins with Q: or A:, either of which must be stripped off of the line by your code before asking the questions to the user.

Since you are loading new data and creating a new tree of question nodes, you must free memory for any previous nodes that were in the tree beforehand. Do not leak any memory from this function.

This member function loads the question tree's data of questions and answers, but it does not load any record of the number of games won or lost. Nor does it change your question tree's count of total games won/lost. 

writeData(output)

In this member function you should write question tree data to the given output stream (ostream&). You must write the data in the same correct file format and order to match that of the input files so that it can be read later by readData if desired. Each line must start with either Q: to indicate a question node or A: to indicate an answer (a leaf). All characters after these first two should represent the text for that node (the question or answer). The nodes should appear in the order produced by a preorder traversal of the tree. Another way of saying this is that if you read an input file using readData and then immediately call writeData, the newly written file should have exactly the same contents as the original that was read. You may assume that the file is writable. This function must be written recursively and must not use any loops.

This function saves the question tree's current data of questions and answers, but it does not save any record of the number of games won or lost.

To help you implement your question tree, we provide a file questionnode.h that declares a structure called QuestionNode to represent one binary tree node. It has the following members. Do not modify questionnode.h. 

struct QuestionNode {
    string data;          // question or answer text
    QuestionNode* yes;    // pointer to "yes" subtree (left)
    QuestionNode* no;     // pointer to "no"  subtree (right)

    // constructor (all parameters are optional)
    QuestionNode(string data = "", QuestionNode* yes = nullptr, QuestionNode* no = nullptr);
};

Style Details:

As in other assignments, you should follow our Style Guide for information about expected coding style. You are also expected to follow all of the general style constraints emphasized in the Homeworks 1-5 specs, such as the ones about good problem decomposition, parameters, using proper C++ idioms, and commenting. The following are additional points of emphasis and style contraints specific to this problem:

Binary tree usage: Part of your grade will come from appropriately utilizing binary trees and recursive algorithms to traverse them. Any functions that traverse a binary tree from top to bottom should implement that traversal recursively. We will check this particular constraint strictly; no exceptions!

Loops: Do not use any loops in any of your code on this part of the assignment.

Recursion: Part of your grade will come from appropriately utilizing recursion to implement your algorithm as described previously. We will also grade on the elegance of your recursive algorithm; don't create special cases in your recursive code if they are not necessary. Avoid "arm's length" recursion, which is where the true base case is not found and unnecessary code/logic is stuck into the recursive case. As mentioned previously, it is fine (sometimes necessary) to use "helper" functions to assist you in implementing the recursive algorithms for any part of the assignment.

Variables: The only member variables you should have on this problem are a pointer to the root of your question tree, and counters for the number of games won and lost. You should not declare any other member variables, nor should you declare any other static or 'global' variables.

Collections: Do not use any collections on this part of the assignment, other than your internal binary tree of nodes.

Memory usage: Your code should have no memory leaks. Do not allocate dynamic memory (new) needlessly, and free the memory associated with any new objects you allocate internally once they are no longer being used.

[an error occurred while processing this directive]