CMSC 341 Fall 2007
Project 3
Assigned
| Monday, Oct 15, 2007
|
Due
| 11:59pm, Friday Nov 2, 2007
|
Intermediate deadline
| Mon Oct 22, 2007
|
Updates
| Tues. Oct 30, 2007
|
Objectives
- To implement a tree ADT from scratch
- To create and extend ADTs to serve a particular purpose
- To perform file IO in java
- To explore the effects of caching results on performance
Overview
In this project, you will build an interactive advisor for the Ghost word game. This
advisor will read in a dictionary of words, store them in an appropriate ADT,
use this ADT to make recommendations on which play should be made next, and
build a displayable tree structure.
We will give
you basic UI code and a display helper class,
as well as specify an interface that you must implement for
the WordTree clas. Other class design choices are yours.
Rules of Play
Ghost is a word game played with n players. The objective is to add letters to a word
fragment in such a way that the fragment does not complete a word but is still the beginning
of a legitimate word. The first player starts with any letter. Each player, in turn, must
add a letter. The first player to complete a word (of three or more characters)
or fail to add a letter loses the round. A player who cannot think of a letter which keeps the
word alive without completing it may bluff. Another player can call the bluff and ask for the
word in mind. If there is no such word (ie. it was a bluff), the bluffing player loses the round.
If there was a word, the calling player loses the round.
A losing player gets a penalty letter -- first 'g', then 'h', and so on until 'ghost' is spelled
out. The player who lost the round starts the next round.
Rounds continue until one player has spelled out the word 'ghost' in penalty letters.
For example, a three player game might start like this:
Player 1: a (might be thinking of 'apple')
Player 2: s (thinking of 'astrology'; two-letter word is OK)
Player 3: p (thinking of 'asparagus', forgetting 'asp' is a word)
Player 3 gets 'g'
Player 3: d (thinking of 'destiny')
Player 1: a (thinking of 'dastardly')
Player 2: w (thinking of 'dawn', hoping to force next player out)
Player 3: d (thinking of 'dawdle')
Player 1: l (thinking of 'dawdle')
Player 2: i (thinking of 'dawdling')
Player 3: n (thinking of 'dawdling')
Player 1: g (forced to finish 'dawdling')
Player 1 gets 'g'. Player 1 and 3 tied at 'g'.
Project Specification
In this project you will be implementing a tree class, named WordTree, from
scratch. Its constructor should take the string specifying a file name
containing a list of the legitimate words (or dictionary). It should build a WordTree from
this list. It should also provide methods to build a displayable list,
return the displayable list, and recommend a next letter to give after the
partial word passed as parameter. Think carefully about what properties you want
your tree to have -- before you start writing code. There are many types of trees and some
are not well-suited for this application.
The recommend function takes a partial word and number of players as arguments. If the partial word
can not be found as an interior node of the tree (ie, there is no valid word starting with that
fragment), the function should return '@'. Otherwise, the method should analyze the subtree beneath
the node containing the frament. A good choice is one which does not complete a word (ideally,
even on your next turn, which is why the number of players is required).
Recommend which letter would be the best choice to play
next.
We will be providing you with the code for the UI, which looks like this:
This is the tree built from the file 'fewwords.txt', after a path has been manually opened up
to the word 'help'. Word fragments can be typed in the bottom textbox and recommendations
requested by pushing the 'Recommend' button.
The program takes four possible command
line arguments (processed in the provided code): a history flag
(as in Proj 2), a number of players (betwen 1 and 9), a filename for the list of valid, and (optionally) a list
of word fragments to make recommendations on.
The provided code parses command line arguments, calls the WordTree constructor, creates a
user interface including a displayable tree created by methods of the WordTree class, reads in the
list of word fragments to get recommendations about, and then gets recommendations of typed in
fragments.
When the history flag is set, you should print out the tree created (marking which nodes
correspond to valid words),
the recommendations for next letters, and some
justification for why that recommendation was made (ie the values of some
metrics that you computed to compare it to other possibilities).
Dr. Rheingans' public directory for this project is
/afs/umbc.edu/users/r/h/rheingan/pub/341/Proj3 and it contains Proj3.java,
the interface specification mentioned above, two dictionaries of valid words ('words.txt' and
'fewwords.txt'), and
a list of partial words to make recommendations on ("fragments.txt").
You should write your code to access the dictionary where it is, rather than copying it
to your directory and accessing it locally. Call the program with the full pathname of the files
on the command line.
Project Notes, Hints, and Requirements
- This project can be developed using the Eclipse Integrated Development Environment (IDE).
- By the intermediate deadline, hand in a description of the type of tree you intend to
implement (about a paragraph) and a picture of the tree created from the file 'fewwords.txt'.
A hand-drawn picture is fine. Give both the description and the picture to your instructor at
the next class after the deadline (ie, either Tues 23 or Wed 24, depending on when your section
meets). You may change design choices later, but you must submit the initial
design by the intermediate deadline.
- You must implement your WordTree class from scratch, with nothing but Object,
primitive types, or classes you develop from scratch yourself as a superclass of WordTree or
any data elements of WordTree.
- You may not change the WordTreeInterface.
- As in previous projects, you should submit your project as a package (proj3).
- To create the file containing your output, use unix redirection on the command line to redirect standard output to a file. Thus, once you have the output on the screen as shown in the sample results above, then you can redirect your output to file by using the command java proj3.Proj3 -h > p3-output.txt.
- This project is an OPEN assignment (as was Project 2). You are still expected to write your
own code, but you may continue to help each other debug. Specifically, you:
- should try as much as possible to complete the project by yourself.
- may get assistance from anyone -- TAs, instructors, fellow students, relatives, friends, etc.
- must document all outside help you get as part of your file header comment.
You MAY NOT:
- copy anyone else's code
- have someone else write your code for you
- submit someone else's code as your own
Any help you receive must be documented, including discussion, books, papers, and web resources.
With each assignment, you will turn in a README text file indicating the sources you used while
working on it and the type of help you received from each. If you received no help, say so. If
you helped someone else, say so. Failure to include this README file will result in your program
being returned ungraded.
Extra Credit
There are MANY interesting ways to extend your base project. Be sure you
finish all requirements of the base project before you begin working on
extra credit.
Indicate any items of extra credit that you did in your README file. This will
allow the TA to look for that additional functionality when grading your
project.
-
Deciding what next letter to recommend, requires traversing the whole subtree rooted at the
current word fragment and calculating all possible outcomes. This might be very time consuming.
As play moves on to the next player, the subtree to be traversed is a child the last subtree
traversed, requiring a repeat of work already done.
Modify your WordTree to cache statistics in interior nodes. Compare the performance of
the cache-enabled WordTree to the original version. Write a one page analysis of the effects
of caching in terms of space and time. Discuss how performance changes as the game proceeds
(ie. as you work your way down the tree). Create your own partial word files containing test
cases which help you conduct a thorough analysis. Submit your paper in .pdf format.
Worth ten points. MANDATORY for H section.
-
Extend the GUI to expand the path to a fragment for which a recommendation is requested.
Worth five points.
-
Improve your recommend function to try to force your opponent(s) into completing words. Explain
your method in your README file. Worth five points.
-
Explore how your program scales up as the dictionary grows. Run your program on dictionaries of
differing sizes. Analyze how your program performs and how big the dictionary can grow before
your program begins to have problems. There is a big file of words available
in /usr/share/dict/words. You can use this for testing, as well as for creating testfiles of
a range of lengths. Discuss the results of your analysis and ideas for adapting your program
to handle longer dictionaries in a paper of about two pages. Submit your paper in .pdf format.
Worth ten points.
Files To Be Submitted
Submit the following files:
- *.java (including Proj3.java ),
- p3-output.txt,
- README,
- any items required for extra credit options
Project grading is described in the
Project
Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
course.
Remember, the due date is firm. Submittals made after midnight of the due
date will not be accepted. Do not submit any files after that time.