/icon48-zip.gif)
/icon48-paperless.gif)
Turn in:
-
/icon_cpp.gif)
questions.cpp
-
/icon_txt.gif)
myquestions.txt
/icon48-jar.gif)
/icon48-survey.gif)
/icon48-txt.gif)
output logs:
Assignment by Marty Stepp and Victoria Kirst. Based on a problem by Stuart Reges of U of Washington.
This problem focuses on recursion. This is an individual assignment. Write your own solution and do not work in a pair/group on this program.
questions.cpp
myquestions.txt
In this problem you will implement a yes/no guessing game called "20 Questions." 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. (Though the game is called "20 Questions," our game will not limit the game to a max of 20.) 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!
You will implement the code to play a single complete run of this game by writing the following recursive function.
Your function must be implemented with no loops and with no collections (such as Vector, Map, arrays, etc.).
bool playQuestionGame(istream& input)
Your function accepts a reference to an input file that stores the set of questions and answers to be used by the computer during the game, with one question or answer per line.
The idea is that this file can be traversed in a specific way to ask the human player a series of questions.
Your function will eventually return true or false to indicate whether the computer won the game.
The input files for the game use the format below at left, where each line either represents a single question or a single answer. Lines that start with "Q:" represent yes-or-no questions, and lines that start with "A:" represent answers for the computer to guess.
The lines occur in a specific order representing a tree-like structure of questions and answers. Each question has two follow-up options that we'll call its children, which are either answer guesses or other questions to be asked. The first child of a question is its "yes" child, which comes immediately after it. The second child of a question is its "no" child, which comes immediately after the "yes" child and any of its children. This tree-like structure is illustrated in the diagram below at right, which shows an indented and annotated version of the file's contents.
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
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
Your game must ask the questions in the proper order, so it is important to understand the file format and how to traverse it. The idea is that you begin by asking the user the question on the first line of the file ("Is it an animal?"). If the user answers Yes to "Is it an animal?", the next question your game should ask is, "Can it fly?" But if the user answers No to "Is it an animal?", the next question your game should ask is, "Does it have wheels?" And so on.
The game continues in this fashion until the game reaches an answer line that begins with "A:", such as, "A:lion".
An answer line indicates that the computer has asked enough questions that it is ready to guess what object you are thinking of.
When you reach an appropriate answer line, your game should ask the player if that is the object they are thinking of.
If the human player says yes, the computer wins the game, and your function should return true.
If the human player says no, the computer loses the game, and your function should return false.
The file ordering and structure may seem strange or confusing at first, but you will find that it is self-similar because a question can be followed by a question.
The program can read its input from different text files. You should initially test with the provided question1.txt or an even smaller file of your own creation. As your code runs, you will be able to create larger files by saving them at the end of the program. Once your code works with question1.txt, you can test it with a larger input such as the provided animals.txt, which comes with permission from the Animal Game web site at animalgame.com.
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.
Constraints:
As stated previously, your solution should not use any loops; you must use recursion.
Do not use any collections or data structures in your solution such as a Vector, Map, arrays, etc.
Lastly, your code must process the file's data by reading the file only a single time for a single play of the game.
Do not attempt to re-open, re-read, or "rewind" the input stream back to the start of the file.
It can be tricky to see how to actually solve the problem given all of these constraints and limitations; the key is in taking advantage of the self-similar nature of the input file and the game's flow using recursion in your code.
Recommended 'skip' helper function:
When the game asks the user a yes-or-no question and the user responds with "Yes", you know that the follow-up question or answer is the next line in the file.
But if the user responds with "No", the follow-up might be much later in the file, and it's harder to get your program to that place in the data.
We recommend that you write a helper function to 'skip' forward over a question line (and all of its sub-questions and answers), which you can call as needed to get to the "No" option for a given question.
The 'skip' helper is not required, though, and there are multiple acceptable and correct ways of solving this problem.
You are allowed to write any helper functions you like on this problem, though they are subject to the same constraints as your playQuestionGame function.
For example, the 'skip' helper is not allowed to use any loops or collections.
Remember that since the input stream is passed by reference, if you read lines from it in one function call, its cursor position will be advanced in other function calls as well.
This allows multiple functions and/or multiple recursive calls to work together, each reading part of the file's data.
(istream documentation)
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. 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.
Yes/no prompts:
When your program needs to prompt the user to answer a yes-or-no question, you should accept any word that starts with "y" (case-insensitively) as being a "yes" answer,
and any word that starts with an "n" (case-insensitively) as being a "no" answer.
If the user's answer does not begin with either of these characters, print an error message and re-prompt the user.
You can use the Stanford library's simpio.h function getYesOrNo to accomplish this.
(These are essentially the same as in the Fractals and Grammar Solver problems.)
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 Homework 1 and 2 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:
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. Redundancy in recursive code is another major grading focus; avoid repeated logic as much as possible. 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:
While this constraint is not new to this assignment, we want to stress that you should not make any global variables or static variables (unless they are constants declared with the const keyword).
Do not use globals as a way of getting around proper recursion and parameter-passing on this assignment.
Loops: Do not use any loops in any of your code on this part of the assignment.
Collections: Do not use any collections on this part of the assignment.
Along with your code, submit a file myquestions.txt that represents a set of questions and answers in the format specified in this document, such that it could be used as an input for your program. For full credit, this must be in proper format, have at least 5 total questions in it, and be your own work. This is worth a small part of your grade.
Here are some ideas for extra features that you could add to your program:
Indicating that you have done extra features: If you complete any extra features, then in the comment heading on the top of your program, please list all extra features that you worked on and where in the code they can be found (what functions, lines, etc. so that the grader can look at their code easily).
Submitting a program with extra features: Since we use automated testing for part of our grading process, it is important that you submit a program that conforms to the preceding spec, even if you want to do extra features. If your feature(s) cause your program to change the output that it produces in such a way that it no longer matches the expected sample output test cases provided, you should submit two versions of your program file: a first one with the standard file name without any extra features added (or with all necessary features disabled or commented out), and a second one whose file name has the suffix -extra.cpp with the extra features enabled. Please distinguish them in by explaining which is which in the comment header. Our turnin system saves every submission you make, so if you make multiple submissions we will be able to view all of them; your previously submitted files will not be lost or overwritten.
[an error occurred while processing this directive]