Computer Science 3675
Section 001
Fall 2008
Programming Assignment 3

Overview of assignment

Many of you solved the Rickety Bridge problem in Java, so it seems appropriate to try the same thing in a higher-order functional style.

There is a group of people who need to cross a rickety bridge from East to West. Because the bridge is rickety, only one or two people can cross the bridge at a time. It is night, and anyone crossing the bridge needs to carry a flashlight. But there is only one flashlight. So two people walk across with the flashlight and one walks back. This continues until they have all crossed.

The people walk at different speeds. When two people cross together, they walk at the speed of the slower person.

The problem is to determine how they should cross so that they are all across in the shortest possible time.

Specifics

The input contains one line for each person containing the person's name and an integer indicating how many minutes that person takes to cross the bridge. The program should show a plan for crossing the bridge by showing the people and the flashlight after each crossing, along with the total time remaining.

For example, if the input is

Grouch 1
Chico  2
Zeppo  5
Harpo  10

Time  East side                            | West side

[ 17] Flashlight Groucho Chico Zeppo Harpo | 
[ 15] Zeppo Harpo                          | Flashlight Groucho Chico
[ 14] Flashlight Groucho Zeppo Harpo       | Chico
[  4] Groucho                              | Flashlight Chico Zeppo Harpo
[  2] Flashlight Groucho Chico             | Zeppo Harpo
[  0]                                      | Flashlight Groucho Chico Zeppo Harpo

There is a discussion of an algorithm to solve this problem below. If you have not seen the problem, it is helpful to ask yourself at this point how you would find the best way for everyone to cross. Be sure that it works for the example shown. Can you prove that your algorithm is correct?

Remark

At first this will look like a difficult program. But I have broken it down into small steps. If you work the steps, you will find it is not bad at all. But still, expect this to take some time. Plan to get it done early.

Libraries

The description below uses some functions from libraries. If you import the following libraries, then you will be able to use everything mentioned.

  Import "collect/string".
  Import "collect/memoize".
  Import "collect/sort".

Representing a person

