The goal of this lab is to practice program design, including file I/O and handling exceptions.
In class yesterday we wrote most of a program to play the game of twenty questions, with the goal of making the program able to learn as it plays. You’ll first complete that program, then you’ll extend it so that it can stores the question it “learns.”
Clone the repository with our work from class:
Take a few minutes to review the code. The class QuestionsGame contains the main() method plus a collection of other static methods that handle interaction with the user. Our tree is built from the interface TreeNode and two classes that implement it, Question and Answer.
(If at some point you want to look at the code for the list classes we worked on in class, clone
/cslab/class/csci235/in-class/12-02 into another directory.)
As class ended, we had just figured out how to make the program learn: when the program has asked about a leaf node (class Answer) and is told that the answer was incorrect, it needs to grow the tree, replacing the incorrect Answer node with a new subtree that contains the old (incorrect) answer and a new node for the correct answer as the children of a new Question node that is able to distinguish between them. So we had just changed the ask() methods so that they return a (possibly new) node; that node is the one that should occupy the place of that node in the tree. And each call to ask() was changed to an assignment that would make that change.
At the root of the tree (in method main()), playing the game changed from
to
The non-leaf (Question) nodes are never replaced; so they always return this. But they re-assign the child when they ask it, because that subtree might grow.
In a leaf node, we call the static method learn() when we need to grow the tree. We pass the leaf node that has turned out to be incorrect to learn(), because the wrong answer will be one of the children of the new node we get back.
Take a close look at learn(), which I filled in when class ended. You should be able to tell that it doesn’t actually learn anything, but it does satisfy the basic contract for the method: it returns the incorrect Answer node. That isn’t very smart, but it is a node that can properly occupy that place in the tree. An implementation of a method or class that doesn’t completely work is often called a stub. Writing stubs is a helpful technique, because it lets you work on (and perhaps even test) other parts of the program before you complete the method. With this stub in place, we could construct a small tree in main() and see that most of the other mechanics of the program work.
With that stub in place, I have fleshed out a few other parts of the program. I filled in the comments describing each of the files, methods, and instance variables. I also modified the main() method so that it gives the user a chance to play the game more than once.
So compile the program and check that it works, after a fashion.
Your first task is to complete the method learn(). That method begins with an incorrect Answer node (named wrong); it needs to finish be returning a new Question with an appropriate question and wrong and another new Answer as its (properly arranged) children. You will need to prompt the user for the missing information.
Once you get that working, you can simplify the initial tree; the program can start with just one Answer as the root node. Pick your favorite animal.
This would be a great time to commit your code to the repository. Have some fun, but don’t take too much time, because there is more to do.
Every time the program starts, it knows only the one answer with which it has been primed. It will be much more interesting if it saves all of the questions and answers that it has learned, so that it starts up everytime with all of its information present.
You can divide this into three parts:
Read the rest of this section before you start, because these three pieces interact.
Think carefully about how to represent the nodes as text. When you read the data, you’ll need to be able to tell where a new node begins, and you’ll have to be able to be able to tell which kind of node you have before you can create it. Because a file is sequential, you’ll need to choose what order to put the nodes in. (Do you remember what the options are?)
You might want to mock up a file using Emacs: make a file that contains what you think a small tree should look like.
Note that for writing out the tree, you’ll probably want a method that takes a filename and a root node and writes the entire tree to the named file. The writing of nodes (and subtrees) will require adding a method to the TreeNode interface and each of its implementing classes.
When it comes to reading in the data, you probably want a method that takes a filename and returns a tree. Reading and constructing a node is a little bit tricky, because you don’t know what kind of node to make until you have read in at least part of it. So you’ll probably need a static method that makes a node from an open file. Because trees are naturally recursive, you will probably need to add a new constructor to one or more of the node classes, passing it the open file along with whatever you’ve already read of the node.
You’ll need to hook your new capabilities into the program. Add a call to write the tree to the file named animals.dat immediately before the program exits. Then add code where the tree is initialized to try to read it in from the same filename, but provide a default tree (of one animal) in case that doesn’t work.
Finally, go back through and make sure that your program catches exceptions when reading or writing the file and does something appropriate.
Commit your program again.
Remove (or rename) the file to which your tree has been saved. Then make a typescript of the following:
Don’t forget to end your typescript.
If you have time, fix some of the rough spots in the program. Here are a few ideas:
For each improvement that you make, add a note to the comment at the beginning of QuestionsGame.java.
Turn in your source files as lab19 with the command