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

1 comment:

Anonymous said...

the profile pic looks really Geeky. (bathing once in a while could be a revolutionary idea).
this post is in line with the picture.
Geeks inherit the earth.