A simple way to represent a person is to use a pair holding an integer (the crossing time) and a string (the person's name). It will be convenient to put the crossing time first. For example, represent Chico by the ordered pair (2, "Chico").

It is convenient to make a name for the type of a person. In a Cinnameg program, write

  Abbrev Person = (Integer, String).

Write a function to get a person's walking time and name. Give the type of each and a contract by writing an expectation for each. Also include an example. Here is how the walking-time function might look.

  Expect walkTime: Person -> Integer
    %: walkTime(p) is the time that person p takes
    %: to walk across the bridge.
  %Expect

  Example walkTime(1, "Groucho") = 1.

  Define walkTime(t,?) = t.

Getting the input

Read the desciptions of the people from the standard input. Cinnameg expression !bxStdin gives you the entire standard input as a string. For now, imagine that the input will be given as a string. (That is convenient for testing, since your functions that do reading are not strictly tied to the standard input.)

Write a function that converts a single line to a person. For example, if it is called stringToPerson, you should find that stringToPerson("Groucho 1") = (1, "Groucho"). The easiest way to do that is to use pattern matching, where the compiler is asked to solve an equation. I will write that for you. Pattern theString(s) matches a string (up to white space) and makes s name that string. Pattern theInteger(n) matches a (decimal) integer and makes n be that integer. Both theString(s) and theInteger(n) will skip over white space.

  Expect stringToPerson: String -> Person
    %: stringToPerson(line) yields the person described by line.
  %Expect

  Example stringToPerson("Groucho 1") = (1, "Groucho").

  Define stringToPerson(str) = (time, name) |
    Match theString(name) ++ theInteger(time) = str.
  %Define

Now write a function that takes the entire standard input and converts into a list of persons. You can use breakIntoLines to cut the input string into a list of lines, then do a map to convert from a list of lines to a list of persons. Include an example that uses a string as a standin for the standard input.

  Example [(1, "Groucho"), (2, "Chico")] = stringToPersonList(str) |
    Let str =
      |"Groucho 1
      |"Chico 2
    %Let
  %Example

Showing a list of persons

You will also want to be able to convert an entire list or persons to a string. A convenient function from the library is separateBy, where ["abc", "def", "ghi"] `separateBy` " " = "abc def ghi". So separateBy concatenates the strings in a list together, with a given string between them. You want to convert a list of persons to a string, not a list of strings to a string. So, for example, personListToString [(1, "Groucho"), (2, "Chico")] = "Grouch Chico". Notice that converting a list of persons to a list of names is a map. So write this function using a map.

Testing what you have

Do not try to write everything and then test it. You have written examples with your functions. Compile what you have and run it. The examples will be tested.

Configurations

A configuration tells who is on each side of the bridge and where the flashlight is. You can create an enumerated type for the flashlight side.

  Type Side = east | west.

  Abbrev Configuration = (Side, [Person], [Person]).

  Abbrev ConfigurationWithCost = (Integer, Configuration).

Solutions

A solution to a particular Rickety Bridge problem is a list of configuration-with-costs. For example, the solution to the input shown above would be

  [(17, (east, [(1, "Groucho"), (2, "Chico"), (5, "Zeppo"), (10, "Harpo")], [])),
   (15, (west, [(5, "Zeppo"), (10, "Harpo")], [(1, "Groucho"), (2, "Chico")])),
   (14, (east, [(1, "Groucho"), (5, "Zeppo"), (10, "Harpo")], [(2, "Chico")])),
   (4,  (west, [(1, "Groucho")], [(2, "Chico"), (5, "Zeppo"), (10, "Harpo")])),
   (2,  (east, [(1, "Groucho"), (2, "Chico")], [(5, "Zeppo"), (10, "Harpo")])),
   (0,  (west, [], [(1, "Groucho"), (2, "Chico"), (5, "Zeppo"), (10, "Harpo")]))]

  Abbrev Solution = [ConfigurationWithCost].

Some useful functions

You will find the following functions useful. Write them.

1. allPairs(x) produces a list of all pairs of members of list x, preserving order. For example, allPairs([a,b,c,d]) = [(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)].

2. insert v x inserts v into list x, preserving order. When applied to a list of integers, insert 5 [2,4,6,8] = [2,4,5,6,8]. You will want to insert a person into a list of persons. A person is represented by a list of pairs, and pairs are ordered lexicographically. For example, (1, "Groucho") < (2, "Chico") because 1 < 2. You will want your lists sorted by walking time. That is why it is convenient to put the time first in the ordered pair.

   If you prefer, you can invent a binary operator that performs this kind of insertion. If the binary operator is called +>, then you would find that [2,4,6,8] +> 5 = [2,4,5,6,8]. To do that, create the operator by giving a declaration

     Operator +>(+).
   

   Then define +> by cases

     Define
       case [] +> x = [x]
       ...
     %Define
   

3. You will probably find it convenient to have a function that takes a solution and returns the time that the solution takes (found in the first member of the solution.) Write that.

4. You will need to be able to compare two solutions to determine which is better (has a lower cost). Write a function betterSolution where betterSolution(s1,s2) yields s1 if s1 has a lower cost than s2, and yields s2 otherwise.

5. It will be convenient to have a function that finds the best solution in a nonempty list of solutions. That is just a fold. What should the fold start with? What function do you use to combine the current best with the next one in the list?

6. Write a higher order function bestOver of type

     Expect bestOver: [<a>] -> (<a> -> Solution) -> Solution.
   

   where bestOver [a,b,c] f produces the best solution in list [f(a), f(b), f(c)]. Notice that f(a) must be a Solution. The definition should be one easy line.

An algorithm

Your algorithm to solve the Rickety Bridge problem will be recursive. So it will not necessarily start in a configuration where everybody is on the East side of the bridge. It will be given a configuration, and must find a solution starting at that configuration.

Write a function that computes the best solution, starting at a given configuration. It will have type Configuration -> Solution.

1. If nobody is on the East side of the bridge, you are done. But what does the Solution look like? For example, suppose that the solution is supposed to start in configuration (west, [], [(1, "Groucho"), (2, "Chico")]). Remember that the solution must show each configuration that it encounters. How many configurations are there?

2. If the flashlight is on the West side of the bridge, then one person will carry it back to the East side. It can be shown that it is always a good idea to choose the fastest person. Since the lists are kept in sorted order with shorter walking times first, the fastest person is at the beginning of the list. So move the fastest person across to the East side and get the best solution from there. What does the entire solution look like?

   Be careful to remember that the time (or cost) that you put into the ConfigurationWithCost is the total amount of remaining time, not just the time for this step. So you will need to see how much the rest of the solution costs. Do not compute the rest of the solution twice. Recursion is an amplifier. If you do a good thing, recursion amplifies it and makes it very good. If you do a bad thing, such as computing the rest of the solution twice, recursion amplifies it and makes it very bad.

   You might find notation E | S convenient. It says to compute the value of expression E after doing statement S. For example, expression

      x + 3x*x + y |
       Let x = 20.
       Let y = 3.
   

   has value 623.

3. If the flashlight is on the East side and there are fewer than three people on the East side, then everybody on the East side walks across, and the solution is done. You will probably find it convenient to have a case for one person and a case for two.

4. Suppose that the flashlight is on the East side and there are three or more people on the East side. Then two people should walk across together. But it is not clear which two people will lead to the best solution. So use the shop-around principle. Try all pairs of people and select that pair that leads to the best solution. Put another way,

   The best solution is the best, over all pairs of persons on the East side of the bridge, found by moving that pair across the bridge and continuing from there.

   Use the bestOver and allPairs functions. You will need a function that takes a given pair of persons and produces the solution that you get by choosing that pair to walk across together. This case should be short and simple. You might find operator -/ useful to remove a person from a list. Again, be sure to remember that the cost that you put into the first ConfigurationWithCost is the total remaining time, not just the time required for the first pair to walk across.

  case ricketyBridgeSolve((=west), e, p::ps) = 

  case ricketyBridgeSolve(west, e, p::ps) = 

Converting a solution to a string

Write a function that converts a configurationWithCost to a string, in a form suitable for including in the output. Just concatenate the parts together. To make things line up nicely, you can pad a string to a given size using operators $$ or `leftin`. For example, "abc" `leftin` 5 = "abc ", where two spaces have been added to make a total of five characters.

Write a function that converts a solution to a string. The string produced should be exactly what you want to show in the end, including line breaks. You will probably find separateBy useful again.

Making the program run

Finally, add a short Execute block. It should

1. Get the list of persons from the standard input. The contents of the standard input (a string) is !bxStdin. After you convert it to a list of persons, you will want to sort it into ascending order by walking time. Just use function sort.

2. Compute the solution, starting with the flashlight and all of the people on the East side of the bridge.

3. Convert the solution to a string and display the string on the standard output.

Make sure the program works.

Memoization and dynamic programming

Even if you are careful to avoid computing the same thing more than once in the above algorithm, you will find that you still do. The problem is that different branches in the recursion will need to find the same subsolution. The amplification property of recursion will amplify that too, and make the algorithm very slow for large numbers of persons.

A standard way to fix that problem is to write down answers that you have found. For example, you create a table whose keys are configurations. With each configuration you store the best solution for that configuration. Any time you need to find the best solution, you first check whether you already know the answer for that one by looking in the table. If not, then you compute it and add it to the table for the next time it is needed.

This kind of thing is so common that it seems it would be useful to have a function transformer that takes a function and transforms it into one that memoizes its answers in a table. Cinnameg provides such a function, called memoize. Definition

  Define fmem = memoize {=>} f.

You need to take care using memoize with recursive functions. When the recursive function wants to call itself, it should now call the memoized version of itself. Otherwise, it is not taking advantage of the table.

Rename your function that computes the best solution. But only change the name on the left-hand side of each equation. Do not change the name in the recursive calls. Create a memoizing version using the old name. So now you have something like the following.

Expect 
  ricketyBridgeSolution: Configuration -> Solution
    %: This is the same as ricketyBridgeSolve but
    %: it memoizes.
    ;

  ricketyBridgeSolve: Configuration -> Solution
    %:...
%Expect

Example ...

Define ricketyBridgeSolution = memoize {=>} ricketyBridgeSolve.

Define 
  case ricketyBridgeSolve(s, [], w) = ...
  case ricketyBridgeSolve...
%Define

Now test the modified program.

Notes

I expect to see an Expect declaration with a documentation comment for each function. There should be an example for each function.

Documentation comments and examples are development tools. As you do each function, write a comment and at least one example for it. Do not add comments and examples only after the program is working. That approach completely misses the point.

This is an exercise in functional programming. Imperative aspects must be kept to a minimum. Make the Execute block at the end very short. It should just get the input, get the solution and display the solution. There should be no loops. There should be no Relets or Redefines. Do the work with functions that just take parameters and produce answers.

Submitting your work

Please call your program ricketybridge.cmg. Submit it using the following command on one of the Linux machines such as login.cs.ecu.edu.

  ~abrahamsonk/3675/bin/submit 3 ricketybridge.cmg