CSCI 3310
Fall 2007
Large Programming Assignment 3

Assigned: Nov 5
Due: Sun., Dec. 9, 11:59pm (This is a firm deadline. No late assignments please.)

Read the entire assignment before you begin to implement it. You will almost certainly want to read it at least twice, and you will need to come back to it while writing your program.

The Rickety Bridge problem

A group of people need to walk across a rickety bridge from West to East. Only two people can be on the bridge at the same time. It is night, and to cross the bridge, a person needs a flashlight. But there is only one flashlight. So two people will walk across the bridge from West to East, then one will walk back, then two will cross, and one will walk back, etc.

The people do not all walk at the same rate. For example, one might take one minute to cross the bridge, while another takes five minutes. When two people cross together, they walk at the speed of the slower one.

The problem is to find a way for the people to cross in a way that takes the least total amount of time.

Example. Suppose that the people are as follows, each with a time, in minutes, to cross the bridge.

It is possible to cross the bridge in 17 minutes, as follows. The solution shows who is on each side of the bridge, at each step. It also shows the side of the bridge that the Flashlight is on.

An algorithm for the Rickety Bridge problem

Imagine a generalization of the problem where, instead of everybody starting on one side of the bridge, the starting configuration has one group on the West side and another group on the East side. The goal is still to get the people on the West side to the East side, but some have already crossed.

It is not clear who should cross the bridge first. So just try all pairs of people. For example, try Groucho&Chico, Groucho&Harpo, Groucho&Zeppo, Chico&Harpo, Chico&Zeppo, and Harpo&Zeppo.

After letting the chosen pair cross the bridge, you need to select someone to cross back. We have argued that you can always select the fastest walker for the return trip. So do that. Now you have a different configuration of people, some on the West side and some on the East side. Just find the best solution from there.

Use the shop-around principle. Try all pairs of people, and see which pair leads to the fastest crossing. Use that one.

This algorithm ends up computing the same thing many times. To speed it up, you will need to memoize. Whenever you compute a result, store it for future reference. Whenever you need a result, first look in the table to see whether you already know that result.

The Person class

An object of this class represents a person in the Rickety Bridge problem. A person has a name (a string) and a crossing time (a real number). Provide a constructor that takes a name and a crossing time and initializes the information for a person.

Provide accessor methods that return the name and the time.

Provide a print method that prints this person's name on the standard output.

Provide an equals method that determines whether two persons are equal. By definition, two persons are equal just when they have the same name. So A.equals(B) should return true if A's name is the same as B's name.

Provide a compareTo method that compares two persons. You can use compare to determine if two persons are the same, or to determine an order of two persons in a list. If A and B are two persons, then A.compareTo(B) should return

That is,

1. If A crosses faster than B, then A.compareTo(B) should return -1.
2. If B crosses faster than A, then A.compareTo(B) should return 1.
3. If A and B cross at the same rate, then A.compareTo(B) should yield the same result as A.getName().compareTo(B.getName()).

The PersonSet class

Write a class, PersonSet, where an object of this class is a set of persons. It is a persistent data type, providing only operations that leave the object unchanged. Operations work by creating new objects, not by modifying existing objects. The PersonSet class supports the following.

PersonSet()

When a PersonSet is constructed using the parameterless constructor, it is an empty set.

isEmpty()

s.isEmpty() is true if s is an empty set.

cardinality()

s.cardinality() is the size of s (the number of persons in set s).

getFirst()

s.getFirst() returns the member of set s that comes first in the order determined by the compare operation of the Person class. So it returns the person in set s who walks the fastest, and, if two walk equally fast, it returns the one whose name is alphabetically first.

getRest()

s.getRest() returns the set that you get by removing person s.getFirst() from s.

insert(p)

s.insert(p) returns the set that you get by adding person p to set s. If p is already in s, it returns the same set s.

remove(p)

s.remove(p) returns the set that you get by removing person p from set s. If p is not in s, then it returns the same set s.

hashCode()

s.hashCode() returns an integer suitable to use as a hash value, for using a PersonSet object as a key in a hash table.

equals(t)

s.equals(t) returns true just when sets s and t have exactly the same members.

print()

