CSCI 203 Project #5

Doublets (i.e., Using Graphs)

Purpose: This project will give you experience with graph representations and traversals.

Description: You are to implement an algorithm to solve Doublet puzzles. A Doublet is a word transformation puzzle in which one word is transformed into another by changing one letter at a time, where each resulting letter sequence is also a word. For instance, given the words head and tail, your program might produce the following output:

head

heal

heil

hail

tail

Since computers don’t intrinsically know common English words here is a list of common (or not so common?) words you can use to build your transformations: words.zip. The word list is alphabetized, so you shouldn’t need to sort it, and is stored one word per line. If you would like a list of just 4 letter words, you can find one here. It is alphabetized as well.

You are to read the words into an array. Using the indexes in the array, build an adjacency matrix representing the graph connecting all words that differ by one letter. Using your queue from project 2, do a breadth first traversal of the graph, keeping the visited nodes in a list (either your linked list or an array) to avoid cycles. When you have printed the answer, use the list to free up the space taken by all the used nodes. I suggest you add a parent pointer to each node to make it easier to print the path when you find one.

Turn-in: Print out your code with a sample run attached as comments after the main program and turn it in.

Hints: One way to do this one is to read the word list into an array. Then build an adjacency matrix with 0’s for words that aren’t connected and 1’s for words that are. To see if one word can be converted to another, start with the first word and do a breadth first traversal of the graph trying to reach the second word. If you can reach the second word, the path taken represents the sequence of transformations needed to turn the first word into the second word by changing one letter at a time; otherwise print that the transformation is impossible.