Assignment #3: The Turnpike Reconstruction Problem

This assignment requires you to solve the problem described in Exercise 7.30 (part b). The problem is known as the Turnpike Reconstruction Problem. In the turnpike reconstruction problem, you have a set of points on the (positive) x-axis, with one point always located at position 0. For example, there might be four points located at positions 0, 3, 6, 8. These points define a sequence of distances that separate them. In this case, the sequence of distances is 3, 6, 8, 3, 5, 2. If there are N points, there will be N(N-1)/2 pairs of distances, and some of the distances may appear more than once.

Determining the distances from the points is trivial. Your problem is to determine the points from the distances, which is considerably more challenging. Note that if there is a solution, there will always be a symmetrical solution (for instance, 0, 2, 5, 8 is also a solution above). You only need to determine one solution, if such a solution exists, or signal that there is no solution.

The Basic Algorithm

Here's a handout that describes the ideas in the basic algorithm. I will discuss this in class, so you should make sure you attend.

Java Coding Issues

The easiest way to store the items is to use a Multiset. A Multiset stores items but allows duplicates. Begin by implementing an efficient multiset class, by using a TreeMap (with the values representing counts) as the data member. Your multiset will need the following operations: clear, isEmpty, size, add, contains, remove (which removes one instance, so if there are several duplicates, only one of them is removed), toString, and toArray.

Pseudocode

In addition to main, and various supporting routines (e.g. Math.abs, to compute absolute values), I would recommend writing three routines, as shown below. I've tried to provide comments that explain what the routines do. I've also listed the number of total lines of code in my solution between the braces for each function, not including blank lines and comments. You have three routines below:
  1. solve: The logically public driver
  2. two parameter solveRecursive: The main recursive routine
  3. three parameter solveRecursive: A helper, so that the two-parameter solveRecursive doesn't have the same code twice.


// Driver routine that can be called from main.
// It is passed the set of distances (which is an input parameter).
// If these distances represent a solution, the solution will
// be placed in points, and solve returns true. Otherwise
// solve returns false, and the contents of points is undefined.
// 6 NON BLANK LINES OF CODE
public static boolean solve( Multiset<Integer> dist, Multiset<Integer> points )
{
    points.clear( );          // Initialize points

    // Find the maximum value in dist.

    // Remove this value from dist, and add
    // two entries to points (0, max).

    // Try to place all the remaining points.
    return solveRecursive( dist, points );
}
 

// Recursive routine to place remaining points.
// dist contains the distances.
// The contract of solveRecursive is identical to solve.
// solveRecursive calls the three parameter helper, below
// to handle the identical logic involved in trying to
// place a point at either distMax or pointsMax-distMax.
// 7 NON BLANK LINES OF CODE
public static boolean solveRecursive( Multiset<Integer> dist, Multiset<Integer> points )
{
    // Handle a base case.
    // Hint: What is the most trivial case for which you can return true?

    // find maximum item in dist (distMax),
    // and then find maximum item in points (pointsMax).
    // You will want to try to place a point either at
    // distMax or pointsMax-distMax.

    // Call a helper (solveRecursive, with three parameters) twice.
    // If either returns true, we return true. If both return false
    // we return false.
}

 
// Three parameter helper.
// Attempts to add a new point (pointToAdd) into points.
// If the attempt succeeds, we return true, and points has the final answer.
// Otherwise, we return false, and points is undefined.
// 22 NON BLANK LINES OF CODE
public static boolean solveRecursive( Multiset<Integer> dist, Multiset<Integer> points, int pointToAdd )
{
    // Attempt to use it at location pointToAdd
    // There must be a matching distance for each
    // value in points && the recursive call must succeed.
    // So...

    // Scan through points; at each step, compute
    // a distance from pointsToAdd, and remove it from dist.
    // If the distance is not present, you can return
    // false AFTER undoing all the deletions from dist.

    // If we get here, all distances were present.
    // Add pointToAdd to points, and then make a call to
    // solveRecursive (which one??) to place the remaining points.

    // If the call to solveRecursive returns true, then we return true.
    // Otherwise we return false AFTER removing pointToAdd from
    // points (recall it was added above)
    // and restoring dist by undoing deletions
}