s.print() prints set s on the standard output, in the form {x,y,z} where x, y and z are the names of its members. In general, it prints the members in some order, inside braces.

printMems()

s.printMems() prints the members of set s on the standard output, separated by commas. This is the same as s.print(), but does not print the braces.

A convenient way to implement a set is as a linked list, kept in compareTo order, so that getFirst just gets the person at the beginning of the list and getRest just gets the list after the first person (the next reference). To insert a person, do the insertion at the correct position. You will find the insert and remove methods easiest to write using recursion, but if you are a glutton for punishment, you are free to use loops.

The Plan class

A configuration is a triple (W, E, F) where W and E are PersonSets and F is a character, either 'W' or 'E'. Configuration (W, E, F) indicates that the persons in set W are on the West side of the bridge, the persons in set E are on the East side of the bridge, and the flashlight is on the side indicated by F ('W' for West, 'E' for East). A plan is a list of configurations, telling how the movement takes place. Additionally, each step of the plan holds a real number telling the time needed to reach the end of the plan, from that point onward. For example, suppose that the persons are Groucho, Chico, Harpo and Zeppo, with times 1, 2, 6 and 10, respectively. A plan might be the following.

Create a Plan class, where an object of class Plan represents a plan. It should contain a West set, an East set, a flashlight side indicator, a time, and a reference to another Plan object representing the rest of the plan. You can use null to indicate the end of the plan.

Provide a suitable constructor and accessors. Think about what you will need.

Provide two methods for printing a plan. p.print() prints plan p in a form suitable for textual output. p.printHTML() prints plan p as an HTML table, for inclusion in an HTML document. For example, if the plan above is asked to print itself using printHTML, it might show something like the following. (You can change the appearance.)

<table border="2">
  <tr>
     <th bgcolor="lightgrey">West</th>
     <th bgcolor="lightgrey">East</th>
     <th bgcolor="lightgrey">Flashlight on</th>
     <th bgcolor="lightgrey">Total time</th>
  </tr>
  <tr>
    <td align="center">Chico, Groucho, Harpo, Zeppo</td>
    <td align="center"> </td>
    <td align="center">W</td>
    <td align="center">0</td>
  </tr>
  <tr>
    <td align="center">Harpo, Zeppo</td>
    <td align="center">Chico, Groucho</td>
    <td align="center">E</td>
    <td align="center">2</td>
  </tr>
  <tr>
    <td align="center">Groucho, Harpo, Zeppo</td>
    <td align="center">Chico</td>
    <td align="center">W</td>
    <td align="center">3</td>
  </tr>
  <tr>
    <td align="center">Groucho</td>
    <td align="center">Chico, Harpo, Zeppo</td>
    <td align="center">E</td>
    <td align="center">13</td>
  </tr>
  <tr>
    <td align="center">Chico, Groucho</td>
    <td align="center">Harpo,, Zeppo</td>
    <td align="center">W</td>
    <td align="center">15</td>
  </tr>
  <tr>
    <td align="center"> </td>
    <td align="center">Chico, Groucho, Harpo, Zeppo</td>
    <td align="center">E</td>
    <td align="center">17</td>
  </tr>
</table>

You might find it helpful to have one or more private methods to help.

The RicketyBridge class

Write a class, RicketyBridge, that is responsible for solving the Rickety Bridge problem. The constructor should take a PersonSet, telling the initial persons on the West side of the bridge. The memoization table should be one of the variables in the class. Use the Java class Hashtable for the memoization table.

Provide a method that takes no parameters, and returns an optimal plan for the set of persons given in the constructor. The plan will be an object of class Plan.

You will want a helper method that takes two sets indicating who is on the West side and who is on the East side. It should assume that the flashlight is on the West side, and produce an optimal plan for this starting configuration. Be sure to look in the memoization table before trying to compute the answer, since there no need to compute it if you already know the answer. This function can use itself to solve subproblems. If you only store configurations where the flashlight is on the West side of the bridge in the memoization table, then it suffices to use the set of persons on the West side as the key for the hash table.

