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