Solving Word Ladder Game - Step 4

◀ Solving Word Ladder Game - Step 3▶ Exercise #5: A Random Maze Generator
Amazon Let’s apply the final step of the Four-Step Programming Model to solve the word ladder game!

Four Step Programming Model: Step 4
Having considered step 3, I code my program efficiently because I know exactly what to do and what to be cautious about. As I code, I realize that I need slightly more variables. Here is the final version of my program:
/*
Michael Wen 
6/19/2003
This program plays a word ladder game with the user.
*/ #include <iostream> #include <fstream> #include <cctype> #include <ctime> #include <vector> #include <string> using namespace std; bool bitmap[26][26][26][26]; vector<string> bitmapv, words; bool isValid(string, string); void ladder(string, int, bool&); bool isRepeated(string); void remove(string); bool allLetter(string); int main(int argc, char **argv) {
/* exit if no file is provided in command line */ if(argc!=2) { cout << "usage: exe <wordlist>\n"; cout << "<wordlist>: a list of words to be used in the game\n"; exit(1); } int i, i2, i3, i4, transition, n; ifstream fin; string word, currWord; bool success; /* initialize the random number generator */ srand(time(0)); for(i=0; i<26; ++i) for(i2=0; i2<26; ++i2) for(i3=0; i3<26; ++i3)
for(i4=0; i4<26; ++i4) bitmap[i][i2][i3][i4] = false; /* open the given file and use a 4-dimensional bool array to store valid words */ fin.open(argv[1]); if(!fin.is_open()) { cout << argv[1] << " cannot be opened, forced exit\n"; exit(2); } while(fin>>word) { if(word.length()!=4 || !allLetter(word)) { cout << "incorrectly formatted file, forced exit\n"; exit(3); } bitmap[word[0]-'a'][word[1]-'a'][word[2]-'a'][word[3]-'a'] = true;
bitmapv.push_back(word); } fin.close(); /* prompt the user to enter a valid ladder size */ cout << "Enter a ladder size (1 to 20 inclusively): "; while(!(cin>>transition) || transition<1 || transition>20) { if(!cin) { cin.clear(); while(cin.get()!='\n') ; } cout << "Enter a ladder size (1 to 20 inclusively): "; } success = false; /* use a while loop to find a word ladder of that size given the beginning and destination words */
while(!success) { words.clear(); if(bitmapv.size()==0) { cout << "current word list cannot support this ladder, forced exit\n"; exit(4); } word = bitmapv[rand()%bitmapv.size()]; remove(word); ladder(word, transition, success); } /* start the game by having the user input the intermediate words in the word ladder, given the beginning and destination words */ cout << "At any time, enter q to exit the game, r to restart the game,\n";
cout << "and s to show solution.\n"; cout << "\nEnter words from " << words.front() << " to " << words.back() << ":\n"; cout << words.front() << endl; n = 0; currWord = words.front(); while(n<transition) { cin >> word; if(word=="q") { break; } if(word=="r") { cout << "\nrestarting..."; n = 0; currWord = words.front(); cout << "done\n"; cout << "Enter words from " << words.front() << " to "; cout << words.back() << ":\n"; cout << words.front() << endl; continue; } if(word=="s") { cout << "\nhere is sample solution:\n"; for(i=0; i<words.size(); i++) cout << words[i] << endl; break; } /* make sure at each stage the user enters a valid word */ if(word.length()!=4 || !allLetter(word) || !isValid(currWord, word)) { cout << word << " is not valid. Enter a new word: "; continue; } currWord = word; ++n; } /* output results depending on how the user did */ if(currWord==words.back()) cout << "\nCongradulations!\n"; else cout << "\nI am sorry. Please try again next time.\n"; return 0; } /* precondition: first and second must consist of only letters and must be of length 4 postcondition: return true if transition from first to second is valid and second is a word in the word list */ bool isValid(string first, string second) { int i, counter; counter = 0; if(!bitmap[second[0]-'a'][second[1]-'a'][second[2]-'a'][second[3]-'a']) return false; for(i=0; i<4; i++) { if(first[i]!=second[i]) ++counter; } return (counter==1); } /* precondition: success should be false in the first function call t should be >= 1 w must be a 4-letter string postcondition: success is set true if the word ladder has been found */ void ladder(string w, int t, bool & success) { /* put w into the solution vector */ words.push_back(w); /* if t is 0, set success to true and return */ if(t==0) { success = true; return; } string newWord = w; char c; /* iterate from ‘a’ through ‘z’ in the first letter of w */ for(c='a'; c<='z' && !success; ++c) { newWord[0] = c; if(bitmap[newWord[0]-'a'][newWord[1]-'a'][newWord[2]- 'a'][newWord[3]-'a'] && !isRepeated(newWord)) { ladder(newWord, t-1, success); if(!success) words.pop_back(); } } newWord = w; /* iterate from ‘a’ through ‘z’ in the second letter of w */ for(c='a'; c<='z' && !success; ++c) { newWord[1] = c; if(bitmap[newWord[0]-'a'][newWord[1]-'a'][newWord[2]- 'a'][newWord[3]-'a'] && !isRepeated(newWord)) { ladder(newWord, t-1, success); if(!success) words.pop_back(); } } newWord = w; /* iterate from ‘a’ through ‘z’ in the third letter of w */ for(c='a'; c<='z' && !success; ++c) { newWord[2] = c; if(bitmap[newWord[0]-'a'][newWord[1]-'a'][newWord[2]- 'a'][newWord[3]-'a'] && !isRepeated(newWord)) { ladder(newWord, t-1, success); if(!success) words.pop_back(); } } newWord = w; /* iterate from ‘a’ through ‘z’ in the fourth letter of w */ for(c='a'; c<='z' && !success; ++c) { newWord[3] = c; if(bitmap[newWord[0]-'a'][newWord[1]-'a'][newWord[2]- 'a'][newWord[3]-'a'] && !isRepeated(newWord)) { ladder(newWord, t-1, success); if(!success) words.pop_back(); } } } /* precondition: w can be any string postcondition: return true if w is in words; return false otherwise */ bool isRepeated(string w) { int i; for(i=0; i<words.size(); ++i) if(words[i]==w) return true; return false; } /* precondition: w can be any string postcondition: remove w from bitmapv if w exists in bitmapv */ void remove(string w) { vector<string>::iterator vi; for(vi=bitmapv.begin(); vi!=bitmapv.end(); ++vi) if(*vi==w) { bitmapv.erase(vi); break; } } /* precondition: w must be a 4-character string postcondition: return true if w is alphabetic; return false otherwise */ bool allLetter(string w) { return (isalpha(w[0])&&isalpha(w[1])&&isalpha(w[2])&&isalpha(w[3])); }
This is a rather big program. Give yourself a big hand if you wrote it completely on your own. If you love challenges, add extra functionality such as give the user a hint along the way and play a word game of any word length!

Next let’s move on to solving an interesting task – generate a random maze!
◀ Solving Word Ladder Game - Step 3▶ Exercise #5: A Random Maze Generator

fShare
Questions? Let me know!