CompSci 18S - Spring 2011 - Word Ladder
January 12, 2011
Group Writeup (10 pts)
For group work, please turn in one sheet of paper with all the names
of those who participated in your group.
Word ladders were invented by Lewis Carroll in 1878, the author of
Alice in Wonderland.
A word ladder is when a word is turned into another word one letter
at a time, each change in letter must be a word.
For example, one can change oil into gas
- Solve the following three ladders. As you solve them, think about the
way you are solving them.
- duke to wins (easy - 4 steps)
- army to navy
- blue to pink
- Discuss the solution with the others in your group. Write a brief
paragraph on how you solved it.
- Now let's think about how you would write a program to
solve word ladders for 5-letter words.
Suppose you are given a file of all 5-letter words.
- Think about a word as a string of characters, or as an array of
characters. The word "science" has the letter (or character) "s" in
position 0 (arrays start in position 0 in Alice and Java), the character
"c" in positions 1 and 5, etc.
Sketch out a function that takes two 5-letter words and returns true
if the words are "one-letter-apart", meaning that only one letter is
different between the two words and the different letters are in the
same position in the word. The function returns false otherwise.
- Write an algorithm to solve the word ladder problem for
5-letter words. That is,
given an array of 5-letter words (assume the file of words
has been read into an array) called dictionary, and
two 5-letter words, print out a ladder if there is one.
- If the dictionary has N words in it, approximately how long does
it take to find a ladder that has M words in it?
For example, the ladder for oil to gas above has 6 words in it.
Consider preprocessing the dictionary of 5-letter words, storing it in a graph
instead of an array. Recall the social network problem we worked on in
which each node in the graph was the name of a person, and there
was an edge (or link) between two people if they were friends.
In this case, each 5-letter word from the dictionary
would be a node in the graph.
- Where do the edges go in the graph? That is, which words would you
create an edge between and why?
- Given the graph of 5-letter words you created and two 5-letter words,
write an algorithm for finding and printing the word ladder of the two
Assume that given a word, you can easily start with the node for that
word in the graph. Then think about "walking" through the graph.