If the number of persons in the West side is less than or equal to 2, then either one or two persons walk across the bridge from West to East, and the plan is over. (There will be just two configurations in the plan, the start configuration and the end configuration.) But if there are three or more persons on the West side of the bridge, then the heart of the algorithm is as follows. The loops choose person1 and person2 to walk together from West to East, and person3 to walk back from East to West. W1 and E1 are the West and East side sets after person1 and person2 walk from West to East. W2 and E2 are the sets after person3 walks back.

  Plan findPlan(PersonSet W, PersonSet E)
  {
    ...
    for(s1 = W; !s1.isEmpty(); s1 = s1.getRest())
    {
      person1 = s1.getFirst();
      for(s2 = s1.getRest(); !s2.isEmpty(); s2 = s2.getRest())
      {
        person2 = s2.getFirst();
        W1 = W.remove(person1).remove(person2);
        E1 = E.insert(person1).insert(person2);
        person3 = E1.getFirst();
        W2 = W1.insert(person3);
        E2 = E1.remove(person3);
        restOfPlan = findPlan(W2, E2);
        ...
    }
    ...
  }

User interface, part 1

Write a main method in the RicketyBridge class. Design your program to read information about the collection of persons, in whatever format you like, from a file, where the name of the file is the command parameter, args[0]. It should print the plan in a simple form, using the print method of the Plan class.

User interface, part 2

After the program works using the first user interface, make it work with a web-page interface.

No args[0]

When the argument array has length 0, make your program read from the standard input. Do not ruin interface 1 to do this. Make it work both ways.

When there are no arguments in the args array, also write a web page to the standard output instead of the simpler style of output. See below for a discussion of what the program should print in this case.

A form

Create a page that contains a form. Here is a sample page.

• form.html

If you look at the form with a browser, you will see boxes to be filled in. Now look at the form with a text editor, not with a browser, so that you see the html text. The data boxes have names, NAME1, TIME1, etc.

Getting information from the form

When someone fills in the form and pushes the submit button, program ricketybridge.cgi will be run. If the boxes are filled in with the example shown above, then the standard input will have string

  "NAME1=Groucho&TIME1=1&NAME2=Chico&TIME2=2&NAME3=Harpo&TIME3=6&NAME4=Zeppo&TIME4=10&NAME5=&TIME5=&NAME6=&TIME6="

  getBinding("NAME1")

Writing a reply

To reply to the request, you write, to the standard output, a preamble followed by a blank line and then the content. The preamble for an HTML page should be

  Content-Type: text/html

  System.out.print("Content-Type: text/html\r\n\r\n");

The content is the text of a web page, written in HTML. For example, a page that just says hello would hold text like the following.

  <html>
  <head>
    <title>Hello</title>
  </head>
  <body>
  <p>Hello.</p>
  </body>
  </html>

Placement of the form and the CGI program

To make this work, you will need to do the following.

1. If necessary, create a directory called public_html in your home directory.

2. Put form.html into the public_html directory.

3. Put a script called ricketybridge.cgi in the public_html directory. In the script, write the following, assuming that your main program is in class RicketyBridge.

     #!/bin/sh
     java RicketyBridge
   

   Also put all of your .class files in this directory.

4. Make both your home directory and the public_html directory world-readable. Make form.html and all of the .class files world-readable, and make ricketybridge.cgi world-readable and executable. The following sequence of commands will do that.

     cd ~
     chmod a+rx .
     cd public_html
     chmod a+rx . ricketybridge.cgi
     chmod a+r form.html *.class
     

5. Now use a web browser to visit the following page, where ~user is a tilde followed by your account name.

       http://www.cs.ecu.edu/~user/form.html
     

   Notice that you do not write 'public_html'.

Warning

If you make your home directory world-readable, then anybody can look at your files. A good idea is to have a directory that is not world-readable where you put most of your work. You can find out the status of your files by using command

  ls -l

  chmod o-r f

Keep your programs in a place that is not world-readable. After compiling them, copy the .class files to public_html.

Testing your program before trying the browser

After you have made your program ready for the browser, compile it and run it directly, as you usually would. Create a file, such as httpdata, containing what your program would receive from a form. (For example, try taking the line above and putting it into the file. But remove the quote marks.) Now run your program, with the standard input redirected to that file.

  ricketybridge.cgi <httpdata

Submitting your work

Put all of your files in a directory for this assignment. Submit them as assignment L3. Command

 ~karl/3310/bin/submit L3 *.java