Wednesday, March 30, 2005

Public Transport

Taking a cue from Kamath, I'm trying out public transport these days. The experience so far is pretty decent. The commute takes a little longer. It takes about one hour now in either direction, but it's stress free. No more getting bugged with signals that take an eternity to change, two wheelers cutting across dangerously or autos poking their wheels to jam your way.

It did take some time to get used to it. The boards have destinations written in Kannada only. Even though I can read a little bit of Kannada, I still couldn't read the boards fast enough. I have to use context to figure out most words. For example, on the day Veerappan was shot, a Kannada paper's headline read Veerappan something. Context didn't help me get the word since I was told later that the headline was "Veerappan Phinish". Even if I do manage to read the destination I still wouldn't have a clue if the bus to Mangammanpalya, Attibele or Chandapura goes through Sarjapur road. But most passengers are helpful if you ask them. On the first day I waited for about half an hour at the the wrong bus stop till someone finally told me that buses that stop there only go towards ShivajiNagar and Airport. By the third day I had the routes and the stops figured out. I still have to ask when I see unfamiliar numbers.

Most of the time I've been lucky, getting a bus right till the quarters. On some days I have to walk a bit, but that's good. With a daily pass for 25 rupees, you can hop on to any bus. From HSR it takes one hop to the new Shanti Nagar depot and another from there to Richmond road. The bus depot is well organized, with separate lanes for buses on different routes. So I know that all buses in a particular lane will go up to Koramangala, after which I can switch again if required. Kamath tells me that when the roads are badly jammed you can walk across the jammed intersection and hop on to another bus.

