Program 4: Morph

Write a program to change one word into another.  At each step only a single letter can be changed at a time, and each word must be a word found in the dictionary.

Use dictionary.txt (taken on a Mac from /usr/share/dict/words) of 235,886 words.  Running the program should look like the following, where user input is shown in bold (though your program when run will not display that in bold):

Program #4: Morph Words    

Author: Dale Reed    

Lab: Tues 8am     

System:  Mac OS X, Qt Creator IDE 

Total number of words: 235886 

Word lengths where there are more than 2000 words:

Length  How Many

------  --------

    4      5272

    5     10230

    6     17706

    7     23869

    8     29989

    9     32403

   10     30878

   11     26013

   12     20462

   13     14939

   14      9765

   15      5925

   16      3377

What length words do you want to use? 4

Number of words read was 5272

Enter starting and ending words, or 'r' for either for a random word: zong zichs

'zong' is not in the dictionary. Please retry.

Enter starting and ending words, or 'r' for either for a random word: song zichs

'zichs' is not of length 4. Please retry.

Enter starting and ending words, or 'r' for either for a random word: song r

Morphing from song to whig.

On each move enter a word of the same length that is at   

most 1 character different and is also in the dictionary, 

or type in 'exit' to exit the interactive portion of the program.

1. Previous word is 'song'.  Next word: soig

Your suggestion of soig is not in the dictionary.  Please retry.

1. Previous word is 'song'.  Next word: sing

2. Previous word is 'sing'.  Next word: wing

3. Previous word is 'wing'.  Next word: wink

4. Previous word is 'wink'.  Next word: wook

New word must be exactly 1 character different.  Please retry.

4. Previous word is 'wink'.  Next word: wine

5. Previous word is 'wine'.  Next word: exit

You chose 'exit' to exit the interactive part of the program.

Now Computer will display a solution path, if there is one.

Solution is: 

   0. song

  16. tong

 122. toug

 671. thug

2270. thig

3887. whig

See here for the same program that includes debugging / trace information.  I suggest you develop your program one stage at a time, breaking down section using functions.  Here are some ideas on data declarations and parameter passing that may help you if you choose to follow a similar approach to the one I chose.

Hints

Dictionary

You will read the dictionary file twice.  The first time you will accumulate counts of how many words of each length there are, storing this in an array.  You know that the longest possible word is around 30 characters, so make your counting array of integers that size.  As you read each word, check its size and add one to the corresponding array location in your word length counting array.

You will then close the file.  Then prompt the user for what size words she wants to deal with, dynamically creating an array to handle these, since in the previous step you already figured out how many there are.  You will need to dynamically allocate space for this array.

This array should be declared in main as:  char **theWords   and then passed as a parameter to functions that need it.  When initially creating it you will pass it simply using its name (theWords) and when declaring it on the (for example) readInWordsFromFile(..) function parameter list, you will need to declare it as    char ** &theWords  Because it is a char ** that will change (and point to a newly allocated array), and you want that change reflected back to the calling part of the program.  Note that dynamic memory allocation for this must occur in two stages: 

1. Allocate an array of char *

2. Imagine that these are a long column (an array) of char *, though initially each of them does not point to anything.  To declare this use something like:

3.            theWords = (char **) malloc( sizeof( char *) * numberOfWords);

4. Next we have to go down this array of char *, allocating space for each word on each row.  This should be done in a loop and will look something like

5.       // For each array entry (i.e. each word), allocate space for that word

6.      for( int i=0; i<numberOfWords; i++) { 

7.         theWords[ i] = (char *) malloc( sizeof(char) * (wordLength+1));  // add 1 to length for the NULL

8.      }

9. Now we can re-read the file.  As each word is read, make sure to convert each word into lower case. You needn't bother checking for duplicates.  As you read each word use strcpy to put it into its corresponding row in the array.

Random Number Generator

• 1. In this program you will allow the user to explicitly type in the starting and ending word, so when this is not done, you can have your program choose words at random.  Random number generators aren't really random, but when developing your program it can be helpful to always have it make the same choices you run the program.  To make this happen you need to seed the random number generator with a fixed value.  You should only seed the random number generator once in your program, typically near the beginning of main().  That statement will look something like:   srand( 1);

  2. To get your program to give different results each time, use time( 0) instead of 1 when seeding your random number generator, so it would look like:   srand( time( 1));

  3. When setting, for example, the startWord, you should do something like:

  4.      strcpy( startWord, theWords[ rand()%numberOfWords]);

Debugging

I highly recommend that you develop your program one step at a time, printing out debugging information as you go.  For instance see the version of the output shown near the top of this page, that includes extensive debugging information.

