Assignment #5: Word Changing

In this assignment, you will solve a generalized version of the word changing problem.

Covers

Graph algorithms, binary heaps, advanced Java programming.

The basic problem

A word can be changed to another word by a 1-character substitution. The basic problem would be to write a program that reads the dictionary and then repeatedly prompts the user for words A and B. The program determines if a word A can be transformed to a word B by a series of 1-character substitutions, and if so, outputs the corresponding sequence of words (using the fewest number of substitutions). As an example, bleed converts to blood by the sequence bleed, blend, blond, blood.

The actual problem

To make things more interesting, we will add an extension that allows two additional ways to transform words. First, you can add a letter (converting a k-character word to a k+1-character word); second you can remove a letter. However, these transformations are not as desireable as simply changing a letter. Hence, the user will specify, either by command-line argument or by input from System.in (your choice), the cost of applying one of these additional transformations (the cost of changing a letter is always 1), and now your problem is to find a transformation of minimum total cost. Example: to convert from ask to way with a cost of 4 for adding or removing a letter, you might get the sequence ask, as, was, way, total cost of 9, but maybe you can do better without adding or removing letters. Observe that if the cost of an additional transformation is huge (larger than the number of words in the dictionary), then the transformation is applied only as a last resort, if no sequence of 1-character substitutions is available at all.

What To Submit

Submit all your source code and the results of running the program on pairs of words and transformation costs that I will specify, using a dictionary I will provide. Include in your program timing data that shows
  1. The time to read the dictionary and build whatever internal data structures you need.
  2. The time to process each query