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

In this assignment you will implement the 20 Questions Game, described in class, using Java. This is a lot of fun but also requires some careful design. There is also a completely optional bonus problem, which will make your 20-questions program considerably more powerful. This assignment is again a step up from the last three, please try to start early!

You will find a 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 by running

  java twenty_questions

• 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 throughout 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 article ("a" or "an") before the name of the animal, e.g., "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 then 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. If the answer is no, the game should thank the player for playing and then list all of the animals that it knows. This listing should be printed using a recursive traversal of the tree. You should not store the names of the known animals in another data structure (e.g. an array or linked list) - the tree should be the only place where this data is stored. For full credit, keep this code as simple and elegant as possible.

The only slightly "grungy" thing 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. If the game is implemented in a single long method, or even a small number of long methods, this is hard to read and debug. Each method should generally be short and have a specific purpose. This will help make the code 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 numbers" (or magic values of any sort!) 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 class. If you wish, you may have other files as well. You can use cs60submit multiple times, once for each file that you need to submit. Alternatively, if you type cs60submitall and hit the RETURN key, all of the java files in the directory in which you are currently located will be submitted. cs60submitall will show you the name of each file that it is sumbitting for you. Pretty nifty!

• Optional Bonus Problem (15 Points): Write another version of the 20 questions game called Bonus20.java which allows the user to read in data from a file when starting a new game and also to save the current state of the game to a file when ending the game. This requires some careful thinking and only a very little bit of code! Specifically, 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. However, in the directory /cs/cs60/assignments/assignment3/bonus/ you will find two files, one named Fileread.java and one named Filewrite.java which demonstrate the use of files. You may copy and modify these files in your program as you wish. Note that you cannot simply save the tree as a file "as is" because the tree is made of interconnected nodes which are not items that Java knows how to save in a file. However, strings can be easily saved and read from files (as the provided sample code illustrates). Therefore, the file will need to be some sort of string representation of the game tree -- that representation is your choice!
  
  Submit your Bonus20.java file and any other files which your program requires.