Following on from a hardware challenge sent out at work last month, I posed a Software Engineering focused problem.
As a successful global company, we have many customers around the world. While marketing are gallivanting around, visiting customers, it might be handy to have a program that tells them which of our customers are closest based upon which customer they are currently visiting. Being an engineer who is interested in writing software that is useful to everyone, you decide to write a general solution to the quandary. Each of our customers lives at a unique location. For the purposes of this program, the world is flat, and the latitude and longitude are for all intents and purposes Cartesian coordinates on a flat plane. For example, in our flat world, lat 45, long -179 is not as close to lat 45, long 179 when compared to lat 45, long 170.
The task was to write a program that takes a single argument on the command line. This argument is a file name which contains the input data. The program should output the nearest three other points for each customer in the list. Note at least one test will require having to deal with all of our (virtual) customers.
EntryFinal timing will be carried out on my 64bit ubuntu machine which has support for the following languages/compilers:
- python 2.7, 3.2, 3.3
- pypy 1.9 (python 2.7.2)
- gcc 4.7.2
- clang 3.0
- php 5.4.6
- ruby 1.9.3
- nodejs 0.6.19
- ghc 7.4.2
- go 1.0.2
- mono 2.10.8 (.NET 4.0)
- octave 3.6.2
- lua 5.2
- java (OpenJDK Runtime Environment (IcedTea7 2.3.6))
1 40.71 -74.01 2 25.04 121.53 3 -4.33 15.32 4 -12.05 -77.05 5 30.05 31.25 6 39.91 116.40 7 51.51 -0.13
1 4,7,3 2 6,5,3 3 5,7,4 4 1,3,7 5 3,7,6 6 2,5,3 7 5,3,1
Results!Many people made very successful brute force implementations. Some used squared distances for comparison to avoid computing square roots. Around 1kB of source was enough for bruteforce solutions in lua and python. Smallest was around 40 lines of Python code.
For really small N, brute force was quicker than the "smarter solutions". But there was still quite a spread in the max N each solution could solve: