Solving Word Ladder Game - Step 2

◀ Solving Word Ladder Game - Step 1▶ Solving Word Ladder Game - Step 3
Amazon Let’s apply the 2nd step of the Four-Step Programming Model to solve the word ladder game!

Four Step Programming Model: Step 2
As for variables, we need a 4-dimensional bool array to store valid 4-letter words, 4 int to initialize the array, a string vector to store a solution, an int store the ladder size, an ifstream object to open the file containing valid words, a string to store the user’s inputted word, and a bool to store whether a ladder given the beginning and destination words is found.

After carefully examining the skeleton, I add more detail to it.
Also, inside ladder(), after I call ladder() recursively, what should I do? There are two possibilities: the ladder is found and success is set true; and the ladder is not found and success remains false.

In the first case, we don’t need to do anything. In the second case, however, we need to pop out the word at the back of the solution vector because that word leads to failure in locating a valid word ladder.

The following updated skeleton will reflect a small modification in ladder():
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

bool bitmap[26][26][26][26];
vector<string> words;		/* the solution vector */
int i, i2, i3, i4, transition;
ifstream fin;
string word;
bool success;

- initialize the random number generator
- open the given file and use a 4-dimensional bool array to store valid words
- prompt the user to enter a valid ladder size
- use a while loop to find a word ladder of that size given the beginning and destination words
	if found, break the while loop and start the game
	if not found, issue an error message and exit
- start the game by having the user input the intermediate words in the word ladder, given the beginning and destination words
- make sure at each stage the user enters a valid word; if not, have him or her enter again
- output results depending on how the user did
}

/*
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) {
- same
}

/* 
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
- if t is 0, set success to true and return
- iterate from ‘a’ through ‘z’ in the first letter of w
if the new word is a valid word and is not in the solution vector, that means this is a valid word in the ladder; call ladder recursively with this new word
if success is false, pop out the word at the back of the solution vector
- iterate from ‘a’ through ‘z’ in the second letter of w
if the new word is a valid word and is not in the solution vector, that means this is a valid word in the ladder; call ladder recursively with this new word
if success is false, pop out the word at the back of the solution vector
- iterate from ‘a’ through ‘z’ in the third letter of w
if the new word is a valid word and is not in the solution vector, that means this is a valid word in the ladder; call ladder recursively with this new word
if success is false, pop out the word at the back of the solution vector
- iterate from ‘a’ through ‘z’ in the fourth letter of w
if the new word is a valid word and is not in the solution vector, that means this is a valid word in the ladder; call ladder recursively with this new word
if success is false, pop out the word at the back of the solution vector
}

/*
precondition: w can be any string
postcondition: return true if w is in the word list; return false otherwise
*/
bool isRepeated(string w) {
- same
}

/*
precondition: w can be any string
postcondition: remove w from the word list 
*/
void remove(string w) {
- same
}

/*
precondition: w must be a 4-character string
postcondition: return true if w is alphabetic; return false otherwise
*/
bool allLetter(string w) {
- same
}
Let's look at the next step!
◀ Solving Word Ladder Game - Step 1▶ Solving Word Ladder Game - Step 3

fShare
Questions? Let me know!