Closest Point, Python3, Need help on finishing the implementation of helper and cp. The purpose of the program is supposed to fulfill the following (the Point and PointSet ADT is what we were given to complete the problem set). They also provided this PDF for guidance. https://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

The Point ADT: A Point will have an x-coordinate and a y-coordinate and will implement the following methods.

__init__(x,y) - initializes the x and y coordinates when the point is created.

dist(self, other) - returns the distance between self and other defined as the maximum of the difference in x-coordinates and the different in y-coordinates. This is sometimes called the max norm.

norm - returns the maximum of the absolute values of the x- and y-coordinates. The norm is the same as the distance from a point to the origin (0,0).

The PointSet ADT: A PointSet will store a collection of points and support the following methods.

add(p) - adds a Point p to the point set.

nn(p) - returns the point in the point set that is closest to Point p. [This could take O(n) time]

cp - returns the pair (tuple) of points that are closest among all pairs of distinct points in the point set. [This should take O(n log n) time].

I believe the next steps to my helper function are: 1. use list comprehension. 2. sort the points within the rectangle according to their y values. 3. Iterate through these y values to find which two are the closest. Remember: this must take O(nlogn) time. Thank you for the help!

My code is below:

class Point: def __init__(self, x, y): self.x = x self.y = y

def dist(self, other): dx = abs(other.x - self.x) dy = abs(other.y - self.y) if dx > dy: return dx else: return dy

def norm(self): x = abs(self.x) y = abs(self.y) if x > y: return x else: return y

class PointSet: def __init__(self, L = []): self.L = L

def add(self, p): #doesn't need to be sorted, just needs to add point p to list L return self.L.extend([p])

def nn(self, p): #returns the point in the pointset that is closest to Point p current_dx = abs(p.x - self.L[0].x) current_dy = abs(p.y - self.L[0].y) current_dz = current_dx + current_dy m = self.L[0] for e in self.L: nxt_dx = abs(p.x - e.x) nxt_dy = abs(p.y - e.y) nxt_dz = nxt_dx + nxt_dy if current_dz > nxt_dz: current_dz = nxt_dz m = e else: continue return m

def cp(self): #returns the tuple of points that are closest among all pairs of distanct points in the PointSet length = len(self.L) if length is not 2: x = sorted(self.L, key = lambda p: p.x) z = self.helper(xsort, ysort) else: return self.L

def helper(self, xsort): def distance(pair): if pair is None: return float('Inf') else: return pair[0].dist(pair[1]) lenx = len(xsort) if lenx == 2: return xsort elif lenx < 2: return None else: median = lenx // 2 left = xsort[:median] right = xsort[median:] nLeft = self.helper(left) nRight = self.helper(right) d = min(distance(nLeft),distance(nRight)) #list comprehension #iterate through y