Last week, a friend forwarded me a link to a programming practice problem on HackerEarth.  The problem is called ‘Gold Mines.’  In brief, the goal is to find the amount of gold present in given rectangular areas of a matrix filled with varying amounts of gold.  The problems are set so that not only do you need to get the correct answers but also get the answers within the space and time set by the judge environment.  You can code in any of the 11 programming languages they have made available in their in-browser editor for this problem.

As I have started learning Ruby (and Rails) recently, I decided to tackle the problem in Ruby.  Though it was producing correct answers on my machine, the program did not complete within the time limit when it ran in the judge environment.  My initial reaction: it can’t be done in Ruby because Ruby is slow.  Looking at previous submissions by other programmers, those who got 100/100 had done it in C and C++ which are known for their speed.

Having used a few other programming languages before, I decided to implement the same algorithm in other languages to verify whether the problem lied in the speed of Ruby.  The first test was in Perl.  No luck.  The same results as in Ruby.  Has anyone done this in any language other than C and C++, I wondered.  I decided it was also a good time to refresh my C/C++ skills.  Coming back to a statically-typed language after using dynamically-typed languages lately, I was reminded of how one needs to be careful with details such as type of integers and containers.  When the C++ code was submitted, the test results fared only slightly better.  The final result was still 50/100 but the rest of the results were partially correct as opposed to ‘time exceeded.’  Noticing that this was the best mileage I got out of three languages, I decided to ‘optimise’ the C++ code by refining the data types used and the methods of dealing with I/O.  Meanwhile, my C++ code became more like C, after converting cins and couts to scanfs and fprintfs respectively and vectors to arrays.  I thought I might as well just run it as a C program, and I did.  Even the might of C did not help.  There can only be one of two reasons:

1. The algorithm is not time-efficient.  Most likely.
2. Over-engineering of the code.  Should using a short int make it more efficient than using an int?  signed vs. un-signed?

It was time to re-visit the algorithm.  At this point, the friend who forwarded me the link, had just cracked it in Python.  That was good news, as Python, Ruby and Perl are in the same family of dynamically-typed languages.  I decided to re-write the algorithm from scratch.  The results were 100/100 in Ruby.  The implementations in Perl and C/C++ followed suit.  Please note: I am not stating the details of the algorithm so as not to spoil the other programmers who are working on it.

Points To Take Home

1. Micro-optimisations do not improve the performance that much.  The bottleneck is almost always in your algorithm.  Fundamental things like split, and integer promotions in Perl, Python and Ruby have been optimised by the community and you are not going to do anything cleverer by not using them or writing a similar one your own.  In C/C++, the code is optimised at compile time.
2. Coding the same solution in different languages make you write cleaner code and make you think about different implementations because one feature is available in one language but not in the other.

All in all, it was a good coding practice and I will be hanging out on HackerEarth more.  It makes me mindful of writing code efficiently and refreshes my skills in other languages that I have not used on a regular basis.