1. Comments on your code
pos computes the absolute value of
a, and is already built into Python under the name
You'd benefit from structuring your code into functions. For example, the expression
max(pos(x-inputs[j]),pos(y-inputs[j])) 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.)
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
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
return sum(distance(Q, P) for P in 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 Θ(n2): it has to compute the distance between every pair of houses. In the interviewstreet.com version of the problem, they say that n ≤ 105 so your approach takes up to 1010 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
W = x = y = 0.0
for Q in points:
d = distance(P, Q)
if d != 0:
w = 1.0 / d
W += w
x += Q * w
y += Q * 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))
Q = median_approx(P, points)
if distance(P, Q) < epsilon:
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(n2).
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!