Word Ladder Nifty Assignment

The Word Ladder program is similar to a "6 degrees of separation" or Oracle of (Kevin) Bacon game, but using words rather than people or actors. Simply, from a given starting word, find the shortest "ladder" of single letter changes which leads to some final word, where each intermediate state is also a word.

For example:

clash, flash, flask, flack, flock, clock, crock, crook, croon, crown, clown.
This program is nifty on several levels. It can be used early in a CS2 course when queues are discussed, and brought up again later when/if graph algorithms are covered. A naive algorithm of checking every word as the potential next word in a chain runs quickly, but precomputing all edges in the graph of words makes finding ladders instantaneous at the expense of a significant up-front cost to compute the graph.

We have used this assignment early in a CS2 course after covering linked structures (to connect a word with its predecessor), stacks, and queues. We have also used it at the end of a CS2 course as an example of breadth-first search in a graph. We have had students animate the process of putting words on the queue to understand that a shortest path is guaranteed to be found. For extra credit we have given the problem of finding the longest word ladder which is, in general, an intractable problem, though solvable in the case of real five-letter words.

We are in the process of incorporating the Oracle of Bacon in addition to words into the assignment. Certainly the next step is to connect nifty CS educators.

Owen L. Astrachan
Last modified: Wed Jul 25 09:23:32 EDT 2001