Prompting for start and end Words

This code should be in a function.  startWord and endWord should be declared in main as arrays of char of some fixed size (probably 81), and then passed to functions where they are used.  You should use some kind of loop to read in those values.  Note that the user can enter two words, or enter two single character 'r' which represent random selection of each word.  Read in both words and then handle the cases.  If a word is 'r' then choose a random word, as illustrated above.  Otherwise validate each word to make sure it is in the dictionary and is the proper length.  Since this code is in a loop, if there is some problem, simply use the continue statement to go back up to the top of the loop to retry.  Then use the break statement to break out of the loop once both words are verified.

Handling Interactive User Input

You will need a loop to handle user input.  It should keep going until the end word is found, or the user types in 'exit' to quit the interactive part of the program.  For each user input word you should:

• 1. See if 'exit' was entered.  If it was break out of the user input and processing loop and return back to main()

  2. Ensure that the length of the user input was correct.  This means that the proscribed length must also be passed as a parameter to this function.

  3. Ensure the new word is at most one character different from the previous word.  You will need to have separate C strings (array of char) to store the current user word and the previous one.  Write a function to count how many characters are different between the two words, and use that result to give an error message and continue back up to top of loop if necessary.

  4. Ensure word is in the dictionary.  You should write a function for this, as you will need it elsewhere.  For the purposes of this program using a sequential (linear) search is probably good enough, where you have a loop that steps through each dictionary word and compares it to the user input.

1. If all the tests are passed, then you have a new current word, that you can copy into the previous word variable for use the next time through the loop.

Computer Generates Solution Path

This is the challenging part of the program.  You will essentially create a tree of all words reachable form the starting word.  The tree keeps growing as you expand each word already in the tree, keeping track of its "children."  Actually using a tree structure for this is beyond what we can comfortably do so far, so instead we will use an array.  Start by putting the starting word on this array.  Find all words that are at most 1 letter away from this starting word.  Store each of these words successively in this array, adding them to the end.  Then repeat, moving to the next line to expand that word, and so on.

This process will end once there are no more words to be expanded, or when the ending word is found.  Once the ending word is found we need a way to trace its ancestry back to the starting word.  This means that for each word we need to also store the index number of its parent, so rather than an array of words, we will instead be dealing with an array of struct, where each struct member has a word as well as the index of its parent.  The resulting array will at most be the size of the original array of words.  Similar to when char ** theWords was declared, we have to declare this in steps.  

1. Declare the array of Nodes.  This will be something like:

   1.         // First allocate an array of Node *

   2.     Node * wordTree = (Node *) malloc( sizeof( Node) * numberOfWords);

2. Next go through the array and allocate space for each word within each array struct node:

• 1.      // Go through array of Nodes and allocate space for each word

  2.     for( int i=0; i<numberOfWords; i++) {

  3.           wordTree[ i].word = (char *) malloc( sizeof( char) * (wordLength+1));

  4.           wordTree[ i].parentIndex = 0;

  5.     }

3. As each word is expanded, add each new word to this array.  I highly recommend you print these newly generated words out as you go, perhaps along with their index numbers, to ensure your program is working correctly.

4. Once the end word is found, use the parent index values to follow ints ancestry back, printing it out as you go, which will give you the solution path in revers order.  The tricky part is then figuring out how to reverse this solution path, so it gives it to you in order. (Hint: Think of how the solution to the Maze problem is done in class, once we get to that.)

Points Breakdown:

1. Choosing start and end words:    (10 pts, 2 pts each part) 

   1. 1. Correctly displays counts of word lengths for word lengths > 2000

      2. Allows allocating array space for different sizes of word lengths

      3. Verify start and end words are in dictionary

      4. Verify length of start and end words

      5. Allows selecting random words when 'r' is entered for either or both words.  Uses random number generator for randomly selected words.

2.  Handling user "moves":   (15 pts, 3 pts each part) 

• 1. Verify each new user word is in the dictionary

  2. Verify each new user word is the proper length

  3. Verify each new user word is exactly 1 character different from the previous word

  4. Notify user when ending word is found

  5. Handle the user entering "exit" to exit the interactive mode of the program

  6. Solution Path   (30 pts, 15 pts each part) 

  7. Computer finds the solution path and shows it if there is one, or indicates that there is no solution if there isn't one.  Solution path is in reverse order.

  8. Same as above, except now the solution path (for any length solution!) is in order.

Turn in Instructions:

Remember that the name of your project should be your netid.  Once you are done with your program, rename main.cpp to be netid.cpp, where netid is your netid.  Zip up only your netid.cpp file and turn it in to Blackboard into the Program 4 assignment.