Programming Assignment 6 SOlution

1. Go to box.miami.edu and make sure you see the version of prog05
   you meant to turn in this morning.  If not, send email to
   vjm@cs.miami.edu right away.

0. Create package prog06 and copy MaintainQueue.java into it.

1. Run MaintainQueue and make sure you know how it works.  It won't
   print the list of names in the queue until you implement toString
   in the next step.  Add a few people, peek, remove, etc.  What
   happens when you remove from an empty queue?  poll?  peek?  element?

2. Implement toString in MaintainQueue.  Visit the elements of
   customers using the new kind of for loop and append them to a
   single String separated by spaces.  Test.

3. In ArrayQueue.java, read and understand offer and peek.
   "Understand" means that you are ready to write either of them on
   the quiz tomorrow!  Implement poll.  Test using MaintainQueue.
   Read and understand the definition of the Iter class.

4. In LinkedQueue.java, read and understand offer and peek.  Implement
   poll.  Implement hasNext() and next() in the Iter class. Unlike
   ArrayQueue.Iter, it needs only one variable to keep track of the
   next node to be visited.  Test using MaintainQueue.

5. Create a class WordStep with a variable

  static UserInterface ui = new GUI();

   and a main method.  In the main method, create a new WordStep and
   store it in a variable named game.  Using ui, ask the user for a
   starting word and a target word.  Ask if the human or the computer
   should play using

    String[] commands = { "Human plays.", "Computer plays." };

   Call game.play or game.solve with the starting word and the target
   word.  Create empty methods so this compiles and runs.

  void play (String start, String target) { }
  void solve (String start, String target) { }

   Inside play, do the following forever (until the return occurs).
   Tell the user the current word (the start) and the target word.
   Ask for the next word.  Set the start word variable to that next
   word.  If it equals the target, tell the user ``You win!'' and
   return.  Otherwise keep looping.  Test.  (Also deal with cancel.)

HOMEWORK

6. In WordStep, create a static boolean method offBy1 which takes two
   String variables as input and returns true if they have the same
   length and differ in exactly one character.

   Modify play so that it uses offBy1.  If the word that the user
   suggests is not one letter away from the current start word, warn
   the user and DO NOT change the current (start) word variable.
   Test.  You still will be able to use nonsense words like "snon".

7. In main, just after creating the new WordStep, ask the user for the
   name of a word file and call game.loadWords(filename).  Add a
   List<String> words to WordStep initialized to an ArrayList<String>,
   and write loadWords that adds all the words in the file to the
   list.

   Write a find method that finds a word in words.  It should return
   the index of the word or -1 if it is not there.  Modify main to
   check that the start and target words are in the list.  Test using
   the file called words (not words.txt by the way) in the prog06
   directory.

8. Modify reallocate() in ArrayQueue to use System.arraycopy.
   Sometimes it has to call it twice.  Test.  Make sure you add enough
   entries when you run MaintainQueue to trigger reallocate().  To
   test set labReallocate to false.  Make sure you do tests with
   first < last    and with   first > last.

9. Modify ArrayQueue.Iter to using a single index variable and no
   count variable.  If the queue is empty, then the constructor should
   set index=-1.  If index==last, then next() should set index=-1.
   Test by setting labIterator to false.

10. Now to implement WordStep.solve.

   Create an array of int called parents whose length is the same as
   the word list.  Initialize all the entries in parents to -1.

   Create a Queue of Integer.  Put the index of the start word into
   the queue.

   While the queue is not empty, remove an index.  Call the word at
   the index the current word.  Go through the list of words and look
   for words which aren't the start word, don't have parents set yet,
   and are one letter different from current word.  For each one you
   find, put its index into the queue and set parents at that index to
   the index of the current word.

   Also check if the word is the target.  If it is report success.  To
   get the solution in reverse order, follow the indices in parents
   the start word.  Display the solution in forward order.  Return.