Chapter 1

Introduction

A word-chain is a sequence of English words where each word is one letter away from the words before and after it. For instance,

(list "eat" "ear" "bar" "brr" "err" "ere" "are" "ate")

is a word chain from eat to ate.

In this lab, you will write a program that finds the shortest word chain connecting two given words in a dictionary. You will do that by viewing a dictionary as a graph where each node is a word and edges connect words that are one letter apart. For instance, the dictionary consisting of the words aaa, aab, aba, baa, abb, bab, bba, and bbb would look like this as a graph:

In this graph, every node is a word, and each edge connects a word to all the other words in the dictionary that are exactly one letter away from it (which means that every edge in this graph is bidirectional).

For this lab we will find it useful to use the following definition of a graph:

;; a graph is:
;; (make-graph (string -> boolean) (string -> (listof string)))
(define-struct graph (node? neighbors))

There are a few differences between this definition of a graph and the one you've seen in class. For one thing, this uses strings instead of symbols (and thus nodes can be manipulated with the functions string->list : string -> (listof character), list->string : (listof character) -> string, and string=? : string string -> boolean). For another, rather than explicitly containing a list of all valid nodes, instead it holds a function that will tell whether a particular string is a node in the graph.