CSCI 3310
Summer 2006
Large Programming Assignment 3

Assigned: June 9
Due: June 19, 11:59pm

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 one.

Some support files

Get copies of the following files, containing some things to make your job a little easier.

• rb_support.h
• rb_support.cpp
• http_support.h
• http_support.cpp
• Makefile
• PersonSet.h
• PersonSet.cpp

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. The returned name should not be changed by another module, so mark it const.

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

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

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

-1		if A and B are different persons, and either A walks faster than B, or A and B walk at the same speed and A's name comes alphabetically before B's name,
0		if A and B have identical times and names (and so are the same person),
1		if A and B are different persons, and either A walks slower than B, or A and B walk at the same speed and A's name comes alphabetically after B's name.

That is,

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

The PersonSet class

A PersonSet object is a set of persons. Class PersonSet is provided to you above. It is a persistent data type, providing only operations that leave the object unchanged. Operations work by creating new 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.

hash()

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

equal(t)

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

print()

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

printMems()

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

Const pointers

In C++, if you declare variable p by

  const PersonSet* p;

  const int* p;

  int a, b;
  p = &a;
  p = &b;

  int a = 1;
  p = &a;
  *p = 2;

Since the PersonSet class is persistent, all pointers to PersonSet objects are marked const in the PersonSet implementation. You should do the same. If you need a variable p that points to a PersonSet object, use

  const PersonSet* p;

  PersonSet* p;

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 ('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 pointer to another Plan object representing the rest 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 the plan in a form suitable for textual output. p.printHTML() prints the plan 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 HashTable class

The algorithm requires memoization. Use a hash table for memoization. Only memoize for configurations where the flashlight is on the West side, so that you do not need to keep track of where the flashlight is. As a key, use the set of persons on the West side. (Everybody else is on the East side.) The associated value for key S should be an optimal plan, starting in a configuration where the flashlight and the persons in set S are on the West side.

Write a class HashTable that is suitable for this kind of table. Use the ideas of hash tables, and use chaining to resolve conflicts. (So, at each cell in the array, store a pointer to a linked list.)

It is acceptable to create an array of a fixed size. For example, you can use an array of 1000 pointers, without letting the array grow as the number of things in the table grows.

Be sure to make the table empty when you create it. (There might be space to put things, but there are no entries in the table yet.) Provide methods to insert information and to look up the plan stored with a key. (Just return NULL no such plan is known.) It is not necessary to provide a method to remove something from the table, since you never remove anything from the memoization table.

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 (a HashTable) should be one of the variables in the class.

Provide a method that takes no parameters, and returns an optimal plan for the set of persons given in the constructor.

You will want a helper method that takes two sets, telling 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 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

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, argv[1]. 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 argv[1]

When the argument count (argc) is 1, make your program read from the standard input. Do not ruin interface 1 to do this. Make it work both ways.

When argc is 1, 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 when argc is 1.

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

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 the form.html and ricketybridge.cgi (executable) file into the public_html directory.

3. Make both your home directory and the public_html directory world-readable. Make form.html 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
     

4. 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

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

Memory management

This program uses a persistent PersonSet class, and manual memory management for persistent classes is considerably more difficult than manual memory management for typical ephemeral classes. Persistent class are more often used with programming languages where there is support from a garbage collector.

Do not try to delete anything for this program. Just let all memory leak away, unless you are absolutely sure that the deletion is safe.

Submitting your work

Put all of your files in a directory for this assignment. Before submitting, move any extraneous .h or .cpp files to a different directory. Log into one of the Unix computers in the lab, and change your directory to the directory that contains your assignment. For example, use command

 cd Assignment3

 ~karl/3310/bin/submit L3 *.h *.cpp