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:

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
        return a
n = long(raw_input())
min =0
inputs = []
for i in range(n):
    temp = raw_input().split()
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.

  • \$\begingroup\$ Dont have an idea for a fancy algorithm, but on the code: Instead of your pos function, you can use math.fabs() and try to use list comprehensions. for i in range(n): min += max(pos(x-inputs[i][0]),pos(y-inputs[i][1])) would become something like min = sum([max(pos(x-inputs[i][0]),pos(y-inputs[i][1])) for i in range(n)]) \$\endgroup\$ Dec 20 '12 at 9:55
  • \$\begingroup\$ "an infinite integer grid" And just what it that? Can we assume that people live in one big square of x*y cells? Or do they live "anywhere"? Are there empty lots? The specification is too poorly worded to give an answer. If you just start to blindly code away without asking such questions, you aren't going to perform well on an interview. \$\endgroup\$
    – Lundin
    Dec 20 '12 at 12:35

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^2)\$: it has to compute the distance between every pair of houses. In the interviewstreet.com version of the problem, they say that \$n ≤ 10^5\$ so your approach takes up to \$10^{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^2)\$.

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!

  • \$\begingroup\$ i have a doubt the median is the best place if literal distance between the points is concern or sum of positive values of difference between x coordinates and y coordinates is taken but the distance considered is neither it is the max value of difference between x coordinates or y coordinates which is not necessarily proportional to literal distance between the points \$\endgroup\$
    – perpetual
    Dec 20 '12 at 21:12
  • \$\begingroup\$ You can compute a geometric median for any metric, not only for the Euclidean metric. \$\endgroup\$ Dec 20 '12 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.