Program #9: The Turnpike Reconstruction Problem

This assignment requires you to solve the problem described in Exercise 8.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.

C++ Coding Issues

The easiest way to store the items is to use multisets. Recall that a multiset is like a set, except that duplicates are allowed. Clearly duplicates are needed for the distance set. It's not obvious that they are needed for the point set, but using them allows the solution to have points on top of each other. The most important thing about a multiset is that there are two versions of erase. If you pass erase an iterator, it will remove the object the iterator is looking at. If you pass erase an object, it will remove ALL occurrences of the object, which is not what you want! So be careful. You may want to write a function called removeOne that will remove one occurence of the object (by calling find to get an iterator).

Also, you will need the logical equivalent of findMax and deleteMax. You would expect back and pop_back to work, but they are not defined. Instead, you can write routines (note that the parameter to erase is an iterator):

template <class Object>
const Object & findMax( const multiset<Object> & m )
{
return *(--m.end( ) );
}

template <class Object>
void deleteMax( multiset<Object> & m )
{
m.erase( --m.end( ) );
}

Pseudocode

In addition to main, and various supporting routines (e.g. 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:

solve: The logically public driver
two parameter solveRecursive: The main recursive routine
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.
// 14 NON BLANK LINES OF CODE
bool solve( const multiset<int> & dist, multiset<int> & points )
{
points.clear( ); // Initialize points
multiset<int> d = dist; // Make a one-time copy of dist

    // Find the two maximum values in dist.
    // Make sure their difference is also in dist.
    // If not, return false.

// Otherwise, remove these three values from dist, and add
// three entries to points (0, max#2, max#1).

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

// Recursive routine to place remaining points.
// dist contains the distances. It is passed by copy so
// we can make changes to the copy (see EXTRA CREDIT).
// 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.
// 6 NON BLANK LINES OF CODE
bool solveRecursive( multiset<int> dist, multiset<int> & 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.
// See below for EXTRA CREDIT.
// 14 NON BLANK LINES OF CODE
bool solveRecursive( multiset<int> dist, multiset<int> & 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.

    // 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.
    // Other wise we return false AFTER removing pointToAdd from
    // points (recall it was added above). Be careful which erase
    // you use.
}

Extra Credit

Making copies of the multiset (i.e., using call-by-value) in the solveRecursive routines is expensive. It would be more efficient to pass the multisets by reference. This means that prior to returning false, the three parameter solveRecursive has to put back elements of dist that it removed in the course of searching for a solution. Implement this improvement. You will need to keep track of what was removed from dist (probably in another multiset), and then reinsert it prior to returning.

Due Date

This program is due on Tuesday, November 30. I will provide some test cases ranging from trivial to complicated. Some cases will not have a solution, and others will. Warning: Start early, this is not alot of code, but what's there is considerably more tricky than previous assignments.