You may talk to other people about your project, and you may help one another, but you should write and hand in your own program. If you get significant help from someone or borrow a small piece of code, acknowledge that help in both your documentation and in comments in the code itself.
By 5:00 Monday, March 15, submitted via HSP.
A readme file that contains
Your program's source code.
In the crossword puzzle books I buy, there is a kind of word puzzle called a Changeling. A changeling (in this context, anyway) is a pair of words with the same number of letters. To solve the changeling, you show a sequence of words, each differing from the previous word by a single letter, that transforms the first word of the changeling into the second.
For example, one solution to the changeling "CAT to DOG" is "CAT, COT, DOT, DOG." The intermediate words must, of course, be words (and in fact, my crossword books say "words beginning with a capital letter, slang, obsolete words, and contractions are not allowed"). Note that in this example, we have the smallest possible number of words, since CAT and DOG differ in three letter positions, and there are three letter transitions in this solution. In a contest of changeling solutions, short solutions win. (Actually, short and clever solutions would be better than the short and dull solutions that are most common, but I won't ask you to write a program to judge cleverness.)
For this project, you will write a program that uses a dictionary to compute solutions to changelings.
To make your changeling programs uniform (so it's easy for me to test them all in the same way), I want you to implement the following command-line interface. The user should be able to run your program in one of two ways. First,
java Changeling dictionaryfile firstword secondword
should compute a solution to the changeling starting at firstword and going to secondword using the indicated dictionary file. Second,
java Changeling dictionaryfile changelingfile
should compute solutions to the changeling word pairs that appear, one space-delimited pair per line, in changelingfile. If the user runs the program with some number of command-line arguments other than two or three, the program should print an appropriate usage message and exit.
So, how are you going to compute changeling solutions? There are undoubtedly many ways to solve this problem, but here is the way I want you to do it. Build a graph out of the dictionary file where each word is a vertex of the graph and two words/vertices are connected if they are the same length and differ by only one letter. Then use a breadth-first search starting at the first word until you find the second word. Then print out the path, if any, that you discovered in this way.
Building the graph can be done more efficiently than by comparing every pair of words (an Omega(N^2) process that would take quite a long time on an 80,000-word dictionary). How to do so is part of what you need to figure out.
Think about this problem before running to the computer to start coding. It's not easy, but the program should be lots of fun to play with when you're done.
When you enter a formula into a spreadsheet, you typically cause the value of one cell in the spreadsheet to depend on the values in one or more other cells. For example, if you enter "=A1 + B1" into cell C1 (using a common cell-naming and formula-constructing scheme), you cause C1 to depend on both A1 and B1. If you then went on to enter "=A1 + C1" into B1, you would have a problem. C1 would now depend on B1, which in turn depends on C1. The spreadsheet would be forced to report an error. (Alternatively, the spreadsheet could loop infinitely, but that would probably reduce its utility.) When I try this using Microsoft Excel, I end up with a big error dialog, followed by some weird blue arrows connecting B1 and C1 to show me the circular references.
For this project, you will write a rudimentary spreadsheet program. This program should allow you to do the following:
Enter integers into cells.
Enter sums of other cells into a cell, using the "=A1+B1+C2" sort of notation.
Save a given spreadsheet in a text file, and load a spreadsheet from a file.
In response, the program should:
Display the numerical value of each cell.
Report any circular references in a comprehensible way.
The file format for the stored spreadsheets should look like this:
A1:5 A2:37 B2:=A1+A2 A3:=A2+B2
That is, each line of the file will represent a single cell, with the cell's column and row (A and 1, for example) followed by a colon, followed by the number or formula in the cell.
You may design either a text-based user interface or a graphical user interface. That part of the program is not easy to design, but you can certainly take hints from existing spreadsheet software.
To compute formula values and to detect circular references, you should build a dependency graph out of the cells. That is, let all non-empty cells be vertices in the graph. There is a directed edge from cell V to cell W if W contains a formula that refers to cell V. That is, arrows point towards the dependent cell. Once you have this graph, you can sort the graph topologically to determine the order in which you should compute values, as well as to detect circular references.
Successful compilation. If your program doesn't compile, I won't grade it.
Correctness. Your program needs to do the job it is intended to do.
Design. I will look for well-considered choices of data structures, classes, and methods, their return values, and their parameters. In the description of your project, you should explain your reasons for making the choices you made.
Style. I want to see good indentation, descriptive variable and function names, well-placed comments, consistent loop structure, and so on. Ideally, your code will be a pleasure to read. (This assumes a reader who enjoys reading program code, but you're in luck, since I am such a reader.)
Documentation. Your description of your project and the comments in your source code are important parts of your project. I want to be able to understand your project fairly well before diving into the code.
Performance. I will not run precise time tests, but I will frown on programs that take 10 minutes to process a single changeling.
Plan your program on paper. Do not start your work at the computer. For relatively large programs like these, forethought can save you a lot of time.
Design classes and methods that will make the main program easy to write. You want your methods to provide services to the rest of your code, and good design of those services can make the difference between code that is very straight-forward to write and code that acts like a tar pit. Think carefully about your classes. It's worth the time.
Make an incremental development plan. That is, make a list of things you will make your program do, in the order in which you will write the code. Each stage of your development should be a small step that can be compiled and tested before you move on to the next step.
Ask questions. I will be very happy to help you when you're stuck. Pride and a two-week deadline don't mix very well.
Start early, have fun, and keep in touch.