CMU 15-211 Fundamental Structures of Computer Science I

Assignment #2: Amazing Word Game

Due: Monday, February 12, 1996, 11:59 PM

This assignment will be collected automatically as described in ``Homework handin procedures.'' Also, please put your name and recitation section at the top of your handin.


In this assignment, you will build several data structures that will be used as part of a program that finds paths through mazes. You will then extend this program to find ``paths'' between words in a dictionary, where a path is a sequence of words in which each differs in only one letter from the previous one. For example, you will find that the word ``shave'' can be transformed into ``beard'' as follows:

shave --> stave --> stare --> stars --> sears --> bears --> beard

The assignment consists of three parts. In Part 1, you will build an abstract data type called a Queue. In Part 2, you will build an abstract data type called a Graph. The underlying representation for a Graph will be an adjacency list. In Part 2 you will also write a procedure for reading the description of a maze from a text file and building the corresponding Graph. After completing Part 2, the Queue and the Graph will be used by a search routine (which we provide) that finds a path between two points given by the user. Finally, in Part 3, you will associate a word with each ``room'' in the maze and extend the program from Part 2 to find paths between words.

The code we have given out to you is in five files in the assign2 directory: maze.c, queue.c, queue.h, graph.c, and graph.h. You will add code to the files maze.c, queue.c, and graph.c and then hand them in. You will not need to hand in or make any modifications to the files queue.h or graph.h. This assignment is more difficult than assignment 1, so START EARLY.

At the end of this assignment is a comment sheet; it is entirely optional.

Part 1: Queues [40pt]

In this part, you will implement several of the operations of a Queue abstract data type. The class definition of a queue of ints based on a linked-list implementation is given in file queue.h. You should not modify this file. You will have to write the code for Queue::insert, Queue::length, and Queue::remove. We have provided code for the constructor Queue::Queue in the file queue.c. Your code should match the function prototypes we have given, and make sure to free up storage appropriately in Queue::remove.

Your solution (a file containing all the routines) should be in a file named ``queue.c''.

Part 2: Graphs and Adjacency lists [40pt]

A maze, shown below, consists of some numbered rooms with two-way passages between pairs of them. This is more commonly known as a graph, the rooms are called nodes or vertices, and the passages called edges. Two nodes connected by an edge are called neighbors. We will discuss more about algorithms on graphs later on in this course.

postscript picture of maze

