summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-16 20:21:12 -0600
committerHaidong Ji2018-12-16 20:21:12 -0600
commit1d6a57ac37f0c56a7639c1124be5501f699f3027 (patch)
tree922a96bbb6cf6d39aff7d494500f8f0d1956a38f
parent88a15736625e2847d5c479ceabf202ea6be1e75b (diff)
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!
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/closest_distance.py67
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/closest_distanceTest.py64
2 files changed, 131 insertions, 0 deletions
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()