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!