CSE326
Summer 2004
Assignment 2
6/25/2004
Due: At beginning of class, Friday 7/2/2004

Working with a partner, develop an algorithm and write code to solve the Word Finder Puzzle.  Turn in the code along with some test data and an analysis of your solution algorithm.

Specifically, write a class called WordFinderPuzzle which reads a puzzle from a file and has methods for displaying and solving.  Even more specifically: on the web you will find code for a Java interface called IWordFinder (in package wordFinderPuzzle).  Make your class implement this interface (and put it in the same package).  You will also find a class already written called WFPuzzleReader, which is capable of reading in a text file containing the puzzle.  Call that in your WordFinderPuzzle class constructor to read in the puzzle.  After you have read the comments in the IWordFinder.java and WFPuzzleReader, you will understand a bit more of the details of what is asked for.  Please do read that carefully before you begin any coding!

Link to all files (by the way, in case you didn't notice, the /docs directory has some Javadoc). Added 6/28:  A .jar file with the binary (.class) files for all the packages.  See the Message Board for explanation.

The rules for the puzzle are basically the same as for the ones you solved with pencil and paper.  Some notes and/or differences:

• The matrix of characters can be any size above a minimum ("any" within the practical memory limits of the computer, as usual with the size of problems).  The pencil-and-paper puzzles were all 18x18.  If you wish, you can assume the matrices are always square, and that is all we will test you on.  However, you are strongly encouraged to write the program to allow any rectangle dimensions
• The puzzle matrix and characters may have upper and/or lower case letters.  You can assume case-sensitivity if you wish.  That is, the characters in the puzzle matrix and the characters of the words being looked for must match.  The test files we use will always have either all upper case or all lower case, and will not have any non-letter characters.
• It is possible that some words on the list might not be in the puzzle.  Please allow for this!
• It is possible that words on the matrix might overlap in arbitrary ways.  On the pencil-and-paper puzzle they only overlapped at the beginning and ends of words.
• It is possible that some words might occur more than once in the matrix.  You are only required to find one of the occurrences (in case there is more than one), but you are encouraged to find them all.

In addition to the program, please create one significant legal puzzle file and turn it in.  (It can be based on a puzzle from a published puzzle book or from the web).

Your analysis should be written separately from the program and turned in on paper.  Your arguments can be informal.  They should include complexity function(s) and big-O analysis, and explanations or arguments or experments supporting your analysis.

There should also be a (very short) written report about how well your algorithm runs on certain test files which we will designate.

The exact method for electronic turn-in will be specified later; expect the deadline to be Thursday evening.

Other notes:
The packages MDUtils and textfile contain some classes used by the WFPuzzleReader.  They need to be copoied to your system and put on the classpath so that WFPuzzleReader will compile and execute, but otherwise you don't need to look at them.