Word Ladders

MCS-178: Introduction to Computer Science II

Before you get to lab, you may want to work through the emacs tutorial. See Using Emacs below.

Introduction

In this project you will be using stacks and queues to solve word ladders. You'll do all your programming in Java and work individually.

In a word ladder problem, the goal is to change one word into another by changing one letter at a time. For example, a word ladder that changes DRY into WET in 4 steps might read:

DAY BAY BAT BET WET
We have already implemented two algorithms for you, depth-first search and iterative deepening depth first search. Both of these algorithms use a stack. Your goal is to implement a breadth-first search algorithm to find a word ladder using the queue data structure.

Getting started

For this project, you'll have three goals

The Unix shell

You'll be using two tools, the Unix shell and emacs, to do your work. The following shell commands are the first ones you'll want to learn:
  ls              ;; list the files in the current directory
  ls -l           ;; list the files with their permissions, owners, time stamps, etc.
  cd dir-name     ;; change to directory named dir-name in the current directory
  cd ..           ;; go up one directory
  cd              ;; go back to my home directory
  emacs &         ;; launch emacs; the & says do so in the background
  javac *.java    ;; compile all the java files in this directory to class files
  java class-name ;; run the main in java class file ClassName.
  javadoc -d docs *.java   ;; Generate documentation in html for all java classes,
                           ;; and store them in directory docs.
                           ;; You can view docs/index.html in your favorite browser.
  man command     ;; tell me everything about a Unix command (try 'man ls')
  cp file1 file2  ;; make a copy of file1 and name it file2
  cp -r dir1 dir2 ;; make a copy of directory dir1 and name it dir2
To make a copy of all the files, the simplest approach would be to use the shell to copy the whole directory containing the files. In a shell window, go to the directory where you want to put your files and type
  cp -r ~mc28/labs/word-ladders/word-ladders .
(Note that this command ends with a space and then a period. Ask for help with this if you need it.) You will get a new directory called word-ladders.

Using Emacs

To do this project, you'll edit .java files, and compile them using into .class files. Once you've made class files, you can run your programs. Outside of lab, I recommend you work through the Emacs tutorial. To do so,
  1. Launch emacs by opening a Unix shell and typing:
      emacs &
    The & makes the program run in the background so that you can continue to type other commands to the Unix shell should you want to. You can also launch emacs from the desktop by clicking on the K in the lower left corner and selecting emacs under applications.

    Be careful not to type another key until you've finished reading the help that comes up on the screen. Note that the 'M-' key is the Alt on the Linux machines.

  2. Memorize how to exit, play around for a minute or two, and then exit emacs.

  3. Restart emacs.

  4. Work through the Emacs tutorial. As you do so, familiarize yourself with the GNU Emacs Quick Reference Guide. You may wish to check off each command on the reference guide as you learn it.

Emacs and Java

A few things are particularly helpful when working with Java in Emacs. If you like 2-space indenting for blocks as on the left below:
  // 2 spaces             // 4 spaces
  if (true) {             if (true) {  
    a = 20;                   a = 2;            
    b = 30;                   b = 3;     
  }                       }            
