CIT 597 Assignment 8: The Animals Game
Fall 2008, David Matuszek

Purpose of this assignment:

General idea:

"Animals" is an old text-only computer game. The user thinks of an animal, and the computer asks a series of yes-no questions, ending with guessing the animal. If the computer guesses wrong, the computer asks the user about that animal, so that it can guess better next time.

The program starts with a very simple decision tree, such as the one on the left. Play goes something like this:

Computer: Think of an animal. Hit Return when you're ready.
User:
Computer: Does it live in the water?
User: No.
Computer: I know! Is it a horse?
User: no

At this point the computer has "lost." It then asks the user for information that it can use to enlarge its decision tree, like this:

Computer: What animal were you thinking of?
User: A zebra.
Computer: What question should I ask to distinguish a horse from a zebra?
User: Does it have stripes?
Computer: What is the correct answer for a zebra?
User: Yes.

The computer can now replace its wrong answer ("horse") with a new node containing a question, with its wrong answer as one child and the new animal as the other child.

Programming details:

Implement a BinaryTree class. This class can be quite small--only implement what you need for the Animals game. You will need to walk down the binary tree, create new nodes, and replace the text in a node.

In this application of a binary tree, the root and the internal nodes will hold questions; the leaves will hold the names of animals. Even though you are programming a minimal binary tree class specifically for this assignment, please keep the class general--don't put methods in it that are unique to the Animals game.

Do a little text cleanup. When the user answers something like "A zebra.", you should save this as just "zebra". When the program guesses an animal, put "an" before names that begin with a vowel, "a" before names that begin with a consonant. For yes/no questions, accept any answer that begins with a capital or lowercase y or n, otherwise repeat the question.

The binary tree should continue to grow as the user plays and enters new animals. When the program ends, all the data can be discarded--you do not need to save it from one run of the program to the next (but there will be some extra credit if you do).

Due date:

Wednesday, November 19, by midnight. Submit, via Blackboard, one file named animals.rb.