HW #11: Word Ladders

Due 11:59pm Tuesday, April 24

The program handin21 will only submit files in the cs21/homework/11 directory.

Your programs are graded on both correctness and style. Please review the comments regarding programming style on the main page

Some of the problems will have optional components that allow you to further practice your skills in Python. Optional portions will not be graded, but may be interesting for those wanting some extra challenges.

Word ladders is a word game. The goal is transform a start word into a goal word by changing one letter at a time. After each letter change, the resulting string must also be a word.

For example, to change the start word COOL into the goal word WARM, a player could take the following steps:

C	O	O	L
W	O	O	L
W	O	O	D
W	O	R	D
W	A	R	D
W	A	R	M

In the first part of the assignment, you will allow the user to play word ladders. You will start by choosing two random words of the same length from the dictionary (in /usr/share/dict/words -- the same as from Hangman). You might want to restrict yourself to words with between 3 and 6 letters. Then you will ask the user to enter a new word which is different by exactly one letter and is also a word. If they enter a word which is not different by exactly one letter or is not a word, print an appropriate message and ask them to enter another word. When they reach the goal word, tell them that they won, how many steps it took, and what their final ladder was. For example:

The start word is: COOL
The goal word is:  WARM
Enter the next word: COOK
Enter the next word: CORK
Enter the next word: CARK
Sorry, CARK is not a word.  Try again.
Enter the next word: WORK
Enter the next word: WARM
Sorry, you changed too many letters.  Try again.
Enter the next word: WORM
Enter the next word: WORK
You won in 5 steps:
COOL, COOK, CORK, WORK, WORM, WARM

Sometimes when a user is playing along in a word ladder, they might get frustrated and not be able to think of the answer. If that happens, they might want to know what a possible solution would have been. While the user is playing, if they enter a question mark (?) at the prompt, you should display a solution to the word ladder. For example:

The start word is: JACK
The goal word is:  KING
Enter the next word: HACK
Enter the next word: HOCK
Enter the next word: POCK
Enter the next word: PICK
Enter the next word: SICK
Enter the next word: SACK
Enter the next word: SACS
Enter the next word: SAWS
Enter the next word: SEWS
Enter the next word: MEWS
Enter the next word: ?
Here is a possible solution:
JACK, HACK, HICK, KICK, KINK, KING

To solve a word ladder, we'll use a data structure called a queue. For those of you up on your British English, a queue is another word for a line, such as the one you wait in to buy a ticket for a movie. We will implement a queue using a linked list: People get into the line at the end (insertAtTail) and they get out of the line at the front (removeFromHead).

Here's how the word ladder solver is going to work. To begin with, we're going to create a queue (an empty LinkedList) where each 'data' element we're going to put in the queue will be a list representing the word ladder you've made so far.

At the start of the game, we haven't made much progress on our word ladder, so we'll insert (always at the end for a queue) a list consisting of only the start word. Assuming we're trying to solve WARM to COOL, we'll start by inserting the list ['warm'] into our queue. So, at this point, our queue will contain only one item: the list ['warm'].

Now, we'll enter a loop which we won't exit until either we reach the goal or we reach a dead end (there are no steps that we can take which without backtracking to a word we've already used). Inside that loop, we'll do the following:

1. Remove (from the front of the queue) the first list in the queue. Call this list ladder and the last item in the ladder we'll call current.
2. Generate all possible one letter changes of current which:
   1. appear in the dictionary
   2. haven't been generated before
   For example, if current is WARM, we'd generate FARM, HARM, WORM, WARD, WARE, WARN, WARP, WARS, WART, and WARY. Now, for each word we generated, make a new ladder that is equal to the the previous ladder plus the new generated word. Put each of these ladders at the end of the queue and mark each of these words as having now been generated. At this time, your queue will contain: ['warm', 'farm'], ['warm', 'harm'], ['warm', 'worm'], ['warm', 'ward'], ['warm', 'ware'], ['warm', 'warn'], ['warm', 'warp'], ['warm', 'wars'], ['warm', 'wart'], ['warm', 'wary']

Since we will repeat this over and over, after one more iteration, we'll have:
['warm', 'harm'], ['warm', 'worm'], ['warm', 'ward'], ['warm', 'ware'], ['warm', 'warn'], ['warm', 'warp'], ['warm', 'wars'], ['warm', 'wart'], ['warm', 'wary'], ['warm', 'farm', 'firm'], ['warm', 'farm', 'form'], ['warm', 'farm', 'fare'], ['warm', 'farm', 'fart']

And after another iteration we'll have:
['warm', 'worm'], ['warm', 'ward'], ['warm', 'ware'], ['warm', 'warn'], ['warm', 'warp'], ['warm', 'wars'], ['warm', 'wart'], ['warm', 'wary'], ['warm', 'farm', 'firm'], ['warm', 'farm', 'form'], ['warm', 'farm', 'fare'], ['warm', 'farm', 'fart'], ['warm', 'harm', 'hard'], ['warm', 'harm', 'hare'], ['warm', 'harm', 'hark'], ['warm', 'harm', 'harp'], ['warm', 'harm', 'hart']

Notice that all the ladders of length 2 are before the ladders of length 3 in the queue. This ensures us that when we finally find our goal word, we know that it was the shortest possible ladder.

If you find a ladder from the start to the goal, return the ladder; otherwise, return the empty list. (For example, you cannot form a word ladder from ANGEL to DEVIL.)

These questions are NOT required to receive full credit. There are several extensions you could add to this program. Here are a few we thought might be interesting.

Success rate

If you picked a random word from the dictionary and then picked another random word from the dictionary (assuming you haven't done the next extension, this other random word should be of the same length), can you find a ladder from one word to the other? Run this random experiment lots of times (you decide what 'lots' means). What percentage of random words can form ladders? What percentage of random [3, 4, 5, 6]-letter words form ladders? Do the results surprise you?

Allowing for insertion and deletion

Allow the word ladder to contain not only single letter changes at each step, but also allow for single letter deletions and single letter insertions. For example, here are two such word ladders. Insertions are shown in green and deletions are shown light gray on the previous line.

The word ladder for HOT to COLD:

H	O	T
C	O	T
C	O	D
C	O	L	D

The word ladder for LINKED to LIST:

L	I	N	K	E	D
L	I	N	E	D
L	I	N	E
L	I	N	T
L	I	S	T

Your program should allow the user to specify if they would like to play with insertions and deletions or if they would like to play the standard way. If they want to play with insertions and deletions, you should allow for choosing random words of different lengths from the dictionary.

A note of warning: allowing for insertions and deletions will make your program slower, so try some easy cases first.

Returning all possible shortest ladders

Currently, your program will return the single shortest ladder, although many other shortest ladders possibly exist. Modify your program so that instead of stopping as soon as you find the goal, you continue to find all possible ladders of the same length, stopping when the length of the ladder at the front is the queue is longer than the shortest ladder you've found.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:41 PM