Skip to main content

Software Challenge 2013


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.

Entry

Final 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
  • luajit-2.0.1
  • java (OpenJDK Runtime Environment (IcedTea7 2.3.6))
More esoteric environments may be added if you really want. If the program failed to terminate in five minutes for any single verification test, or if the program fails to compile, or terminates early I discarded that program as an incorrect entry and sent an email with the reason.

Example Input

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

Example Output

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:


KDTree

These are the data structures I was expecting, I created one in pure python that was reasonable but couldn't compete with the compiled solutions over a certain input size. One engineer submitted a Python + Scipy solution that simply imported scipy.spatial. This was reasonably fast, and very easy! The same engineer also wrote a brute force solver in cython that was much faster for the smaller tests.

Nontree?

The winning solution was a bit of a new take on a quadtree - with nine children instead of four and splitting occurred at 40. It easily solved fifty million customers in around two minutes. When all my resources were dedicated it could often solve one hundred million as well. I had a few occasions where my system locked up at that size though!

Timings


Summary

A single bitcoin was the main prize, although finding one has proven tricky! I thought it was a fun challenge, and I look forward to the next one!

Comments

Popular posts from this blog

Matplotlib in Django

The official django tutorial is very good, it stops short of displaying
data with matplotlib - which could be very handy for dsp or automated
testing. This is an extension to the tutorial. So first you must do the
official tutorial!
Complete the tutorial (as of writing this up to part 4).

Adding an image to a view

To start with we will take a static image from the hard drive and
display it on the polls index page.
Usually if it really is a static image this would be managed by the
webserver eg apache. For introduction purposes we will get django to
serve the static image. To do this we first need to change the
template.



Change the template
At the moment poll_list.html probably looks something like this:


<h1>Django test app - Polls</h1> {% if object_list %} <ul> {% for object in object_list %} <li><a href="/polls/{{object.id}}">{{ object.question }}</a></li> {% endfor %} </ul> {% else %} <p>No polls are available.</p> …

Homomorphic encryption using RSA

I recently had cause to briefly look into Homomorphic Encryption, the process of carrying out computations on encrypted data. This technique allows for privacy preserving computation. Fully homomorphic encryption (FHE) allows both addition and multiplication, but is (currently) impractically slow.

Partially homomorphic encryption just has to meet one of these criteria and can be much more efficient.
An unintended, but well-known, malleability in the common RSA algorithm means that the multiplication of ciphertexts is equal to the multiplication of the original messages. So unpadded RSA is a partially homomorphic encryption system.

RSA is beautiful in how simple it is. See wikipedia to see how to generate the public (e, m) and private keys (d, m).

Given a message x it is encrypted with the public keys it to get the ciphertext C(x)with:

C(x)=xemodm
To decrypt a ciphertext

Bluetooth with Python 3.3

Since about version 3.3 Python supports Bluetooth sockets natively. To put this to the test I got hold of an iRacer from sparkfun. To send to New Zealand the cost was $60. The toy has an on-board Bluetooth radio that supports the RFCOMM transport protocol.



The drive protocol is dead easy, you send single byte instructions when a direction or speed change is required. The bytes are broken into two nibbles: 0xXY where X is the direction and Y is the speed. For example the byte 0x16 means forwards at mid-speed. I was surprised to note the car continues carrying out the last given demand!

I let pairing get dealt with by the operating system. The code to create a Car object that is drivable over Bluetooth is very straight forward in pure Python:

importsocketimporttimeclassBluetoothCar:def__init__(self,mac_address="00:12:05:09:98:36"):self.socket=socket.socket(socket.AF_BLUETOOTH,socket.SOCK_STREAM,socket.BTPROTO_RFCOMM)self.socket.connect((mac_address,1))def_write(self,data_byte):…