Prog 3: Work Play

Write a program to change one word into another, such as converting work into play. At each step only a single letter can be changed at a time, and each word must be a word found in the dictionary. This is inspired by Robert Frost's poem "Two Tramps in Mud Time" where the last stanza is:

But yield who will to their separation,

My object in living is to unite

My avocation and my vocation

As my two eyes make one in sight.

Only where love and need are one,

And the work is play for mortal stakes,

Is the deed ever really done

For heaven and the future’s sakes.

Remember that for this program you may work with a partner, though you must register yourselves at least a week before the deadline. See Pair Programming on the syllabus for more information.

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):

Running your program again could look like the following:

Program #3: Work Play Author: Dale Reed Lab: Tues 8am System: Codio Total number of words in dictionary file: 235886 Word lengths where there are more than 1400 words: Length How Many ------ -------- 3 1420 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 17 1813 Currently we have 1420 words of length 3 in the dictionary. Changing from 'dog' to 'cat' Choose from the following options: 1. Change the word length 2. Display some dictionary words 3. Get start and end words 4. Play the word change game 5. Find the end word with debug 6. Find the end word 7. Display an answer sequence 8. Exit the program Your choice -> 5 0. dog: 1:bog 2:cog 3:fog 4:gog 5:hog 6:jog 7:log 8:mog 9:nog 10:rog 11:sog 12:tog 13:vog 14:wog 15:dag 16:deg 17:dig 18:dug 19:dob 20 :doc 21:dod 22:doe 23:dol 24:dom 25:don 26:dop 27:dor 28:dos 29:dot 30:dow 1. bog: 31:bag 32:beg 33:big 34:bug 35:boa 36:bob 37:bod 38:bom 39:bon 40:boo 41:bop 42:bor 43:bos 44:bot 45:bow 46:boy 2. cog: 47:cag 48:cig 49:cob 50:cod 51:coe 52:col 53:con 54:coo 55:cop 56:cor 57:cos 58:cot 59:cow 60:cox 61:coy 62:coz 3. fog: 63:fag 64:fig 65:fob 66:fod 67:foe 68:fon 69:foo 70:fop 71:for 72:fot 73:fou 74:fow 75:fox 76:foy 4. gog: 77:gag 78:gig 79:goa 80:gob 81:god 82:goi 83:gol 84:gon 85:goo 86:gor 87:gos 88:got 89:goy 5. hog: 90:hag 91:hug 92:hob 93:hod 94:hoe 95:hoi 96:hon 97:hop 98:hot 99:how 100:hox 101:hoy 6. jog: 102:jag 103:jig 104:jug 105:job 106:joe 107:jon 108:jos 109:jot 110:jow 111:joy 7. log: 112:lag 113:leg 114:lug 115:loa 116:lob 117:lod 118:lof 119:loo 120:lop 121:lot 122:lou 123:low 124:lox 125:loy 8. mog: 126:mag 127:meg 128:mig 129:mug 130:mob 131:mod 132:moe 133:moi 134:mon 135:moo 136:mop 137:mor 138:mot 139:mou 140:mow 141:mo y 9. nog: 142:nag 143:nig 144:noa 145:nob 146:nod 147:non 148:nor 149:not 150:nou 151:now 152:noy 10. rog: 153:rag 154:reg 155:rig 156:rug 157:rob 158:roc 159:rod 160:roe 161:roi 162:rok 163:ron 164:rot 165:row 166:rox 167:roy 11. sog: 168:sag 169:seg 170:sig 171:sob 172:soc 173:sod 174:soe 175:soh 176:sok 177:sol 178:son 179:sop 180:sot 181:sou 182:sov 183:s ow 184:soy 12. tog: 185:tag 186:teg 187:tig 188:tug 189:tyg 190:toa 191:tod 192:toe 193:toi 194:tol 195:tom 196:ton 197:too 198:top 199:tor 200:t ot 201:tou 202:tow 203:tox 204:toy 13. vog: 205:vag 206:vug 207:vod 208:voe 209:vol 210:vow 14. wog: 211:wag 212:wig 213:wob 214:wod 215:woe 216:won 217:woo 218:wop 219:wot 220:wow 221:woy 15. dag: 222:zag 223:dab 224:dad 225:dae 226:dah 227:dak 228:dal 229:dam 230:dan 231:dao 232:dap 233:dar 234:das 235:daw 236:day 16. deg: 237:keg 238:peg 239:deb 240:dee 241:del 242:den 243:dev 244:dew 245:dey 17. dig: 246:pig 247:zig 248:dib 249:did 250:die 251:dim 252:din 253:dip 254:dis 255:dit 256:div 18. dug: 257:pug 258:dub 259:dud 260:due 261:dum 262:dun 263:duo 264:dup 265:dux 19. dob: 266:kob 267:pob 20. doc: 21. dod: 268:pod 22. doe: 269:poe 270:yoe 271:dye 23. dol: 272:kol 273:pol 24. dom: 274:pom 275:yom 25. don: 276:eon 277:ion 278:kon 279:pon 280:yon 26. dop: 281:kop 282:pop 27. dor: 283:kor 284:yor 28. dos: 285:kos 29. dot: 286:pot 287:yot 30. dow: 288:pow 289:yow 31. bag: 290:baa 291:bab 292:bac 293:bad 294:bae 295:bah 296:bal 297:bam 298:ban 299:bap 300:bar 301:bas 302:bat 303:baw 304:bay 32. beg: 305:bea 306:bed 307:bee 308:bel 309:ben 310:ber 311:bes 312:bet 313:bey 33. big: 314:bib 315:bid 316:bim 317:bin 318:bis 319:bit 320:biz 34. bug: 321:bub 322:bud 323:bum 324:bun 325:bur 326:bus 327:but 328:buy 35. boa: 329:koa 330:poa 331:zoa 332:bra 36. bob: 37. bod: 38. bom: 39. bon: 40. boo: 333:zoo 334:blo 41. bop: 42. bor: 43. bos: 44. bot: 45. bow: 46. boy: 335:poy 336:yoy 47. cag: 337:cab 338:cad 339:cal 340:cam 341:can 342:cap 343:car 344:cat Winning sequence was found! Currently we have 1420 words of length 3 in the dictionary. Changing from 'dog' to 'cat' Choose from the following options: 1. Change the word length 2. Display some dictionary words 3. Get start and end words 4. Play the word change game 5. Find the end word with debug 6. Find the end word 7. Display an answer sequence 8. Exit the program Your choice -> 7 Winning sequence in reverse order is: 344. cat 47. cag 2. cog 0. dog Currently we have 1420 words of length 3 in the dictionary. Changing from 'dog' to 'cat' Choose from the following options: 1. Change the word length 2. Display some dictionary words 3. Get start and end words 4. Play the word change game 5. Find the end word with debug 6. Find the end word 7. Display an answer sequence 8. Exit the program Your choice -> 8 Exiting the program

Note that the defaults are to work with words of size 3, with the default starting word being "dog" and the default end word being "cat". Running the program again might look like the following:

Finding the ending word going from "work" to "play" on Codio took about 25 seconds. Note that if it takes too long (>30 seconds?), Codio may kill your process, mistakenly thinking that it is a "runaway" program in an infinite loop.

Hints about Vectors

You should use vectors to store any word lists your program uses. Some examples of useful vector operations are:

vector< string> dictionary; // Declare a vector called dictionary that stores strings

string aWord = "Hey"; // Store "Hey" into a string variable called aWord

string otherWord = "there"; // Store "there" into a string variable called otherWord

otherWord.size()

dictionary.push_back( aWord); // Append string aWord to the end of the dictionary vector

dictionary.size() // Gives the total number of entries in the dictionary, indexed 0 .. n-1

cout << dictionary[ 2]; // Display the third word in vector dictionary, stored at index 2

if( aWord == otherWord) // Evaluates to true if the two strings are the same

aWord.compare( otherWord) // Evaluates to a negative number if aWord < otherWord, 0 if equal,

// and a positive number if aWord > otherWord

dictionary.clear(); // Delete all the contents of vector dictionary

Suggested Plan of Attack

This program is more complex than previous programs. Following is a suggested sequence of steps. You will need to run my solution inside Codio to become familiar with what you are trying to do before writing the code for each step, and to see specifically what the error messages are in each case that is listed.

