When we were on the Falcon project, the client had been using the "Closest Points" problem as one of their programming exercises in order to evaluate and vet new engineers wishing to join the project. The "Closest Points" problem is, given a set of points in a plane, find the two points that are closest to one another. In particular, the engineering candidate was to use the "Divide and Conquer" algorithm as the mechanism for solving the "Closest Points" problem. However, the client was not having success at getting suitable implementations of the solution. In addition, they were also convinced that such a problem could not be solved using TDD methods. DJ Daugherty took the "can't solve using TDD" as a challenge and threw the problem at the Falcon folks to see what we would do. A few of us took the time to tackle it. This is my solution.
Algorithms, especially those that are mathematical and/or data-driven, quickly expose the dilemmas presented by typical TDD philosophies, and especially those that are more quixotic in nature. However, when applied pragmatically and with proper forethought, TDD can be used to drive algorithm-based solutions quite well, with the result being much more sensible and reliable implementations.
This talk explores four solution types to the "Closest Points" problem:
- Permutation Search - A purely naive matching of all permutations with ordering (even though ordering doesn't really matter). This solution is the easiest to test-drive without knowing any algorithm. However, the permutation search is O(n!), making it the worst possible solution, and impractical for real-world use.
- Combination Search - A better naive matching of all combination regardless of ordering. This solution can be test-driven, provided the developer observes that the checking of points does not depend on order. The combination search is O(n!)/2 (i.e., "n choose 2"), making it the second worst possible solution, and impractical for real-world use.
- Plane Sweep - An efficient matching of points where the points are ordered by their x position and then the plane is swept, looking for best matches in a sliding window whose size is based on the best match found so far. This solution can be test-driven provided the developer has worked out the algorithm a priori (i.e., the critical operations of the algorithm are test-driven, and then the integration of those operations is test-driven). This method is O(n log n), and is well-suited for real-world use.
- Divide and Conquer - An efficient matching of points where the points are ordered by their x position and then recursively bisected into smaller regions until the point set is sufficiently small to easily search. This solution can be test-driven provided the developer has worked out the algorithm a priori (i.e., the critical operations of the algorithm are test-driven, and then the integration of those operations is test-driven). This method is O(n log n), and is well-suited for real-world use.
A live demonstration of my solution developed in Swift on macOS will be given.