I recommend editing the file ~/.emacs in your home directory and inserting the following lines at the start or at the end of that file:
  (c-add-style "java-indent-2" '("gnu" (c-basic-offset . 2)))
  (setq c-default-style '((java-mode . "java-indent-2")))

To reindent your whole file, type

   C-x h             ;; Control-x followed by h makes the whole buffer the "region"
   M-x indent-region

To compile within emacs type

   M-x compile
Emacs will ask you for a compilation command. Replace "make -g" with the one of your choosing, perhaps "javac Queue.java". or, if you want to compile everything in the directory, "javac *.java".
   C-x `       ;; this command (control-x backquote) automatically
               ;; moves the cursor to a compilation error.  The key `
               ;; is found in the top left corner of most keyboards.

Tour of the code provided

First, compile and run the program by going into a shell, changing to your word-ladders directory, and typing
  javac *.java

There are two dictionaries you can use. The file dict contains a test dictionary of all words legal in Scrabble tournaments using the letters A through H only. Feel free to edit that test file as you see fit as you test your program. The full official tournament Scrabble dictionary is in ~wolfe/lib/TWL98, which is the default dictionary used by WordLadderSolver if you don't explicitly provide on as a command line argument.

You can now run the main(String[]) method in each of the class files:

  java Stack               ;; Run my test routines for Stack
  java WordDictionary dict ;; Test WordDictionary on dictionary file dict
  java WordLadderSolver    ;; This will output information on program usage
Try running the WordLadderSolver with varying arguments to learn what they all do.

Next, you'll want to familiarize yourself with the class interfaces. You'll find the documentation generated by javadoc by clicking here.

Programming exercises

  1. We would like you to document all the code you write in Java. You can do so now, or as you go. Add javadoc comments to your Queue class. There are two kinds of javadoc comments I'll want you to add, one preceding the class definition, and one preceding each public method. Javadoc commands start /** and end */. Regular (i.e., non-javadoc) comments start /* and end */. If a regular comment appears on only one line, you can use begin the comment with //.

    You can now make the documentation as described in the section Unix Shell above.

    If you wish to find more information about javadoc, including how to include links and other information in your comments, visit the javadoc webpage. For this project, you can simply include plain text in your comments.

  2. Complete the implementation of Queue.java. Currently it only has "stubs" and no code. The code should mirror that in Concrete Abstractions with the exception that dequeue() returns the removed element rather than the queue.

    I recommend you write one method at a time, and test each one as you go. Start by implementing the constructor Queue(), then compile and run. The call to debug() in main should print out the initial state of the data structure.

    Next, edit the method enqueue(). You can then write add calls to enqueue() to your main() to test your implementation so far.

    If you don't see how to test your procedures one by one as you write them in Java, ask! It's an important skill.

    Now, fill in the remaining methods one by one, testing each as you go. I'd implement dequeue() next, so you can test how it interacts with enqueue() when you wrap around the end of the array elements. If you want to, you can skip grow() for now and continue with the project, so long as you make sure the initial queue size is large enough.

  3. Before proceeding, we recommend you review the tour of code provided once more.

    Write and test the code for bfs() in WordLadderSolver.java. Unlike the code for dfs(), the code should be iterative, and can all be contained in one method with a couple while or for loops. You should find that bfs() works quite a bit faster then iddfs() and still finds a shortest word ladder. Your procedure should output trace information if tracing is turned on.

    The following general breadth-first search pseudocode is from Manber's text Algorithms. It computes a breadth-first search tree from v:

    
    Algorithm Breadth_First_Search (G, v)
    Input:  undirected graph and a start vertex v
    Output: depends on the application
      mark v;
      put v in a queue;
      while the queue is not empty do
        remove the first vertex w from the queue;
        perform prework on w (depending on application)
        for all edges (w,x) such that x is unmarked do
          mark x;
          add (w,x) to the tree T;
          put x in the queue
    
    

  4. Write and test the code for dfs() in WordLadderSolver.java. Depth first search is identical to breadth first search, except it uses a stack in place of a queue. The word ladder found for your dfs() should be identical to that found by dfs2(), a procedure we've provided. (The latter procedure uses an implicit stack meaning that the Java interpreter has a stack which is keeping track of the recursive calls to dfs2.)

Optional exercises

Feel free to come up with other questions about word ladders and try to answer them. For example, is it possible to get from any three letter word to any other? What are the two three-letter words in the dictionary which require the longest word ladder to join them? To get started answering either of these questions, you'll have to add a short method or two to the WordDictionary() class.

Postlab

You do not need to write up a report for this project. You will be graded, however, on your coding style and clarity and appropriateness of your javadoc and non-javadoc comments, and on your testing. In particular, be sure to leave test cases in the main of queue.java, along with comments about your choice of test cases.

Unless you've done optional exercises, you only need to submit the files Queue.java and WordLadder.java for grading.

The gradesheet for the project is available in PostScript or PDF format. (If you print a copy out, you can staple it to the front of your project report to save paper.)

Submitting your code

To submit your code, do the following:
  1. Make sure your code is documented. In particular, report any bugs in a comment at the head of your file. Make sure javadocgenerates the right documentation files and that they look good.

  2. Reindent all your code in Queue.java and WordLadderSolver.java using C-x h followed by M-x indent-region in emacs.

  3. In a shell, cd to your project directory and type ls to make sure you are in the right place. Finally, type
    ~wolfe/public/178/submit Queue.java WordLadderSolver.java
    
    You could also submit other files on the same line if you did any optional exercises.