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

fShare
Questions? Let me know!