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.
// 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
}