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.

So, for example, if a dictionary consists of just the 10 words:

case cast cat cats cave cost most sale save suave

then the graph that results is:

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

where the numbers 0..9 represent the 10 words in order. You can check yourself that each path in the graph corresponds to an ordered word ladder