# Five aligned points and some of the pairwise distances. Infer the relative positions!

Given five points on a straight line such that their pairwise distances are 1,2,4, ..., 14,18,20 (after ordering), find the respective positions of the five points (relative to the furthest point on the left).

-
 What do you want: shortest code? best complexity? – Alexandru Feb 4 '11 at 15:42 Best complexity and generality (number of points, distances, etc.). – wok Feb 4 '11 at 16:13 The problem isn't general: there is one correct answer for the numbers given, but there is more than one answer for other combinations of five points with the first three and last three pairwise distances known. And if you increase the number of points, you will need more known distances to insure a single solution. So I don't think a general solution is possible. – Tyler Feb 5 '11 at 21:38

R

``````prop <- function(num_points, first_distances, last_distances)
{
last_point = max(last_distances)
proposal = c(0, sort(sample(1:(last_point-1), num_points-2)), last_point)
d = sort(dist(proposal))
num_first_distances = length(first_distances)
num_last_distances = length(last_distances)
num_distances = length(d)
if(all(d[1:num_first_distances]==first_distances)&&all(d[(num_distances-num_last_distances+1):num_distances]==last_distances))
{
print(proposal)
return(TRUE)
}
else return(FALSE)
}

while(TRUE)
{
if(prop(5, c(1,2,4), c(14,18,20))) break()
}
``````

Here is the source of the problem and an algorithm with R which I used for inspiration.

-
If you already know the answer it is best to wait a few days before posting it to give others a chance. – Alexandru Feb 4 '11 at 15:41
What is written above is using R. There may be more elegant solutions. – wok Feb 4 '11 at 16:13
Indeed, there are better solutions, since the one above use random trials rather than dynamic programming. – wok Feb 5 '11 at 10:01