Wednesday, September 15, 2004

Google Code Jam

Warning: Geeky Content.
I participated in the Google Code Jam challenge phase today. You are given two problems to solve in one hour. On problem is for 1000 points and another easier one is for 400 points. The solution can be submitted in C/C++, C#, Java or VB.NET (Python not allowed :( ).
I worked on the 400 pointer first. You are given a list of strings like {"...Y...T..",".......T..",..} where Y denotes your position and T denotes an enemy. You are to return distances to each enemy. Pretty straightforward (piddlu in IIT lingo). I guess the only factor here is how fast you can code up the solution. Passed the test cases in the first attempt. That left me about 45 minutes for the 1000 pointer.
For the 1000 pointer you are given the weight, coordinates and time of a rock falling into a pool. With each passing second, a ripple moves around the rock with the initial amplitude equal to the rock's weight. The amplitude falls with time as the ripple moves out. The ripple is square shaped. Ripples from different rocks add up. You are given a list of strings of the form "weight time x y". The function should return the highest amplitude at any point of time in the pool. Took about 40 minutes to code it up slow and steady. There were two errors which I couldn't fix in the 5 minutes that remained for testing. The sad thing was that one of the errors was was a stupid optimization that I shouldn't have added before testing (premature optimization - BAD). The other was my old nemesis - a boundary problem (< instead of <=) that resulted in one edge of the ripple not containing all points. I submitted the code anyway. In another 10 minutes after the deadline I was able to fix the errors with a couple of debug prints of the pool matrix. I wish I'd added the debug prints initially. I guess I should have attempted the 1000 pointer first (I have solid 20/20 hindsight) but the 1000 pointer in the practice rounds had given me the heebie-jeebies.
The 1000 pointer in the practice round had a graph where all nodes are connected to each other. A pseudo random generator gave the weights of the edges initially (note initially). You are given two nodes and the shortest path between them has to be determined. Looks like a simple application of Dijkstra's algorithm so far. But, the weights of the edges change while you are traversing the graph. If you travel along an edge of length 3, you need to recompute the weights three times (the new weights are pseudo-random). You have the option of looping at the same node. A self-loop has a weight of one. Solutions to most problems involve looping at a node multiple times till the weights are favourable. I coded up a brute force algo that worked for two of the three test cases they'd given. I didn't know Dijkstra's algo then. The program couldn't complete within the 8 second limit for the larger graph. I found another guy's solution later. It took me four hours just to figure out how that worked. That scared me off the 1000 pointer problems.
If you're interested in the problem statements and the solutions, drop me a mail (binu#removehashes#k#s at gmail com).
All in all a good experience (I now believe firmly that participating is much more important than qualifying :) ). There are other contests on TopCoder which is hosting the Google contest. Some nice links I found during all this:
Graph algorithms on Wikipedia
An online book on algorithms
A quick STL tutorial

Sunday, September 05, 2004

The Free Taxi

I pulled off a nice surprise on Rupa (classmate at IIT-B) who came over
from Bombay this weekend. Rups had given me the flight details but he
wasn't expecting me to pick him up from the airport. As I saw him coming
into the arrival lounge, I hid behind a pillar.
A taxi driver swoops down on Rupa: "Sir, Taxi?"
Rupa (busy punching some number on his mobile): "Nahi"
I move in from behind: "Sir, Taxi chahiye kya?"
Rupa (again without looking up): "Nahi. Katao."
Me (expecting Rupa to look up this time): "Sir free taxi hai."
Rupa (yet again doesn't look to see who is offering a free ride): "Nahi
chahiye."
Me (sure he'll look this time): "Sir apko Binu se milna jana hai na?"
Rupa (finally looks up bewildered): "Abbe!?"

Wednesday, September 01, 2004

The Life, the Universe and Everything

Try this query on google:
answer to life, the universe and everything