1. (2 points) Read in words from the dictionary file dictionary.txt
  1. Read words from the dictionary file and display them on the screen, and then close the dictionary file.
  2. Put the dictionary reading code into a function, called from main()
  3. As you read each word, you should convert all of its letters to lower case, since later comparisons might not work otherwise and mixed case also is not the same as ASCII order. To convert a letter to lower case use the tolower( c) function found in the cctype library, where c is of type char.
  4. Create a vector in main(), pass the vector, and read the words from dictionary.txt into the vector. Don't forget to pass your vector as a reference parameter!
  5. Create an array in main to count how many words there are of each size in the dictionary. Pass this array to the code used to read from the dictionary. As each word is read, check the size of each word using the .length() string member function, and only store (using the vector .push_back() member function) the strings that are the desired length.
  6. Back in main display the table of how many there are of each length word, displaying only rows with counts >= 1400
  7. If you later change the length of words that you are using, you should call the same code again, this time passing the new length. Don't forget to clear the dictionary vector (using the vector .clear()member function) before reading in words of a different length!
2. (0 points) Set up your menu display and menu handling code, though the details for handling each option will be left for later.
3. (3 points) Implement menu option 8. Exit the program
4. (5 points) Implement menu option 2. Display some dictionary words. Use this to verify that the previous code reading in dictionary words worked correctly.
5. (5 points) Implement menu option 3. Get start and end words. Note that your program should have default values of "dog" and "cat" respectively initialized into those string variables.

- 1. If the user input word is "exit" then exit the program
  2. If the user input word is "r" then select a random word from the dictionary, which means you must pass the dictionary vector to this code. You should have srand( 1) near the top of main(), so your results are predictable and match what is expected. Assuming your vector of words is called dictionary, and you have already calculated the numberOfWords in the dictionary, then to set string startWord to be a random dictionary word you would use something like:
  3. startWord = dictionary[ rand()%numberOfWords]);
  4. If the user input word is the wrong length, give an error message and prompt for them to retry
  5. If the user input word is not in the dictionary, give an error message and prompt for them to retry. To look up a word in the dictionary I suggest you use the binarySearch(...) function given to you in the sample.cpp code as part of your Codio project.

(10 points) Implement menu option 4. Play the word change game. This should be in a function of its own.
1. At the beginning of the function you should verify that the start and end words are set and are not blank. If not, give an error message and return to the main menu.
2. Prompt for the next move. (See my solution to know specifically what this looks like and what the error messages should be.)
3. Check to see if "exit" was entered. If so, return from the function.
4. Validate the length of the user-suggested next word. If incorrect, give an error and have the user retry. This implies your code is in a loop, so you can use the continue statement.
5. Verify that this suggested next word is in the dictionary. (Here again you could use binary search, mentioned in a previous step.) If not in the dictionary, give an error message and have the user retry.
6. Verify that the previous word and the next word vary by exactly a single character. If it doesn't, give an error message and have the user retry.
7. Check to see if the next word is the end word, that is the goal. If so give a congratulatory message (see my solution) and return from the function.
(10 points)Implement menu option 5. Find the end word with debug.
Running this code looks like what is shown in the sample output at the top of this page. Look at that output and notice that the debugging information shows (on the left) the index and the word being expanded. Then to the right of each of these words are all the new words that are created by expanding the current word. To the left of each of these new words is the index position where each of them is stored in the successors vector.

1. Implementing this feature is the challenging part of the program. You will essentially create a tree of all words reachable from 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 (and is a CS 251 Data Structures topic), so instead we will use a vector of strings. Start by putting the starting word in this new successors vector. Find all words that are at most 1 letter away from this starting word. Append each of these words successively to the successors vector, Then repeat, moving to the next successors vector entry 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.
2. (10 points) Implement menu option 6. Find the end word
3. Now modify your code from the previous step, adding an additional parameter to that function. Use this parameter to selectively display the debugging information. This way you can share the same code for these two menu options.
4. (10 points) Implement menu option 7. Display an answer sequence.
5. 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 vector index of its parent. I suggest you do this in a separate parallel vector. As each newly generated word is appended to the successors vector, also append the index of its parent to this other parallel vector.
6. To display the answer sequence, start with the last word stored in the successors vector. This should be at position successorsVector.size() -1, since the vector index values go from 0 .. n-1. Display the index value for this word and the word itself. Then go to its parent and do the same, repeating this process until you get to the beginning of the successors vector, where the start word is storede.
7. The solution sequence is displayed in reverse order.

Food for Thought (but not necessary...)

What determines the length of the search for a solution? Is there a way to speed this up?
How about doing a "bi-directional" search to minimize the total number of words expanded? What additional overhead is there using this approach?
Consider solutions for the following begin-end words: beer:wine, work:play, study:sleep, nap:run.
Are the sizes of the search spaces smaller going in one direction compared to the other for these pairs of words? Why or why not?