Meeting Point problem from interviewstreet.com

Question

I am trying to solve the "Meeting Point" problem from interviewstreet.com:

There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time. eg: (x,y) can be reached from (x-1,y+1) in a single unit of time. Find a common meeting place which minimises the sum of the travel times of all the persons.

For example, if the input is:

4
0 1
2 5
3 1 
4 0

the output must be 8. Here's my solution:

def pos(a):
    if a<0:
        return -a
    else:
        return a
n = long(raw_input())
min =0
inputs = []
for i in range(n):
    temp = raw_input().split()
    inputs.append([long(temp[0]),long(temp[1])])
x = inputs[0][0]
y = inputs[0][1]
for i in range(n):
    min += max(pos(x-inputs[i][0]),pos(y-inputs[i][1]))
for i in range(1,n):
    x = inputs[i][0]
    y = inputs[i][1]
    temp =0
    for j in range(n):
        temp += max(pos(x-inputs[j][0]),pos(y-inputs[j][1]))
    if min>temp:
        min =temp
print min

I know I am brute forcing the answer but I couldn't find an algorithm that fits the problem. I have been thinking about the problem statement for a while yet I don't have any clue how to optimize it. If any of you could help me with the code in Python or C.

Answer 1

1. Comments on your code

1. Your function pos computes the absolute value of a, and is already built into Python under the name abs.

2. You'd benefit from structuring your code into functions. For example, the expression max(pos(x-inputs[j][0]),pos(y-inputs[j][1])) appears twice. Your code would be clearer if you'd written a function with a docstring, for example:

   def distance(A, B):
       """Return the Chebyshev distance from A to B."""
       return max(abs(a - b) for a, b in zip(A, B))
   

   ("Chebyshev distance" is a name that mathematicians give to this function.)

3. You have code near the start for finding the total distance if the meeting point is at house number 0, but then you repeat that code inside a loop over the other meeting points. This seems like a waste. I guess you're doing this because you need an initial value for min.

   But instead you could use Python's built-in function min, which avoids the need for a special case to get the initial value. This needs a bit of re-organization, but it comes out quite simple:

   def total_distance(Q, points):
       """
       Return the total distance from `Q` to each of the points in the
       sequence `points`.
       """
       return sum(distance(Q, P) for P in points)
   
   def min_total_distance(points):
       """
       Find that point that minimizes the total distance to the
       other points, and return the minimum total distance.
       """
       return min(total_distance(P, points) for P in points)
   

   If you are a fan of hard-to-read code, then you could write the entire computation in a single expression:

   min(sum(max(abs(a - b) for a, b in zip(P, Q)) for P in points) for Q in points)
   

2. A better algorithm

Your algorithm is Θ(n²): it has to compute the distance between every pair of houses. In the interviewstreet.com version of the problem, they say that n ≤ 10⁵ so your approach takes up to 10¹⁰ distance computations. That's not utterly intractable, but it's not going to be doable within the time limits at interviewstreet.com.

So is there an approach which scales better as n becomes large?

Well, if we weren't restricted to the meeting point being one of the houses, then the best meeting point would be the geometric median. The geometric median is hard to compute, but it can be approximated by an iterative procedure due to Endre Weiszfeld:

def median_approx(P, points):
    """
    Return a new approximation to the geometric median of `points` by
    applying one iteration of Weiszfeld's algorithm to the old
    appromixation P.
    """
    W = x = y = 0.0
    for Q in points:
        d = distance(P, Q)
        if d != 0:
            w = 1.0 / d
            W += w
            x += Q[0] * w
            y += Q[1] * w
    return x / W, y / W

def geometric_median(points, epsilon):
    """
    Return an approximation to the geometric median for `points`.
    Start with the centroid and apply Weiszfeld's algorithm until the
    distance between steps is less than `epsilon`.
    """
    n = float(len(points))
    P = tuple(sum(P[i] for P in points) / n for i in range(2))
    while True:
        Q = median_approx(P, points)
        if distance(P, Q) < epsilon:
            return Q
        P = Q

Unfortunately, for this problem, the meeting point must be one of the original points, so the geometric median doesn't solve it.

However, if the set of points is fairly random (that is, not chosen adversarially), then the best meeting point seems likely to be one of the closest points in the set to the geometric median.

So we have a chance of finding the best meeting point by taking a heuristic approach: compute an approximation G to the geometric median, sort the points by their distance from G, look at the closest k points, and pick the best one. If we choose ε to be small enough, and k to be large enough (but not so large that the computation takes too long), then we'll get the right answer.

from heapq import nsmallest

def best_meeting_point(points, epsilon, k):
    """
    Return (a guess at) the point in `points` that minimizes the sum
    of distances to the other points, by computing an approximation
    `G` to the geometric median (using `epsilon`) and then taking the
    best point among the closest `k` points to `G`.
    """
    G = geometric_median(points, epsilon)
    closest_k = nsmallest(k, points, key = lambda P: distance(G, P))
    return min(closest_k, key = lambda P: total_distance(P, points))

This runs in O(jn + kn) where j iterations are needed for Weiszfeld's algorithm to converge. j doesn't grow proportionally with n (it depends on ε and on the magnitude of the coordinates in the input), so this is o(n²).

But beware: if the points are chosen adversarially, I think k might have to grow like Ω(n). I don't know an efficient algorithm for finding the answer in this case. So whether you can use this algorithm to pass the challenge at interviewstreet.com depends on how nice their test cases are. Good luck!