Description
This program focuses on binary trees and recursion. Turn in files QuestionTree.java and QuestionNode.java
from the Homework section of the web site. You will need support files UserInterface.java, QuestionMain.java,
VaderMain.java, and input text files from the Homework web page; place them in the same folder as your class.
The Game of 20 Questions:
In this assignment 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. It will make a guess about what your object is. If this guess is correct, the computer wins; if not, you win.
The computer keeps track of a binary tree whose nodes represent 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. The idea is that this tree can be traversed to ask the human player a series of questions.
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.
The following partial output log shows one game being played on the above tree:
Is it an animal? yes
Can it fly? no
Does it have a tail? yes
Would your object happen to be mouse? yes
I win!
Initially the computer is not very intelligent, but it grows more intelligent each time it loses a game. If the computer’s
answer guess is incorrect, you must give it a new question it can ask to help it in future games. For example, suppose in
the preceding log that the player was not thinking of a mouse, but of a cat. The game log might look like this:
Is it an animal? yes
Can it fly? no
Does it have a tail? yes
Would your object happen to be mouse? no
I lose. What is your object? cat
Type a yes/no question to distinguish your item from mouse: Does it meow?
And what is the answer for your object? yes
Is it an animal?
Can it fly?
bird Does it have a tail?
mouse spider
Does it have wheels?
bicycle Is it nice?
TA teacher
overall root (left = “yes”) (right = “no”)
2 of 4
The computer takes the new information from a lost game and uses it to 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:
In this assignment, you will create classes QuestionTree and QuestionNode to represent the computer’s tree of yes/no
questions and answers for playing games of 20 Questions. You are provided with a client QuestionMain that handles
user interaction and calls your tree’s methods to play games. Below are two logs of execution (user input is underlined):
Log of execution #1 Log of execution #2
Welcome to the game of 20 Questions!
Shall I recall our previous games? n
Think of an item, and I will guess it.
Would your object happen to be Jedi? n
I lose. What is your object? hobbit
Type a yes/no question to distinguish your
item from Jedi: Does it use the Force?
And what is the answer for your object? n
Challenge me again? y
Does it use the Force? n
Would your object happen to be hobbit? n
I lose. What is your object? droid
Type a yes/no question to distinguish your↵
item from hobbit: Is it metal?
And what is the answer for your object? y
Challenge me again? y
Does it use the Force? n
Is it metal? y
Would your object happen to be droid? y
I win!
Challenge me again? n
Games played: 3
I won: 1
Shall I remember these games? y
What is the file name? question1.txt
Welcome to the game of 20 Questions!
Shall I recall our previous games? yes
What is the file name? question2.txt
Think of an item, and I will guess it.
Is it an animal? no
Does it have wheels? yes
Would your object happen to be bicycle? yes
I win!
Challenge me again? yes
Is it an animal? yes
Can it fly? no
Does it have a tail? yes
Would your object happen to be mouse? no
I lose. What is your object? cat
Type a yes/no question to distinguish your↵
item from mouse: Does it meow?
And what is the answer for your object? yes
Challenge me again? yes
Is it an animal? yes
Can it fly? no
Does it have a tail? yes
Does it meow? yes
Would your object happen to be cat? yes
I win!
Challenge me again? no
Games played: 3
I won: 2
Shall I remember these games? no
The program can instruct your question tree to 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
http://animalgame.com/ . Check your output using our Output Comparison Tool from the course web site.
Is it an animal?
Can it fly?
bird Does it have a tail?
Does it meow? spider
Does it have wheels?
bicycle Is it nice?
TA teacher
overall root (left = “yes”) (right = “no”)
cat mouse
3 of 4
Implementation Details:
The contents of the QuestionNode class are up to you. Though we have studied trees of ints, in this assignment you
can create nodes specific to solving this problem. Your node class should have at least one constructor used by your tree.
Your node’s fields can be public. QuestionNode should not perform a large share of the overall game algorithm.
Your QuestionTree must have the following members. You may add extra private methods. You should throw an
IllegalArgumentException if the parameter passed to any method below is null.
public QuestionTree(UserInterface ui)
In this constructor you should initialize your new question tree. You are passed an object representing the user interface
for input/output. Your tree will use this user interface for printing output messages and asking questions in the game (see
next page). Initially the tree starts out containing only a single answer leaf node with the word “Jedi” in it. The tree will
grow larger as games are played or as a new tree is loaded with the load method described below.
public void play()
A call to this method should play one complete guessing game with the user, asking yes/no questions until reaching an
answer object to guess. A game begins with the root node of the tree and ends upon reaching an answer leaf node. If the
computer wins the game, print a message saying so. Otherwise your tree must ask the user what object he/she was
thinking of, a question to distinguish that object from the player’s guess, and whether the player’s object is the yes or no
answer for that question. The two boxed partial logs on the first page are examples of output from single calls to play.
All user input/output should be done through the UserInterface object passed to your tree’s constructor.
After the game is over, the provided client program will prompt the user whether or not to play again; this is not part of
your play method. Leave this functionality to the client program.
public void save(PrintStream output)
In this method you should store the current tree state to an output file represented by the given PrintStream. In this
way your question tree can grow each time the user runs the program. (You don’t save the number of games played/won.)
A tree is specified by a sequence of lines, one for each node. 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. For example, the
two trees shown in the diagram and logs on the preceding pages would be represented by the following contents:
question1.txt question2.txt
Q:Does it use the Force? Q:Is it an animal?
A:Jedi Q:Can it fly?
Q:Is it metal? A:bird
A:droid Q:Does it have a tail?
A:hobbit A:mouse
A:spider
Q:Does it have wheels?
A:bicycle
Q:Is it nice?
A:TA
A:teacher
public void load(Scanner input)
In this method you should replace the current tree by reading another tree from a file. Your method will be passed a
Scanner that reads from a file and should replace the current tree nodes with a new tree using the information in the file.
Assume the file exists and is in proper standard format. Read entire lines of input using calls on Scanner’s nextLine.
(You don’t load the number of games played/won, just the tree. Calling this method doesn’t change games played/won.)
public int totalGames()
public int gamesWon()
In these methods you should respectively return the total number of games that have been played on this tree so far, and
the number of games the computer has won by correctly guessing your object, during the current execution of the
program. Initially 0 games have been played and won, but the games played increase by 1 for each game that is played
(each time play is called), and the games won increase by 1 each time the computer guesses your object correctly.
4 of 4
UserInterface:
Your tree should be designed to be usable with many user interfaces. We have provided a class QuestionMain with a
text user interface and a class VaderMain with a graphical user interface. Both of these classes need to display output to
the user and read input from the keyboard, but they do so in different ways (console vs. graphic). In order for your code
to work with both programs, we provide you with a Java interface for the common behavior of both user interfaces:
public interface UserInterface {
public void print(String message); // displays an output message to the user
public void println(String message); // displays an output message and new-line
public String nextLine(); // waits for user to type a string; returns it
public boolean nextBoolean(); // waits for user to choose yes(true) / no(false)
}
For example, if you had a variable ui that referred to an object that implements the UserInterface interface, you could
write the following code to ask the user a yes/no question:
ui.print(“Are you having a nice day?”);
boolean yesNo = ui.nextBoolean();
if (yesNo) {
ui.println(“That is good to hear!”); // true means user said “yes”
} else {
ui.println(“Sorry to hear that.”); // false means user said “no”
}
The following code would ask the user a more general question to which the user could type any string as a response:
ui.print(“What is your name?”);
String answer = ui.nextLine();
You must use this user interface in your program. Programs that do not do so and try to handle user interaction directly
will lose substantial credit on the assignment.
Creative Aspect (myquestions.txt):
Along with your program, turn in a file myquestions.txt that represents a saved question tree in the format specified
from your save method. For full credit, this must be in proper format, have a height of at least 5, and be your own work.
Style Guidelines and Grading:
Part of your grade will come from appropriately utilizing binary trees and recursion to implement your guessing game as
described previously. Every method with complex code flow should be implemented recursively, rather than with
loops. A full-credit solution must have zero loops. 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 or repeat cases already handled.
Redundancy is another major grading focus; some methods are similar in behavior or based off of each other’s behavior.
You should avoid repeated logic as much as possible. Your class may have other methods besides those specified, but
any other methods you add should be private.
An important concept introduced in lecture was called “x = change(x)”. This idea is related to proper design of recursive
methods that manipulate the structure of a binary tree. You must follow this pattern on this assignment to receive full
internal correctness credit. For example, at the end of a game lost by the computer, you might be tempted to “morph”
what used to be an answer node of the tree into a question node. This is considered bad style. Question nodes and answer
nodes are fundamentally different kinds of data. You can rearrange where nodes appear in the tree, but you shouldn’t turn
a former answer node into a question node just to simplify the programming you need to perform.
You should follow good general style guidelines such as: making fields private and avoiding unnecessary fields
(Remember that you will lose points if you declare variables as fields that could instead be declared as local variables);
declaring collection variables using interface types; appropriately using control structures like loops and if/else;
properly using indentation, good variable names and types; and not having any lines of code longer than 100 characters.
Comment your code descriptively in your own words at the top of your class, each method, and on complex sections of
your code. Comments should explain each method’s behavior, parameters, return, pre/post-conditions, and exceptions.
For reference, our solution is around 130 lines long (70 “substantive lines”), including comments and blank lines.