Assignment 2: Ordered Word Ladders

An ordered word ladder ('owl') is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by one action:

1. changing one letter, e.g. barn→born

2. adding or removing one letter, e.g. band→brand and bran→ran

The following are examples of word ladders of different length:

• ban→bar→boar→boat→goat, length 5

• an→can→cane→dane→date→mate→mite→site→size, length 9

Phase 1

At the heart of the assignment is a function that compares 2 arbitrary null-terminated strings and returns true if the strings satisfy one of the 2 conditions above, and false otherwise. This function has signature:

   1 bool differByOne(char *, char *)

Write such a function and of course test it.

Phase 2

Generate a graph that represents all the words in the input that differ by one. Each word is represented as a vertex in the graph, and vertices are adjacent if the corresponding words differ by one. The words can be found on stdin, and are in dictionary order. You may assume that they consist of just lower-case letters (a-z) in this assignment. You must use the graph ADT provided in lectures in this assignment.

For example, if a dictionary consists of the 12 words:

case cast cat cats cave cost cove love most sale save suave

then the graph that represents all ordered word ladders is:

             0
           /   \
          1     4
         / \   / \
        2   5 6  10
        |   | |   |
        3   8 7  11

where the numbers 0..11 represent the 12 words in order. You can check yourself that each path in the graph corresponds to an 'owl'.

This owl graph is interesting because it has 4 maximal word ladders, which are easy enough to read off the graph of course.

Owl graphs typically are not trees. Take the dictionary pan pen pin which generates the complete graph on 3 vertices:

           0
          / \
         1---2

This clearly has one maximal path of length 3. More basically, consider a single-letter dictionary a b c d, which generates a tetrahedron and has a maximal owl of length 4.

You