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.
The cost of applying
one of these additional transformations (the cost of changing a letter
is always 1), is the length of the longer string in the transformation.
In other words, converting from bend to blend costs 5,
as does converting from blend to bend.
Example: to convert from ask to way
you might get the sequence
ask, as, was, way, total cost of 7,
but maybe you can do better without adding or removing letters.
What To Submit
Submit all your source code and the results of running the program
on pairs of words that
I will specify, using a dictionary I will provide.
Include in your program timing data that shows
- The time to read the dictionary and build whatever internal data
structures you need.
- The time to process each query. Exceptionally fast implementations
may warrant extra credit.