CompSci 18S - Spring 2007 - Word Ladder


Classwork 1
January 10, 2007
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.

Problem

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

oil
nil
nip
nap
gap
gas

Part 1

  1. Solve the following three ladders. As you solve them, think about the way you are solving them.
    1. duke to wins (easy - 4 steps)
    2. army to navy
    3. blue to pink

  2. Discuss the solution with the others in your group. Write a brief paragraph on how you solved it.

  3. 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.
    1. 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.

    2. 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.

    3. 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.






Part 2

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.

  1. Where do the edges go in the graph? That is, which words would you create an edge between and why?

  2. 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 words. 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.