Solving Word Ladder Game - Step 1

◀ Exercise #4: Word Ladder Game▶ Solving Word Ladder Game - Step 2 Amazon Let’s apply the 1st step of the Four-Step Programming Model to solve the word ladder game!

Four Step Programming Model: Step 1
Since a valid word is only 4-letter long, there are 26*26*26*26 possible combinations. Therefore, I use a 4-dimensional bool array to store valid words. I could store them into a string vector, but searching would take a long time.

The heart of the program is ladder(), which takes a string, an int, and a bool named success.
It basically finds and stores a solution into a vector. If this solution is not found, success is still false and we should pick a different beginning word next time. If no words can form a valid word ladder, we simply output an error message. Here is my skeleton:

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
- initialize the random number generator
- use a 4-dimensional bool array to store valid words
- prompt the user to enter a valid ladder size
- find a word ladder of that size
	if found, continue
	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
- 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) {
- return true if second word is a valid word and is exactly one letter different from first
- return false otherwise
}

/* 
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. So call ladder recursively with this new word.
- 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. So call ladder recursively with this new word.
- 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. So call ladder recursively with this new word.
- 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. So call ladder recursively with this new word.
}

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

/*
precondition: w can be any string
postcondition: remove w from the word list 
*/
void remove(string w) {
- remove w from the word list vector so that we do not use it as the beginning word twice
}

/*
precondition: w must be a 4-character string
postcondition: return true if w is alphabetic; return false otherwise
*/
bool allLetter(string w) {
- return true if w consists of exactly 4 English letters
}

Let's look at the next step!◀ Exercise #4: Word Ladder Game▶ Solving Word Ladder Game - Step 2