Assignment 3: Twenty Questions!
Due Monday, February 9 by 11:59 PM

In this project you will implement the 20 Questions Game described in class using Java. This is a lot of fun but also requires some careful design. Please start early!

You will find the compiled version of our solution to this assignment in a file called twenty_questions.class in the directory /cs/cs60/assignments/assignment3. Note that Node.class is the compiled version of Node.java, which in our solution is the class describing a single node in the binary tree. Play this game to make sure that you understand how your program should work.

• The program should start off knowing only one question ("Is it bigger than a breadbox?") and two animals ("a mouse" and "an elephant"). This data should be organized as a binary tree. To make the graders' lives easier, please use this question and these two animals as the starting data.
  
  
• Each time the game is played, the program asks a question (the question at the current node in the tree) and waits for the user's "yes" or "no" response. (You should assume througout this assignment that any answer that starts with the letter 'y' or 'Y' stands for "yes" and anything else stands for "no".) Based on this response, the program then asks the next question.
  
  
• At the end of the game, the program has either guessed the animal correctly or doesn't know the animal. In the latter case, the program asks the user to tell it the animal. It is assumed that the user will also specify the correct pronoun before the name of the animal (as in "an aardvark" or "a giraffe"). Then the program asks the user to give it a question that distinguishes between this new animal and the one it found in its binary tree. (It is assumed that the user will give an actual question, ending in a question mark.) Finally, the program asks if the answer to this question would be yes or no for the animal that it has just learned. Now the binary tree is updated to contain all of this new information.
  
  
• The player should be asked if she or he would like to play again. If the answer is yes, the game should repeat from the root of the tree.

The only "grungy" aspect of this project is that of getting input from the user. To demonstrate how input works in Java, we have provided a small demonstration program called IO.java in the directory /cs/cs60/assignments/assignment3. You may use any and all of this code in your own code.

Think about the design of your code before starting to program. We will be grading this program for both functionality and good style. Regarding style, keep the following in mind:

• Break up the problem into small logical chunks and make sure that your methods are short and elegant. The code should be relatively easy for somebody else to read and comprehend.
• You will need to define a Node class representing a node in the binary tree. Every internal variable in your Node class must be private. You should use getters and setters to get and set the values of these variables.
• Remember to avoid the use of "magic values" in your code.
• Finally, remember to document your code by providing a header with your name, file name, and date and a description of what the file does. In addition, have at least one line (and ideally even more) of explanation for each method in your code.

Please submit all of the files that comprise your implementation of this game. Undoubtedly, you will have a file describing a node in the binary tree as well as the executable program. If you wish, you can have other files as well. You can use cs60submit multiple times, once for each file that you need to submit.

For Optional Bonus Credit (15 Points) write another version of this game called Bonus.java which allows the user to save the binary tree in a file before quitting the game. When the game starts, the program asks if the user would like to load in a file that was saved earlier and, if so, prompts the user for the name of the file. When the game ends, the program asks the user if the game should be saved to a file and, if so, prompts the user for the name of the file. Note that we haven't talked about file input and output in class. Take a look at the java documentation available on the course web page. Part of the objective of this bonus problem is to figure out how file input and output work. You can, of course, use the IO.java code in any way you like.