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 your documentation and in comments in the code itself.
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,
changeling dictionaryfile firstword secondwordshould run compute a solution to the changeling starting at firstword and going to secondword using the indicated dictionary file. Second,
changeling dictionaryfile changelingfileshould 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 one way. 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 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.
These editors are, essentially, one-line-at-a-time editors. In response to a prompt, you issue commands that usually affect the current line (that is, the most recently printed line). So, for example, a typical session using edit on this file might look like this:
knuth> edit final.txt [Editing "final.txt" 151 lines, 1884 characters] CS 127 1> 1,3 CS 127 Winter 1998 Final Projects 3> d Due: 5:00, Wednesday March 18 3> a This is a new line typed by the user. The additions end with a period alone on a line. . 5> s [Saved "final.txt" 152 lines, 1884 characters] 5> q [Bye-bye] knuth>
Here, we have started editing the file "final.txt," asked to look at lines 1 through 3, deleted line 3 (making the old line 4 into the new line 3), added two new lines of text, saved the resulting file, and quit.
To get a better idea of how edit actually works, you can run it yourself in any UNIX window. Note that my example above is a bit different from the real edit. I have included the current line number in the edit prompt, enclosed all editor messages in square brackets, replaced the "w" ("write") command with the "s" ("save") command, and printed the first line as soon as the editing session began. If you want to make small modifications of this nature, do so, but document them well.
The core of this project will be to implement a small version of edit that includes the following commands:
M,N Print lines M through N, inclusive. <return> Print the next line. a Add new text following the current line. The new text will be ended by a period alone on a line. i Insert new text before the current line. The new text will be ended by a period alone on a line. d Delete the current line. /bleah Print the next line on which the string "bleah" occurs. s Save the file. q Quit
In addition to the core, you might add the ability to copy, cut, and paste lines, save to a new file, start editing a non-existent file (that is, create a new, empty file and start editing it), make global substitutions of one string for another, undo the previous operation, etc.
One of the biggest decisions you will need to make for this project is how to store and manipulate the text file you are editing. Ideally, your program should be able to handle an arbitrarily large file. Thus, if you shoot for the ideal, you won't be able to declare a fixed-size array in which you will store the entire file. Even if you do work with a fixed-size array, you'll need to make sure that your various operations take a reasonable amount of time (for example, finding the next occurrence of a string should take less than a second to keep your user from getting cranky).
Plan the order in which you are going to implement the features of your program. You need a list of code segments to write, along with ways to test them. If you design a sequence of small, testable steps for your development, you'll be much more likely to finish your program successfully than if you try to write large blocks of code before testing anything. Planning ahead may seem the stodgy way to go, but it's also more successful in the long run (and, usually, in the short run, too).
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.