For this part you are to write a program that reads in a maze description from a file and builds the corresponding graph. The graph will be represented using an adjacency list. A ``maze description'' is simply a file containing pairs of numbers describing each passage by its end points. The pairs are preceded by two size numbers: the number of rooms and the number of passages. The rooms are numbered from 0 up to (#of rooms - 1). For example the maze above could be described by:

       0 2
       0 3
       2 4
       5 6
       1 4
       2 3
The Graph corresponding to this maze will have 7 nodes, and 6 edges.

Our representation of a Graph with n nodes will be an array of n node structures called Adj_list. The ith entry in the array, Adj_list[i], corresponds to the ith node in the graph, and is represented by the following structure

struct node {
  word_t name;     // the 'name' of the node (the 5 letter word associated with it)
  int index;       // the index of the node in Adj_list
  list_element *neighbors; // a list of the neighbors of this node
You do not have to worry about the name field until part 3. In this structure, neighbors is a pointer to a linked list containing the indices in Adj_list of the node's neighbors. The list elements are represented by the following structure.

struct list_element {    // an element on a node's list of neighbors
  int neighbor;          // the index of a neighbor
  list_element *next;
Since your program will only find out the number of nodes at run-time (when it reads in the file) the array Adj_list will have type ``node *''. When you read in the number of rooms you will then allocate enough space for that many nodes.

Your job: Your job consists of two tasks. First, you are to implement the operations Graph::Graph, Graph::insert_edge, Graph::find_node_by_number, and Graph::nodes described in file ``graph.h''. Your solution belongs in file ``graph.c''. Next, you should write a function

Graph *read_maze(fstream &mazefile)
that reads the maze from a file and builds the corresponding graph. (If you prefer, you may make this a member function of the Graph class and appropriately change graph.h: if so, you will need to slightly modify the main routine and you should hand in graph.h as well.) We have given you the code for associating an input stream to the input file, just like on Assignment 1. (The ``&'' is needed for passing the input stream into the procedure.) Your code should be in a file called maze.c (or you may put it into graph.c if you write the code as a member funcion). For simplicity in this assignment (all parts), you do not need to check that new returns a valid pointer, but you may if you wish.

In maze.c we have given you one half of a program to find paths through mazes. After doing Parts 1 and 2, you will have completed the second half of that program. You can use the parts we have provided to help you test your code. For example, if after reading in the maze shown above (also in the file tiny.maze) you typed:

0 1

the program should print:

0 2 4 1.

If you typed:

0 6

the program should print:

No path.

The files tiny.maze, small.maze, med.maze, and big.maze contain mazes of different sizes.

We have also given you object code that runs on the DECstations and SPARCstations in files maze.dec and maze.sparc that you can run. It is possible that your program may find somewhat different paths than this one and still be correct.

Hint: If you are having trouble debugging your code, you may wish to write a short routine that prints out the contents of the adjacency list you create. Or, you may wish to continue to part 3, after which it may be easier to observe the execution of your code.

One note: your compiler may give a warning that some line in main is not reachable. That's just because we have a ``while(1)'' loop in the code.

Part 3: Paths between words [20pt]

You may be wondering how we created these maze files. These were created by starting from a list of 5-letter words and declaring that two words are neighbors if they differ in only one letter. If 17 and 32 are connected in the maze, this corresponds to words 17 and 32 in the word file (the first word is number 0) differing in only one letter. The file ``small.maze'' was created from ``small.dictionary'' in this way. Similarly for files ``med.maze'' and ``big.maze.''

In Part 3, we ask you to modify the code in graph.c and maze.c so that:

  1. In addition to reading in a maze, your program also reads in the associated dictionary of 5-letter words.

  2. Instead of asking the user for two numbers, it asks for two words.

  3. If one of the words given by the user is not in the dictionary, it should tell the user.

  4. Your program finds the path between the numbers associated with the two words. For instance, if the words are words 1 and 8 in the dictionary (where the first word is word 0), it finds a path between nodes 1 and 8 in the maze. However, instead of printing out a list of numbers, your program should print out the corresponding list of words.
In doing this part of the assignment, you should fill in the routines Graph::name_node and Graph::find_node_by_name in graph.c.

Here are some paths you can use to test out your program. In the small database (small.maze and small.dictionary) words corresponding to the numbers listed in Part 2 are:

 bread cheer -> bread breed creed creek cheek cheer

 blood sweat -> blood brood broad bread breed creed creek cheek cheer
                sheer sheet sweet sweat

 blood water -> no path.
You can also try in the big dictionary:

 party class -> party parts ports forts foots boots blots blows glows
                gloss glass class

We give you object code for this problem in the files wordmaze.dec and wordmaze.sparc that you can try out. Your solution should be in maze.c.

Code in queue.h

 * The queue is represented as a linked list, with ``next'' pointers
 * pointing from a node to the one behind it in line. Elements are
 * inserted into the tail of the queue and removed from the head.
 * An empty queue:
 *    (queue_t) p->+------+
 *                 | NULL | tail
 *                 +------+
 *                 | NULL | head
 *                 +------+
 * A queue with two elements, 'a' and 'x', inserted in that order:
 *              p->+------+           +------+next    +------+
 *                 |   *----tail----->| NULL |<-----------*  |next
 *                 +------+           +------+        +------+
 *                 |   *  | head      |  'x' |item    |  'a' |item
 *                 +---|--+           +------+        +------+
 *                     |                                 /|\
 *                     +----------------------------------+

struct queue_node {
  queue_node *next;       /* points to the next element, or NULL */
  int item;

class Queue {
  Queue();                // Constructor.  Executed when you create new one

  int insert(int value);  // Insert integer into queue
  int remove(void);       // If queue is not empty, remove element from the
                          // queue.  Otherwise, return -1.
  int length(void);       // How many elements are in the queue
  queue_node *tail;       // points to tail of queue, or NULL
  queue_node *head;       // points to head of queue, or NULL
  int          len;       // length of the queue

Code in queue.c

#include <iostream.h>
#include "queue.h"

// Code for a queue of ints, using linked-list implementation

Queue::Queue()  // no type needed for constructor
  head = NULL;
  tail = NULL;
  len = 0;

int Queue::insert(int value)
// Some of your code for Part 1 goes here.

int Queue::length(void)
// Some of your code for Part 1 goes here.

// For cleanliness, sets tail to NULL on empty queue.
int Queue::remove(void)
// Some of your code for Part 1 goes here.

Code in graph.h

typedef char word_t[6];  // 6, not 5, so we have space for '\0'

struct list_element {    // an element on a node's list of neighbors
  int neighbor;          // the index of a neighbor
  list_element *next;

struct node {
  word_t name;         // the 'name' of the node (the 5 letter word associated with it)
  int index;           // the numeric identifier for the node: index in Adj_list
  list_element *neighbors; // a list of the neighbors of this node

class Graph {
  Graph(int n);         // Constructor.  Executed when you create a new one.
                        // n is the number of nodes in the graph

  int name_node(int number, char *name);         // Part 3 only: Assigns a name to a node

  int insert_edge(int neighbor1, int neighbor2); // Inserts an edge into the graph
                                                 // returns 0 on a success, -1 on a failure

  node *find_node_by_number(int index); // Given a node number, returns that node structure

  node *find_node_by_name(char *name); // Part 3 only: Given a node 'name', 
                                       // returns that node structure

  int nodes(void);                     // Returns number of nodes in graph.

  int number_of_nodes;
  node *Adj_list;

Code in graph.c

#include <iostream.h>
#include <strings.h>
#include "graph.h"

// Implementing graphs as an adjacency list...

Graph::Graph(int n)
// Some of your code for Part 2 goes here.

int Graph::name_node(int number, char *word)
// Some of your code for Part 3 goes here.

int Graph::insert_edge(int neighbor1, int neighbor2)
// Some of your code for Part 2 goes here.

node *Graph::find_node_by_number(int index)
// Some of your code for Part 2 goes here.

node *Graph::find_node_by_name(char *word)
// Some of your code for Part 3 goes here.

int Graph::nodes(void)
// Some of your code for Part 2 goes here.

Code in maze.c

#include "queue.h"
#include "graph.h"

#define INIT (-1)

// This routine reads a maze from the stream pointed to by file, and
// builds a new Graph to represent the maze.
// The following line is an example of how you could read from the file.
//                      mazefile >> rooms;
// The first line of the file contains the number of rooms in the maze,
// which is an integer.  The second line contains the number of passages,
// another integer.  Each succeeding line contains a pair of room
// numbers, which represents a passage.
// Note that in the maze file, a passage i j represents a passage from
// room i to room j and a passage from room j to room i.

Graph *read_maze(fstream &mazefile)
// *******************************
// Your code for Part 2 goes here.
// *******************************

int main(void) 
  fstream mazefile;       // the file containing the maze
  fstream dictfile;       // the file containing the dictionary
  char file_name[50];     // temporary space for typing in file names
  Graph *maze;            // the maze
  word_t dict_word;       // the words
  int i;                  // an index variable
  int *parent;            // the parent array;
  cout << "Enter the name of the mazefile: " << endl;
  cin >> file_name;, ios::in);  // open in "input mode"
  if (!mazefile) {
    cout << "Sorry, can't find file " << file_name << endl;
    return 1;

  maze = read_maze(mazefile);

// The following seven lines are needed for Part 3.
// Uncomment them when you start to work on Part 3.

//  cout << "Enter the name of the dictionary file: " << endl;
//  cin >> file_name;
//, ios::in); // open in "input mode"
//  if (!dictfile) {
//    cout << "Sorry, can't find file " << file_name << endl;
//    return 1;
//  }

// ****************************************************************
// Your code for Part 3 goes here.  You access the dictionary using
// dict_file >>                                                    
// ****************************************************************

  parent = new int[maze->nodes()];
  Queue myqueue;         // creates an empty queue
  while(1) {
    int start, end, current;
    node *current_node;

    list_element *ptr;

// ***********************************************************
// For Part 3, you will have to rewrite the following 3 lines.
// (Your code may take more than three lines.)                
// ***********************************************************

    // read in start and end room numbers

    cout << "Give two vertices: ";
    cin >> start;
    cin >> end;
    // initialize parent array

    for(i=0; i < maze->nodes(); ++i) parent[i] = INIT;

    // THE SEARCH: 
    // begin at "end" and go back to start so can print out more easily.

    // The following is an implementation of breadth-first search

    parent[end] = end;    // assign a dummy value to parent[end]
    myqueue.insert(end);  // start it off

    while(myqueue.length() > 0) {
      current = myqueue.remove();
      if (current == start) break;  // can stop now!

      // search the adjacency list of current node for
      // neighbors that have not yet been visited

      current_node = maze->find_node_by_number(current);
      for(ptr = current_node -> neighbors; ptr != NULL; ptr = ptr->next) {
        if (parent[ptr->neighbor] == INIT) {
          parent[ptr->neighbor] = current;

    // now, read off the path

    if (current != start) cout << "No path." << endl;  /* didn't find it */
    else {
      for (i=start; i != end; i=parent[i])
        current_node = maze->find_node_by_number(i);
        cout << current_node->name <<   " ";
      cout << (maze->find_node_by_number(end))->name <<  endl;

    // empty out the queue, so can start over
    int junk;
    while(myqueue.length() > 0)
      junk = myqueue.remove();
  } /* end while(1) loop */