From 1d6a57ac37f0c56a7639c1124be5501f699f3027 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Sun, 16 Dec 2018 20:21:12 -0600 Subject: Closest pair done! I thought it wouldn't be this hard after I worked it out in Java first, but once again it was fun and I learned a lot: 1. in all my previous exercises, my Python code performed better than my Java code. This is the first time that my Java code significantly outperforms my Python code: 0.92 seconds versus 7.93 seconds! My Java code did use more than twice the memory. 2. Good re-enforcement of Python list copying concept, versus aliasing. Don't forget the [:] (or [l:r]) magic! 3. list of (num, num) sort by first num by default, with proper tie breaking. To sort on the second num, do list.sort(key=lambda x: x[1]. Cleve use of lambda, and it also does proper tie breaking. 4. I forgot to put this into my Java program comments, that Java code gave me a good practice of comparator versus comparable interfaces, which was very nice. Fun stuff! Curious how much faster C++ program will be. I'll find out!--- .../sources/closest_distance.py | 67 ++++++++++++++++++++++ .../tests/closest_distanceTest.py | 64 +++++++++++++++++++++ 2 files changed, 131 insertions(+) create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/closest_distanceTest.py diff --git a/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py b/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py new file mode 100644 index 0000000..d394f2d --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py @@ -0,0 +1,67 @@ +# Uses python3 +import sys +import math + + +def distance(p1, p2): +# return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) + return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 + + +def baseCaseMinDistance(P, low, high): + if high - low == 1: + return distance(P[low], P[high]) + if high - low == 2: + d1 = distance(P[low], P[low + 1]) + d2 = distance(P[low], P[high]) + d3 = distance(P[high], P[low + 1]) + return min(d1, d2, d3) + if high - low == 3: + d1 = distance(P[low], P[low + 1]) + d2 = distance(P[low], P[low + 2]) + d3 = distance(P[low], P[high]) + d4 = distance(P[low + 1], P[low + 2]) + d5 = distance(P[low + 1], P[high]) + d6 = distance(P[low + 2], P[high]) + return min(d1, d2, d3, d4, d5, d6) + + +def dPrimeDistance(shadedP): + minDistance = float('inf') + for i in range(len(shadedP)): + for j in range(1, 6): + if i + j < len(shadedP): + tempDistance = distance(shadedP[i], shadedP[i + j]) + minDistance = min(tempDistance, minDistance) + return minDistance + + +def minimalDistance(P, low, high): + if high - low <= 3: + return baseCaseMinDistance(P, low, high) + mid = int(low + (high - low) / 2) + midX = P[mid][0] + d1 = minimalDistance(P, low, mid - 1) + d2 = minimalDistance(P, mid, high) + d = min(d1, d2) + shadedP = [x for x in P[low:high] if abs(x[0] - midX) <= d] + shadedP.sort(key=lambda x: x[1]) + dPrime = dPrimeDistance(shadedP) + return min(d, dPrime) + + +def minDistance(X, Y): + P = [] + for x, y in zip(X, Y): + P.append((x, y)) + P.sort() + return math.sqrt(minimalDistance(P, 0, len(P) - 1)) + + +if __name__ == '__main__': + input = sys.stdin.read() + data = list(map(int, input.split())) + n = data[0] + x = data[1::2] + y = data[2::2] + print("{0:.9f}".format(minDistance(x, y))) diff --git a/AlgoDesignAndTechniqueEdxPython/tests/closest_distanceTest.py b/AlgoDesignAndTechniqueEdxPython/tests/closest_distanceTest.py new file mode 100644 index 0000000..b3391a7 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/tests/closest_distanceTest.py @@ -0,0 +1,64 @@ +''' +Created on Dec 16, 2018 + +@author: haidong +''' +import unittest + +from sources.closest_distance import distance, minDistance + + +class Test(unittest.TestCase): + +# def testDistance(self): +# p1 = (0, 0) +# p2 = (1, 1) +# result = 1.414214 +# self.assertAlmostEqual(result, distance(p1, p2), places=6) + + def testSortPointsArray(self): + p = [(4, 4), (-2, -2), (-3, -4), (-1, 3), (2, 3), (-4, 0), (1, 1), (-1, -1), (3, -1), (-4, 2), (-2, 4)] + p.sort() + self.assertEqual(-4, p[0][0]) + self.assertEqual(0, p[0][1]) + + p.sort(key=lambda x: x[1]) + self.assertEqual(-4, p[0][1]) + self.assertEqual(-3, p[0][0]) + self.assertEqual(4, p[10][1]) + self.assertEqual(4, p[10][0]) + + def testMinDistance(self): + x = [0, 3] + y = [0, 4] + result = 5.0 + self.assertAlmostEqual(result, minDistance(x, y)) + + def testMinDistance1(self): + x = [0, 3, 5] + y = [0, 4, 6] + result = 2.828427 + self.assertAlmostEqual(result, minDistance(x, y), places=6) + + def testMinDistance2(self): + x = [7, 1, 4, 7] + y = [7, 100, 8, 7] + result = 0.0 + self.assertAlmostEqual(result, minDistance(x, y), places=6) + + def testMinDistance3(self): + x = [4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2] + y = [4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4] + result = 1.414214 + self.assertAlmostEqual(result, minDistance(x, y), places=6) + + def testMinDistance4(self): + x = [-2, -3, -1, 2, -4, 1, -1] + y = [-2, -4, 3, 3, 0, 1, -1] + result = 1.414214 + self.assertAlmostEqual(result, minDistance(x, y), places=6) + + +if __name__ == "__main__": + #import sys;sys.argv = ['', 'Test.testName'] + unittest.main() -- cgit v1.2.3