On some days the bus ride is pretty entertaining. One day, the opposite seat had a man trying hard to get a few winks of sleep. Next to him was his nemesis, a guy chattering on his mobile. The groggy chap would occasionally raise his eyelids with supreme effort and reply to some of the motormouth's questions on the phone. None of this seemed to affect mobile addict though. Yesterday there was an altercation between two people that went into a tight loop with each one asking the other, "Neenu Yaru?" (Who're YOU?). When one bystander tried to resolve the deadlock, he was in turn asked "Neenu Yaru?" (Who're YOU to intercede?). It all ended with neither of them getting an answer when one of them had to get down at his stop. I wish my phone had an FM tuner for the not so interesting days.

Let's see how long this new found enthusiasm to reduce the traffic density in Bengaluru lasts.

Tuesday, March 29, 2005

Sweet Sixteen

The Google India Code Jam final round was held in Bangalore last Saturday. Among the fifty finalists, there were a good number of contestants who had been flown in from Singapore. Most of the finalist were students. The contest was held in two Reliance Webworlds in Cunningham road and CMH road. This time the problems were tougher than those in the qualifiers, though the time limit was increased to two hours. The first problem was related to web crawling. You are given a list of URLs that the crawler traversed first. The second list contains URLs crawled from the pages in the first list. Each URL would be preceded by an index into the page in the first list. These URLs would be relative to the URLs in the first list (can contain ../). A third list contained URLs found in pages in the second list. The aim was to find the total number of unique pages in the list. This took some time to finish.

The second problem involved finding the path with the shortest number of turns between two points in a 500x500 matrix. All the roads in the matrix were specified by their start and end coordinates. This problem was far too tedious to attempt in the remaining time. One had to find all the intersections of the roads and construct a graph. After determining the edges on which the points lay you had to find all possible paths between the two points and get the one with the minimum turns. In case two paths had the same number of turns, there was a crazy sorting criterion for resolving the order. I wasted some time on this before giving up and moving to the next problem.

The last problem was a battle game. You are given a certain number of armies in your territory. Your opponent has three territories and the number of armies in those territories is also given. When you attack any of your opponent's territories, there are probabilities for 2 to 3 possible outcomes (you lose 2 armies, he loses none, both lose one and so on). If you win a territory, you need to post one of your armies in the territory before attacking the next one. Depending on the sequence of the attack, the probability of winning would change. The aim was to determine probability of the best winning strategy. I coded up a solution with a recursive algorithm to this one, but it was far too buggy. I ran out of time while debugging it. No regrets though since I'm not sure if the algo would have worked even if all the bugs were thrashed out.

Luckily for me, there were hardly any submissions for the second and third problems. Based on the submission time for the first problem, I was at the 16th position. After the contest ended at 1:30, everyone went to the Google office for lunch and technical talks. Lunch was good and the tech talks were interesting. The first talk was about the page rank algorithm. Spammers are always coming up with ways to get the Googlebot to rank them higher and Google is always looking at ways to counter their moves through changes in their page ranking system. The next talk was about the massive Google cluster and their cluster file system. I think they did a good job of convincing everyone that Google is the place to be in if you want to do interesting work in computer science.

The awards ceremony was next. I was relieved to know I had retained the 16th position after the system tests. That means a cheque for 25 K (minus the taxman's share :( ). There was a dinner in the evening at the Taj where I got to chat with some of the other contestants and the hosts.

It was a great experience. Google intends to interview finalists who are interested in a job with them. I have declined the interview for now.

Thursday, March 17, 2005

Engaging Week

On Tuesday I got a mail asking me to confirm my participation in the code jam finals. That kept me grinning for a while. But on Wednesday I was grinning from ear to ear all through the day. I think I still am. I'm now formally engaged to be married to Preethi.

The engagement was a family affair at Preethi's home. Her uncle asked everyone present if there were any objections to the match. How could there be? Anyway, I glanced menacingly across the room just to be sure (OK. I'm kidding). After that both our horoscopes were tied into a bundle and presented to my uncle and the date of the wedding was announced. Simple. The wedding is on the morning of April 22nd (9 to 9:15 am) in Bangalore. No more details here. That should get some of you to write to me. You'll see me soon with the invitations.

Engagement snaps here:

Sunday, March 06, 2005

Google Code Jam Update

The final results are out. Here's the link. I'm number 51, the guy on the fence. The good news is that if any one among the top 50 cannot confirm his/her participation in the onsite round in Bangalore, I'm in. Since a good number of the finalists are from Singapore, Indonesia and Malaysia, I guess I still have a decent chance of making it.

Saturday, March 05, 2005

Google India Code Jam

I made it into the first round of 500 qualifiers in the Google India Code Jam. That kept me busy for a while. The round to select the top 50 was held today. The results aren't officially out yet, but I'm at number 52 now, missing the top 50 by the narrowest of margins. What makes it really hurt is that I did pretty good today and could have been placed 15th but for a case I hadn't considered in one problem.

There were three programs to be submitted within the alloted time of 1 hour and 15 minutes. The points allotted to any solution depended on how quickly you submitted the solution.

The first problem for 250 points was very simple. There's a mechanical display that displays binary number numbers up to 32767 from a counter. The display gears that wear out for each binary digit flip. Given any two numbers, you had to calculate the wear in the display when counting between them. Pretty simple. Got a pretty good score on this one.

The second problem for 700 points had a 11x11 chessboard. You are given the position of rooks and bishops on the board in a format like "2 5 Rook", "4 8 Bishop". Up to 50 pieces can be given. You have to return the number of squares on the board that are controlled by the pieces. If a bishop or rook come in path of each other, the number of squares controlled comes down since the line of attack is blocked. Scored well on this one too. Doesn't require much thinking to code up a solution to this one.

In the last problem for 900 points you are given a sequence of integers. You need to determine the minimum number of changes required in the series to make the it an arithmetic progression. For example if you are given a sequence like
"100 -90 130 175 800 225 -10 275 30", the sequence you can make with minimum changes is "100 125 150 175 200 225 250 275 300" changing numbers at positions 2, 3, 5, 7 and 9. So the result is 5 changes. This was my waterloo. I coded up a solution that would work fine with series like this one. When I submitted the solution, I had totalled 1386 points with 30 minutes to spare (45 minutes for three programs).

At the end of the coding round, I was placed 15th, making it comfortably in the top 50. Next it was the challenge round for another 15 minutes. In this phase you can view the source code of the nine other contestants in your room and challenge them. If you provide a test case that fails, you gain 50 points, else you lose 25. I did find a valid challenge but couldn't get the 50 points since another guy challeged the same code successfully just before I did.

The system tests began next and went on for an hour. My solution for the third problem failed for a case like this "999 2 998 4 997 6 996 7 -999 9 10". This could be made into a series like "1 2 3 4 5 6 7 8 9 10 11" with 8 changes which is the minimum required. My solution however considered a transformation to "999 998.5 998 997.5 997 996.5 996 995.5 995 994.5 994" and returned 7 instead. If only I had ignored progressions with non integer increments I would be beaming right now. The thing with the code jam is that even if your solution fails one case, you lose all points for the submission. This mistake cost me 650 points and I slipped to the 52nd position. I missed the top 50 by 6 points. Could have made it with the 50 points from the challenge. The only hope now is if at least two contestants from the top 50 cannot confirm their participation in the final round in Bangalore.

Shit happens.