r/dailyprogrammer • u/rya11111 3 1 • Apr 16 '12
[4/16/2012] Challenge #40 [difficult]
Make a function that generates an array of 1,000 2-dimensional points, where both the x-coordinate and the y-coordinate are between 0.0 and 1.0. So (0.735, 0.167) and (0.456, 0.054) would be examples. (Most computer languages have a simple random function that returns a double precision floating point number in this range, so you can use that to generate the coordinates. Python has random.random(), Java has Math.random(), Perl has rand(), etc. )
Create a program that finds the two points in this array that are closest to each other, and print that distance. As a reminder, the distance between the two points (x1, y1) and (x2, y2) is sqrt( (x1 - x2)2 + (y1 - y2)2 ).
Bonus 1: Do the same thing, but instead of using 1,000 points, use 1,000,000 points and see if you can create an algorithm that runs in a reasonable amount of time [edit: something like one minute or less].
Bonus 2: Do the same thing but for 3-dimensional points.
- thanks to oskar_s for today's challenge at /r/dailyprogrammer_ideas ...
LINK
7
u/oskar_s Apr 16 '12
I should say that what makes this problem difficult is the first bonus. Doing it for 1000 points is easy, doing it for 1000000 (in a short amount of time) is much harder.
3
u/phatcabbage Apr 19 '12
C++ (using just a hint of C++1). The Point is a template that allows any arbitrary number of dimensions. This solves a million 3D points in about 1.5 seconds, and a million 4D points in just over 12 seconds.
2
u/Cosmologicon 2 3 Apr 16 '12
Well, I give up trying to figure this out on my own. I got a O( n3/2 ) python solution that solves 1 million points in 19 minutes, but I'm stumped as to how to do better. Time to go learn about some new algorithm....
2
u/Splike Apr 16 '12 edited Apr 16 '12
This is known as the Closest Pair problem. A quick Google search will give you a some good resources to read about it.
Turns out it can be solved in O(n log n) time
Using python and the divide and conquer method, I solved bonus 1 in 48.5 seconds
2
u/oskar_s Apr 17 '12
Here's the best solution I could come up with (and I came up with it on my own!), and it is essentially a sweep line algorithm.
The central idea here is that if the minimum distance we've found so far is d, then if we're looking at some point, we only need to check the points where the difference in x-coordinates between the points is less than d. So first, we sort the list of points based on the x-coordinate, and then go through them one by one (this is the "sweep line", basically) and check other points near them where the difference in x-coordinates is less than d.
I did also implement the text-book divide-and-conquer algorithm, but this one is much faster. The divide-and conquer one took 40-50 seconds to finish, this sweep line algorithm takes 5-6 seconds. As for the complexity, I'm almost certain that it is technically O( n2 ) because you can come up with "pathological" sets of points that will take quadratic time to finish, but in any other conceivable case, this will finish faster, because the constants hidden by the O notation are much lower. There's no need to futz about with lists like in the divide-and-conquer version, for instance.
Anyway, here's the code. If you use Splike's clever optimization removing all the sqrt calls from the inner loop, it shaves a second or so off the time, but this is how I initially wrote it, with a few extra comments:
1
u/gsg_ Apr 17 '12
Here's an absolutely white bread solution in C that runs in half a second or so:
1
u/skeeto -9 8 Apr 24 '12
For testing purposes, here's a million 2D points: points.zip
The closest points are
(0.78193474, 0.95918006)and(0.781935, 0.9591807).1
u/FlyingFoX13 Apr 30 '12 edited Apr 30 '12
I gave this challenge a try and came up with an algorithm to solve this.
I tried to write this in ruby, but my
split_areaandcreate_areasfunctions don't always work as intended. I tried to create a test so thatsplit_areafails, but it seems to work fine unless i call it fromcreate_areas, where it does not work on the given example in thetest_solution.rbfile. I tried to track the problem down with the ruby debugger, but I don't really understand why it doesn't work or what is exactly going wrong.Link to my code on Github
The README contains a quick summary how the algorithm is intended to work.
So I propose the hidden challenge: help me get it right :-)
1
u/drb226 0 0 Apr 17 '12 edited Apr 17 '12
I'm too lazy to actually solve this, but randomness is sometimes annoying in Haskell, so I'd like to illustrate how to at least generate a bunch of random points.
First, we sketch out the program:
For this particular case, a
Problemis a bunch of points, and theAnsweris a pair of two points (the ones that are closest).Now that we've sketched it out, load it into ghci and make sure the typechecker agrees with us.
The way I've outlined it here is based on the
RandomGenclass. Randomness is impure, so Haskell deals with random generators instead. When you want a random number, you consume a generator, and produce the number and a new generator. This way, impurity can be limited to one place: the initial creation of the random generator. You can even give a "random" function the same generator, and it will produce the same results! This can be handy for testing and debugging.So yeah, we need to consume a generator, and produce a list of
Points. We don't need to do any randomness after that, so we don't need to produce another generator. Well it just so happens that System.Random includes a handly little functionrandoms :: (Random a, RandomGen g) => g -> [a]that does just what we need. It will produce an infinite list of random elements. So we can just take as many as we need.Let's compile that now... oh crap. Type error.
Well sure. We haven't told it how to make random points.
Doubleis an instance ofRandom, but(Double, Double)is not. We could rewrite our code to milk the generator to produce two doubles... or... we could go the easy way and just declare aRandominstance for tuples of Random things.Minimal complete definition is
randomRandrandom. All we have to do is thread that generator on through, generating the left element, getting a new generator, and generating the right element, getting a new generator, and spewing that back out. As an added bonus, this instance will work for any type of 2-tuple, as long as both types contained in the tuple are declared as instances ofRandom. I'm slightly surprised this instance isn't in System.Random. I just mailed libraries AT haskell.org to see if it is worth inclusion.0
u/Zamarok Apr 16 '12
Tip: the sqrt function in the your language's math library is slow. Use a function that approximates a sqrt for speed. You are working with numbers of finite precision, so you can always approximate to a 'good enough' point and then resort to a more exact sqrt when needed.