The Game of 20 Questions: In this assignment you will implement a yeso 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 (Though the game is called "20 Questions," our game will not limit the tree to a height of 20. Any height is 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. overall root (lefi- "yes") (right - "no") Is it an animal? Can it fl Does it have wheels? bird Does it have a tail? bicycle Is it nice? mouse ider TA teacher The following partial output log shows one game being played on the above tree Is it an animal? ves Can it fly? no Does it have a tail? ves Would your object happen to be mouse? yes I win! Initially the computer is not very intelligent, but it grows smarter 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: (You must match the format of the logs in this spec exactly; use the Output Comparison Tool on the course web site.) Is it an animal? ves Can it fly? no Does it have a tail? yes Would your obiect happen to be mouse? no I lose. What is vour obiect? cat Type a yeso question to distinguish your item from mouse: Does it meow? And what is the answer for your object? yes l 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 overall root (left - "yes") (right = "no") Is it an animal? Can it Does it have wheels? bird Does it have a tail? bicycle Is it nice? Does it meow spider TA teacher mouse In this assignment, you will create classes QuestionTree and QuestionNode to represent the computer's tree of yeso 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! Snall _ recall our previous games? n 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 Think of an item, and I will guess it Would your object happen to be computer? n I lose. What is your object? cat Type a yeso question to distinguish your Does it have wheeIS? yes item from computer: Is it an animal? And what IS the answer tor your object ? y Challenge me again? y Is it an animal? no Would your obiect happen to be bicycle? ves I win! Challenge me again? yes Is it an animal? n Would your object happen to be computer? n Can it fly? no I lose. What is your object? shoe Is it an animal? yes Does it havea tai1? yes Type aroescomput estiones idi go on youryfert? Wou deyouhatb1ectou appen to beat use? n Chalienge me agay tor your opject? XiYem from mouse: Does it meow^ngusnyour item from mouse: Does it meow? And what is the answer tor vour obiect? yes Challenge me again? yes Is it an animal? n Does it go on your feet? Would your object happen to be shoe? y I win! Challenge me again? n Is it an animal? yes Can it fly? no Does it have a tail? yes Does it meow? ves Games played: 3 I won: 1 Shall I remember these games? y What is the file name? guestionl.txt Would your object happen to be cat? yes I win! Challenge me again? no Games played: 3 I won: L 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 questionl.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 questionl.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 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 lic 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 "computer" in it. The tree will grow larger as games are played or as a new tree is loaded with the load method described below ublic void play () A call to this method should play one complete guessing game with the user, asking yeso 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. ublic 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 uestion1.txt uestion2.txt :Is it an animal? A:cat Q:Is it an animal? Q:Can it fly? A:bird Q: Does it have a tail? A:mouse A:spider Q: Does it have wheels? A:bicycle Q:Is it nice'? A: TA A:teacher Q:Does it go on your feet? A: shoe A:computer ublic 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.) ublic int totalGames ) ublic 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 corectly 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 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) public void println (String message)i// displays an output message and new-line public String nextLine ); public boolean nextBoolean ); // displays an output message to the user // waits for user to type a stringi returns it // 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 yeso question ui.print("Are you having a nice day?" if (ui.nextBoolean)) ui.println("That is good to hear!") // true means user said "yes" ui.println ("Sorry to hear that."); else [ // 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 = u.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 If you are unfamiliar with PrintStream or Scanner, consult textbook Chapter 6 or the Java API documentation. 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 "r = change( 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 tum 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 both files descriptively in your own words at the top of each 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. The Game of 20 Questions: In this assignment you will implement a yeso 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 (Though the game is called "20 Questions," our game will not limit the tree to a height of 20. Any height is 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. overall root (lefi- "yes") (right - "no") Is it an animal? Can it fl Does it have wheels? bird Does it have a tail? bicycle Is it nice? mouse ider TA teacher The following partial output log shows one game being played on the above tree Is it an animal? ves Can it fly? no Does it have a tail? ves Would your object happen to be mouse? yes I win! Initially the computer is not very intelligent, but it grows smarter 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: (You must match the format of the logs in this spec exactly; use the Output Comparison Tool on the course web site.) Is it an animal? ves Can it fly? no Does it have a tail? yes Would your obiect happen to be mouse? no I lose. What is vour obiect? cat Type a yeso question to distinguish your item from mouse: Does it meow? And what is the answer for your object? yes l 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 overall root (left - "yes") (right = "no") Is it an animal? Can it Does it have wheels? bird Does it have a tail? bicycle Is it nice? Does it meow spider TA teacher mouse In this assignment, you will create classes QuestionTree and QuestionNode to represent the computer's tree of yeso 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! Snall _ recall our previous games? n 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 Think of an item, and I will guess it Would your object happen to be computer? n I lose. What is your object? cat Type a yeso question to distinguish your Does it have wheeIS? yes item from computer: Is it an animal? And what IS the answer tor your object ? y Challenge me again? y Is it an animal? no Would your obiect happen to be bicycle? ves I win! Challenge me again? yes Is it an animal? n Would your object happen to be computer? n Can it fly? no I lose. What is your object? shoe Is it an animal? yes Does it havea tai1? yes Type aroescomput estiones idi go on youryfert? Wou deyouhatb1ectou appen to beat use? n Chalienge me agay tor your opject? XiYem from mouse: Does it meow^ngusnyour item from mouse: Does it meow? And what is the answer tor vour obiect? yes Challenge me again? yes Is it an animal? n Does it go on your feet? Would your object happen to be shoe? y I win! Challenge me again? n Is it an animal? yes Can it fly? no Does it have a tail? yes Does it meow? ves Games played: 3 I won: 1 Shall I remember these games? y What is the file name? guestionl.txt Would your object happen to be cat? yes I win! Challenge me again? no Games played: 3 I won: L 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 questionl.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 questionl.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 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 lic 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 "computer" in it. The tree will grow larger as games are played or as a new tree is loaded with the load method described below ublic void play () A call to this method should play one complete guessing game with the user, asking yeso 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. ublic 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 uestion1.txt uestion2.txt :Is it an animal? A:cat Q:Is it an animal? Q:Can it fly? A:bird Q: Does it have a tail? A:mouse A:spider Q: Does it have wheels? A:bicycle Q:Is it nice'? A: TA A:teacher Q:Does it go on your feet? A: shoe A:computer ublic 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.) ublic int totalGames ) ublic 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 corectly 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 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) public void println (String message)i// displays an output message and new-line public String nextLine ); public boolean nextBoolean ); // displays an output message to the user // waits for user to type a stringi returns it // 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 yeso question ui.print("Are you having a nice day?" if (ui.nextBoolean)) ui.println("That is good to hear!") // true means user said "yes" ui.println ("Sorry to hear that."); else [ // 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 = u.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 If you are unfamiliar with PrintStream or Scanner, consult textbook Chapter 6 or the Java API documentation. 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 "r = change( 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 tum 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 both files descriptively in your own words at the top of each 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