CSC 122: Computer Science II, Fall 2006

Project 4

Rumpelstiltskin

Deadline: Friday, December 8, 5:00 p.m.

Overview:

In the classic fairy tale "Rumpelstiltskin", a magical creature threatens to take a woman's baby unless she can guess the creature's name. She guesses names unsuccessfully for a while, then overhears that its name is Rumpelstiltskin and wins the challenge (I always considered this a bit of a cheat, and wondered just what the moral of the story was supposed to be, but that's beside the point...).

In this assignment, you will implement a program to play a name guessing game. To help the computer guess a name, after each incorrect guess you will tell it whether the desired name comes before or after the guess in dictionary order. When the program starts, the user can load in a list of common names from a file and store them in a binary search tree. Playing a game is then just following the process of searching the tree, with the twist that it asks the user which way to go from each node. If it finds the player's name in the tree, then the computer wins. If it reaches a point where there are no more possible names, then it gives up -- the user is then asked what name they were thinking of, and it is inserted at the correct position in the tree. In either case, the computer offers to play another round. At the end, the user is given the chance to save the names (including new ones learned while playing) to a file before exiting.

Specification:

The Guessing project has at least four classes:

1. Driver: Contains the method main, which creates an instance of GuessingGUI and invokes its start method. Driver will be used to run the application stand-alone (not in the BlueJ environment) once you have completed the rest of the project. You should test as you go by using instances of GuessingGUI, Game and the other classes you write.
2. GuessingGUI: Contains code that creates a Graphical User Interface with components that are used to accomplish interaction with the application (see below). You should not have to modify this class, but it is worth looking through the code to see how the methods in your Game class will interact with the GUI. It also contains the methods used by Game to communicate with the player and to open files for reading and for writing.
3. Game: Contains a skeleton of code with TODO comments indicating what needs to be filled in.
4. The fourth class will be some form of binary search tree, used by the game to hold the collection of known names. You may base this on the BST class discussed in class, or the version presented in the textbook; however, you will need to figure out how to adapt these classes to play the name guessing game (where the interaction with the user determines the search path through the tree).
5. You may choose to write or include additional classes or methods; a TreeNode class, for example. For each such class and method make sure to provide complete documentation using JavaDoc format.

The Project and Getting Started:

The Guessing project:

• The provided files can be copied from I:\10607_CSC122\public\Rumpelstiltskin. In addition to the Java files for the project skeleton described above, you will find a text file named 2Knames.txt which has the 2000 most popular baby names from 2005, according to the U.S. Social Security Administration (http://www.ssa.gov/OACT/babynames/); the names are arranged one per line, in order from most to least popular, so they are ready to be loaded in when playing the game.
• Implement the project using the test-driven implementation strategy: first build a test system and stubbed implementation of each class.
• When you write out the contents of the tree, you should perform a preorder traversal. This will allow the same tree structure to be created when the file is read back in. For each name traversed, write it to the file with the method call writer.println(name); (that is, you may use a PrintWriter object in the same way you use System.out).
• There is a demonstration version of the program in the public folder, named RumpelstiltskinDemo.jar -- it is an executable jar file which should run when double-clicked, if Java is installed correctly.

Standards:

Your project should be well-written, neatly-formatted, modular, and well-documented.

Grading:

• Correctly handling binary search tree operations (60 points)
  • write the tree to a file
  • insert a name
  • play the (binary-search-like) name guessing game
• Correctly filling in the skeleton of the Game class. (20 points)
• Documentation and style (20 points)

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated