Exercise #4: Word Ladder Game

◀ Solve The Eight Queens Puzzle - Step 4▶ Solving Word Ladder Game - Step 1 Amazon Many of you probably have heard of this game. You give the size of the “ladder” and the computer generates two words, the beginning word and the destination word, for you. You must come up with another word which is exactly one letter different from the beginning word. Then you come up with another word which is exactly one letter different from the one you just came up with.


For example, if the ladder size is 3 and the beginning and destination words are “dank” and “bale”, respectively, then you can come up with the following sequence:

dank – bank – balk – bale

Then you win the game. There are many subtle points in the implementation, however.

For example, if the ladder size is 3 and the beginning and destination words are “dank” and “bank”, respectively, then the following sequence

dank – bank – dank – bank

is a valid word ladder. If most word ladders the computer generates look like this one, the player would feel pretty upset. Therefore, let’s make it a rule that no words in a ladder may be repeated. Also, to make life easier, let’s assume that all words are 4-letter words.

The following are the program’s specifications:

• Start by reading a file, given in command line, that contains a list of valid 4-letter words. If not all words are 4-letter words, either output an error message and terminate the program or ignore invalid words and continue.
• Ask the user for the size of the word ladder, which must be between 1 and 20, inclusively.
• Search through all valid words and find such a word ladder.
• If a word ladder cannot be found (probably the word list is too small or the ladder size too big), output an error message and terminate the program.
• Prompt the user to enter a word ladder, given the beginning and destination words.
• If the user enters an invalid word, prompt him or her to enter again.
• You may add extra functionality such as the ability to quit at any time, the ability to restart at any time, and the ability to show a sample solution.
• Under no circumstances should your program crash. Therefore, you must do proper error-checking to ensure that even the most wacky psychotic can’t break it.

You can also make it menu-driven and allow the user to play the game many times, but they are trivial features.

What you should get out of writing this program is how to do exhaustive error-checking.
Here is one sample run:

./ladder words.txt
Enter a ladder size (1 to 20 inclusively): a
Enter a ladder size (1 to 20 inclusively): yes
Enter a ladder size (1 to 20 inclusively): 123
Enter a ladder size (1 to 20 inclusively): -123
Enter a ladder size (1 to 20 inclusively): 4
At any time, enter q to exit the game, r to restart the game, 
and s to show solution.

Enter words from sect to heat:
sect
sept
seat
teat
heat

Congratulations!

Here’s another sample run:

./ladder words.txt
Enter a ladder size (1 to 20 inclusively): 4
At any time, enter q to exit the game, r to restart the game, 
and s to show solution.

Enter words from rove to love:
rove
love
lote
lote is not valid. Enter a new word: lave
lave is not valid. Enter a new word: 1234
1234 is not valid. Enter a new word: dadadalla
dadadalla is not valid. Enter a new word: dove
move
mole

I am sorry. Please try again next time.

You shouldn’t expect the player to enter the identical ladder as the one your program finds. For example, from bake to sale with ladder size being 2, you can do

bake – sake – sale

or

bake – bale – sale

Both are fine, provided all words are in the input file. Now you should be able to write the program.

This program is probably bigger and harder than any of the earlier ones you wrote, so get started immediately. There are many procrastinators out there, and I’m sure you are not one of them!

As usual, I provide my own skeletons and code. You shouldn’t refer to them unless you are stuck and desperate. Let's apply the Four Step Programming Model described in Chapter 11.8!◀ Solve The Eight Queens Puzzle - Step 4▶ Solving Word Ladder Game - Step 1