Reference no: EM132333613

Assignment - This assignment provides practice with pointers, lists, file I/O, sorting, queues, and recursion.

Introduction - For this assignment, you'll be using a database of English five-letter words. This list has about 5,800 words in it. You can also make your own data files: one 5-letter word per line. You'll write a program to find word-ladders: connections from one word to another formed by changing one letter at a time with the constraint that each time a letter is changed, the resulting string of letters is a 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

money

All of these words can be found in the file and in a dictionary. Your program will find the shortest word ladder between two words you enter when running the program. There may be more than one shortest ladder, your program must find one, but not all such ladders.

You are to write a program named ladderq.cpp that uses a file of 5-letter words to find the shortest ladder from one word to another using a process outlined below. You must develop a class to do this, the class Ladder has been started for you, but you will need to add MORE member functions (both public and private).

Your program should:

1. Read and store the words from a file (specified by the user).

2. Prompt the user to enter two five-letter words (and continue to prompt). For each pair of words, output to the screen AND to an output file, wordladders.txt, a shortest ladder from the first word to the second. If one of the words is not of length 5, your program should halt.

Coding/Algorithm - To find the shortest ladder, you should use the templated Queue class that we discussed in class. First, store all of the words from the file in a vector of type Wnode * (this is done in LoadWords).

struct Wnode

{

string word;

Wnode * prev;

};

The vector is diagrammed as:

A ladder is found by putting the starting word (or rather a pointer to the Wnode that the word is in) on the queue, then putting all words 1 letter away from this word on the queue, then putting all words 2 letters away on the queue, then all words 3 letters away, etc. As each word is taken off the queue, if the last (target) word is found the process can stop (there may be other words on the queue, but they'll be ignored). This process is guaranteed to find the shortest word ladder.

A Word w isn't actually stored on the queue, a pointer to a struct containing w is stored. The other field of the struct is a pointer to the word that is one letter away from w and that caused w to be put on the queue (the word's predecessor). For example, if w is bears, then pointers to structs containing dears, fears, gears, beard (and so on) are enqueued with each struct pointing to bears since this word preceeded the others and caused them to be enqueued. The first word doesn't have a predecessor. It's field cannot be 0/NULL since this is used for another purpose. An easy fix is to make the pointer self-referential, it points to the struct itself (and this will need to be checked when printing ladders).

More Details - The first word (entered by the user) is looked up in the list of words, and a pointer to the struct containing the word is enqueued. Your program should be able to handle a first word even if the word is NOT in the list of words (all other words in the ladder, except perhaps for the last, must be in the list of words).

Put a pointer to the struct containing the first word onto the queue (it's a queue of Wnode pointers). So, let's assume, based on the example above, that we would like to build a word ladder where our starting word is bears and our target word is deals. We begin by first enqueueing the pointer to the Wnode containing the word bears. To be on the safe side, you should change bears Wnode's prev pointer to point to itself. The reason for this will become apparent as you continue. Once you have done so, you must then repeat the 'dequeue/enqueue' process listed below to build the ladder from bears to deals.

1) Dequeue an element from your queue (remember, what you are actually dequeueing is a pointer to a Wnode). This means, we dequeue the pointer to the Wnode containing bears. Why bears? Because so far, it is the only Wnode that has been enqueued! Now, we find each word that is one letter apart from the dequeued word (bears). In the example above, we find that the words which are one letter apart from bears are - dears, beard, fears and gears. Each time you find a word that is one letter apart from bears:

a. Check to see whether the current word is the target word (in this example, if it is the word deals). If one of these is the target word, you're done (or if one of the words is one apart from the target word you're done, you can stop early).

2) Otherwise, if each of the one apart words (dears, beard, fears and gears) isn't the target word deals or one apart from deals, enqueue each of them as long as they have not been queued up before (you can use the prev pointer fields in a Wnode to determine if a word has been enqueued before --- initially all prev fields should be set to 0/NULL, this helps determine if a word has been enqueued before). If a word's Wnode's prev pointer is 0/NULL set that word's Wnode's prev pointer to the address of the word that it is one letter apart from (in this example, it would point to the Wnode containing bears) and then enqueue it. This means each word is enqueued at most once. Continuing from our example, since none of the one-letter-apart words (dears, beard, fears and gears) is our target word deals, we must enqueue all of them and then repeat the process. However, the next time around when you dequeue, the word that will come up will be dears. Note that we could have stopped once we found the word dears because it is one apart of deals. However, continuing would still result in the same ladder because by enqueuing dears, we would end up finding deals which it is one apart from.

When the target word is derived, you'll need to print out the ladder from the first word to the target word. The prev pointer in the Wnode stores information that will allow the ladder to be recreated, you may need to use recursion or a vector since the ladder will be backwards (but should be printed properly). You could also search backwards, so to find a ladder from smart to brain search from brain to smart. OR, YOU CAN USE A STACK AND THEN POP which will simply reverse the items automatically. I prefer if you take the stack or recursive approach.

Ladder Member Functions -

You must implement the functions described below. You'll find it useful to implement other member functions. Sometimes the functions should be private. This is the case when a member function is a helper function for other member functions, but shouldn't be called by the user. Making a helper function private ensures that only other member functions can access the helper function, but client programs cannot.

• Clear(), sets all prev fields to 0/NULL.
• FindLadder(), tries to find a ladder between two words that are parameters to the function. FindLadder can return a boolean (and set some state in the Ladder class) or it can return a pointer. It makes more sense to return a boolean and store the beginning of the ladder (if one was found) in a private variable that can be accessed by the function Print. Pass the strings to FindLadder as const reference parameters.
• Print prints the word ladder. Private data may be needed to store the last node of the ladder (the prev field of the last node can be used to access all other ladder nodes, the first node in the ladder has a self-referential pointer).

You'll probably find it useful to write a function IsOneApart that is used to determine if two strings are one letter apart. To do this, count the letters that are equal. If this is one less than the total number of letters in the words, the words are one apart. This function does NOT need to be a member function, it has two strings as parameters (const reference) and returns true if the strings are one letter apart. You can just define this function in ladder.cpp and use it there.

You may want to write a separate function to find a word in the vector of Wnode * read and constructed using the function Ladder::LoadWords. The function can be useful in debugging and developing the program.

You may find it useful to write a function that gives back all the words that are one letter apart from a given word. This list of words could be stored in a vector or the List class (random access isn't needed). It's not at all necessary to do this, and there is no grade improvement, but it may be helpful.

Attachment:- Topics Combined Assignment Files.rar