Python shortest distance points

Question

Write a function called dist that takes in two points (so two lists of two elements each), and computes the distance between them. Make sure this works on the example below before proceeding to the next step.
Use dist in a nested loop inside shortestDist to compare each element of the list of points with every element in the list after it. So, basically, find the shortest distance between points in a list.

Here's what I have so far:

        sample= [[45, -99], [24, 83], [-48, -68], [-97, 99], [-8, -77], [-2, 50], [44, 41], [-48, -58], [-1, 53], [14, 86], [31, 94], [12, -91], [33, 50], [82, 72], [83, -90], [10, 78], [7, -22], [90, -88], [-21, 5], [6, 23]]

        def dist(p0, p1):
            return (((p0[0] - p1[0])**2) + ((p0[1] - p1[1])**2))**.5


        def shortestDist(sample):
            distances = []
            for i in range(len(sample)-1):
                for j in range(i+1, len(sample)):
                    distances += [dist(sample[i],sample[j])]
            return(min(distances))

That finds the distance alright between two points. I just need some help figuring out how to start writing shortestDist to compare all points and keep track of the shortest distance. UPDATE: The error was resolved and I'm good to go now. Thank you to everyone for their assistance!

Answer 1

This should do the job

def shortestDist(points):
        sh = float("inf")
        for i in range(1, len(points)):
                d = dist(points[i-1], points[i])
                if d < sh:
                        sh = d
        return sh

Answer 2

This is a fully functioning example based on a list of points.

points = [(1,5), (5,8), (8,1), (9,5)]

def euclideanDistance(coordinate1, coordinate2):
    return pow(pow(coordinate1[0] - coordinate2[0], 2) + pow(coordinate1[1] - coordinate2[1], 2), .5)

distances = []
for i in range(len(points)-1):
    for j in range(i+1, len(points)):
        distances += [euclideanDistance(points[i],points[j])]
print min(distances)

Answer 3

I think code below would move you into right direction:

def shortestDist(points):
    min_dist = None
    while points:
        p1, p2 = points.pop()
        dist = dist(p1, p2)
        if min_dist is None:
            min_dist = dist
        else:
            min_dist = dist  if dist < min_dist else min_dist

Let me know if you don't understand some parts of code and i will give more explanations to it.

Good luck!

Answer 4

First, you might want to use tuples rather than lists. Either way will work, but given the values "x" and "y" are different, albeit both "numbers" (doubles,int...), a tuple is typically used.

You can pass in the points like:

dist((0,1), (2,3))

And they can be accessed like you would access a list:

p0[0] # access "x" in point 0
p0[1] # access "y" in point 0

As for writing shortestDistance, you'll want to take in a list of the tuples from above: e.g. [(0,1),(2,4),(3,2),(1,3)]

So something like this for the def:

def shortestDist(listOfPoints)

Then for each point you can compare it to each point after it using the following, which stores it in a dictionary.

 currentIndex = 0
 pointDict = {}
 for point in listOfPoints:
    currentPoint = point
    for i in range(currentIndex,len(listOfPoints)):
        pointDict[currentPoint] = dist(currentPoint,listOfPoints[i])

That should get you started. It assumes that the points are not duplicated.

Answer 5

def solve(self, coordinates):
    m = float('inf')
    for i in range(len(coordinates)-1):
        for j in range(i+1,len(coordinates)):
            z = ((coordinates[i][0]-coordinates[j][0])**2)+((coordinates[i][1]-coordinates[j][1])**2)
            m = min(m,z)
    return m

Iterate through all the possible coordinates and find the distances then compare the with minimum counter in this case variable m.

We can also sort the coordinates according to the the x coordinates and y coordinates the find distances separately and then finally compare the min of x and min of y, so as to reduce the time complexity.

1. To sort with respect to x:

   coordinates.sort(key = lambda x:x[0])

2. To sort with respect to y:

   coordinates.sort(key = lambda x:x[1])