Due: Tuesday, Nov. 14, 8am
The files for this assignment can be found in ~ola/cps100e/ladder. These files are itemized below and a listing of some are attached as an appendix to this document.
Makefile, QueueAr.h, QueueAr.cc, StackAr.cc, StackAr.h, Exception.cc, Exception.h, globals.h.
In your cps100e directory, you should create a directory prog4. All work for this assignment will then be done in the directory ~/cps100e/prog4.
You should copy the files for this assignment into your prog4 directory. To do this, cd into the prog4 directory you created and type cp ~ola/cps100e/ladder/* . (don't forgot the final .).
For this assignment, you'll be using a database of English five-letter words from the Stanford GraphBase (a list compiled by Don Knuth). This list has about 6,000 words in it. There is a smaller file of data to work with also.
In your prog4 directory, create a link to these data files by typing:
ln -s ~ola/data/knuth.dat knuth.dat ln -s ~ola/data/words5.dat words5.dat
Word Ladder: Turning Stone into Money
The input to word ladder is two words of the same length, the output is a sequence of words in which consecutive words share all but one letter, starting with the first word and ending with the last. One letter can be changed to another letter only if the resulting symbols form a valid word. For example, to turn stone into money, one possible ladder is (replace 't' by 'h', replace 'o' by 'i', etc.):
stone shone shine chine chins coins corns cores cones coney moneyAll of these words can be found in the Knuth file and in a dictionary.
Assignment: Part I
You are to write a program ladderq.cc that uses a file of 5-letter words to find the shortest ladder from one word to another. You may want to develop a class to do this (e.g., class Ladder), but you do not have to. However, you should not, in general, use global variables in a program. A class lets you have private data that is global to each member function.
Your program should:
> ladderq Enter two 5-letter words (length != 5 to end): smart brain smart start stark stack slack black blank bland brand braid brain Enter two 5-letter words (length != 5 to end): angel devil There is no path from angel to devil Enter two 5-letter words (length != 5 to end): no more
The file knuth.dat has extraneous information in it. Ignore lines that begin with *, and only process the first 5 characters on other lines. Knuth asks that the file not be altered, hence these restrictions.
To find the shortest ladder, you should use the Queue class provided. First, store all of the words from the file in a vector of type Wnode.
struct Wnode
{
string word;
Wnode * prev;
};
(this assumes the use of the class string from CPstring.h. You
can use some other kind of string if you want).
When the user enters a word, put a pointer to the struct containing the word onto the queue (it's a queue of Wnode pointers). Then repeat the dequeue/enqueue process below.
Dequeue an element (it's a pointer). Find all words one letter apart from the dequeued word. If one of these is the target word, you're done. Otherwise enqueue each of the words found if it hasn't been queued up before (you can use the pointer fields in a Wnode to determine if a word has been enqueued before). Note that this means each word is enqueued at most one time.
When the target word is derived, you'll need to print out the ladder from the first word to the target word. You can use the prev pointer in the Wnode to store information that will allow the ladder to be recreated.
The output for each word pair should also include the number of words enqueued (this is not shown in the sample output above).
To use the templated Queue class you'll need a separate file templateq.cc (you'll need to create a similar templatest.cc for part II of this assignment). This file is illustrated below.
#include "QueueAr.h" #include "QueueAr.cc" #include "globals.h" template class Queue <Wnode *>;
If you want several kinds of queue, just put another definition in the template.cc file. Once the template.cc file is compiled to template.o, you only need to relink, not recompile, every time you make a change in ladder.cc.
Repeat part 1 of this assignment, but use a stack instead of a queue. Name this program ladderst.cc. (DO NOT simulate a queue with a stack, just replace the queue by a stack.) Replace all Enqueue operations with Push operations, all Dequeue with Pop, and all GetFront with Top. Otherwise the program should work the same way. However, your program will not necessarily find the shortest ladder.
You should create a README file for this and all assignments. All README files should include your name as well as the name(s) of anyone with whom you collaborated on the assignment and the amount of time you spent.
To submit your assignment, type:
submit100e prog4 README ladderq.cc ladderst.cc
Write a new version of ladderq.cc called ladxtra.cc. Preprocess the words when they are read in so that only ``good'' words are tried as one-letter-off matches, not every word is tried. Instead, only try words that are in fact one letter off. This will involve comparing all the words when they are read in and somehow keeping track of which words are one letter apart. This will make the program run much more quickly since not all words will be considered as candidates.
To submit the extra credit assignment, type:
submit100e prog4Xtra README ladxtra.cc