Why I don't think much of government...

This is actually a reply to Sagar's comment about my low view of the government. You can see the original post here, and the comments are below that. It deserved more than a few lines of text in reply, so I've given it a post of its own..

It's not that I hate governments - it's just that I have a rather cynical view of them. There's a gaping flaw in our current model of democracy - or rather, a lesson which people often learn subconsciously, but which needs to be explicitly incorporated into the workings of government. The lesson is - always distrust the people who govern you. Never give them the benefit of the doubt - ever. Failure to do so invariably results in either:

1. Dictatorship/Oligarchy/Plutocracy, or
2. An all powerful bureaucracy.

Trusting those who have power is a bad thing - either they misuse it, or they make human mistakes which go undetected and end up amplified because of the unquestioned power. Both ways, the governed lose...

My views on this are heavily influenced by Chapterhouse: Dune - see the discussion between Lucilla and Great Honoured Matre(the 'Spider Queen')...

BTW, I have similar views on laws - or rather the stupid view that goes 'The letter of the law must be observed.' Such a statement doesn't aid justice - it turns it into a side issue. As Dune's Bene Gesserit say, the problem with laws is that they have no human understanding...

It just goes on...

It's official - the weather god who takes care of Mumbai's weather has gone certifiably insane. The rain is practically a constant feature now - it never seems to stop, just varies between 'not-so-mild drizzle' to 'killer thunderstorm'...

I'm told the government has declared an indefinite holiday for now - people aren't willing to risk sending their children to school, or risk their cars by travelling. The trains are working intermittently - every so often things go crazy in some part of the city and the trains stop there, which eventually propagates all over the city. As I write, the harbour lines are down, and I don't think the Central lines have worked properly since Tuesday. I don't really know anything about the buses, but BEST lost quite a few in the Tuesday floods, so there's no way they can operate at full capacity in this sort of weather. As usual, people have been asked to stay indoors as much as possible...

The authorities have finally gotten off their asses(mostly) and started doing stuff. In fact, the traffic cops have put in a stellar performance in their yellow raincoats. Nice work guys, keep it up...

And the radio stations - great work done there - they've been helping out people with directions on the road and giving constant updates on conditions in different parts of the city. Plus they play some pretty good music too...

Meanwhile, I've been messing with graph algorithms for the past few days - ended up learning and coding a whole bunch of things - shortest paths, minimum spanning trees, topological sort - the works. Time to do a bit of the theoretical stuff - a weird combination of discrete math, common sense and pseudocode...

Seems like I forgot to mention my last SRM - cracked all 3 probs and fixed the dive my rating took after the power failure on Tuesday. It was a pretty straightforward problem set, but a bunch of new members were disqualified for cheating. Yeesh...Come on people, why mess up such a fun competition by trying to cheat?

Back to work...

Not again...

Once again, the clouds have done their Chappar Phaad Ke act and screwed up life in Mumbai again. Thankfully, things aren't nearly as bad as the fateful Tuesday - and it's a Sunday to boot, so most people weren't at work. Still, there was flooding in some parts of the city, and the delivery of supplies and other relief materials was messed up. To top it off, schools have been closed for tomorrow, and I heard on the news that exams scheduled for tomorrow have been cancelled as well. Looks like Mumbai will never look upon the rains in quite the same way again...

It's a nice holiday for all us lazy bums, but there are so many unfortunate people who suffer terribly every time this kind of thing happens. Busybee once wrote that the difference between the rich and the poor in Mumbai was that the former enjoyed the rain and the latter hated it...

Ah, Nature - the great leveler...

This is probably my shortest blog post ever. That's the second broken record - the first was that I've already posted thrice about the rains - what other topic enjoys so much coverage in Mumbai these days? As my dad remarked today, we've turned into Englishmen - whenever we meet, we discuss the weather...

The aftermath...

One of the things I was going to mention in this post was a small factoid: Mumbai now holds the record for the most amount of rain received in 24 hours. Unfortunately, Thite beat me to the punch by saying this in a comment on the previous post. Feel free to check that out for the numbers...

Turns out the city hasn't yet moved on - a sizable number of people still don't have water or electricity. As usual the authorities are taking their own sweet time getting things fixed up - calling each other names, playing the blame game, and diverting attention away from their sheer incompetence seem to be at the top of their to-do lists...In that respect, things haven't changed - not even this kind of disaster could manage that...On top of that, the bureaucracy is going to waste a huge amount of time in completely useless paperwork - time that could have been spent on relief operations. To paraphrase a wise man, "The government is an ass."

The news shows that people in the affected areas are getting increasingly restive. They've been blocking roads, letting the air out of bus tyres and causing whatever havoc they can, all in the hope of speeding the relief process. Hopefully this will make the authorities sit up and take notice. I have a better idea, though - send the local corporator, MP or whoever a warning - say that the entire neighbourhood/ward/whatever will summarily vote for the opposing candidate in the next election unless things are made to work within 24 hours. If that doesn't work, nothing will...

Still, any canny politician knows the ancient maxim: Public memory is short. Let's hope that doesn't apply in this case - this is not something that should be forgotten quickly.

Thankfully, the agitations are completely run by ordinary people. As of now, there are no demagogues taking political advantage of this tragedy. The average Indian politician is of no help - they have neither the wit nor the wisdom to lead or act effectively. As Dune says, "A leader is he who keeps a people from becoming a mob." Out here, a leader is a person who knows the buttons to push to rouse the rabble, and is sly enough to realise that he might get something out of it...

Star News was showing videotapes of the flooding, made by people shooting from windows and the compounds of their buildings. That really brought home the extent of the floods - all this time I had a sort of academic understanding of it - no real first hand experience.

There was one video taken from a great height, that showed it all - no roads visible at all - just one huge lake, with trees incongruously placed here and there, and stalled cars and trains, as well as people trudging resolutely through waist deep water. In some cases water went as high as 10 feet. No wonder they called in the navy...

At least 800 people are dead. That is not a small number. But as Stalin once said, "The death of one man is a tragedy. The death of a thousand is a statistic." Sad, but true. Just hearing numbers like that desensitizes you. You have to really think about what the number means before anything vaguely resembling an emotional response comes out.

Hats off to the good samaritans who did what had to be done - hundreds of them did a great job distributing water and biscuits to people struggling to get home. These are actions that save lives. Dumbasses with political power, take note.

The sad reality is that Mumbai's disaster management began and ended with the aforementioned heroes(and that's exactly what they were - contrary opinions, bugger off). While no one envisaged anything like this, surely a sensible disaster management group could have adapted plans for other eventualities to this situation. As it turns out, there was no disaster management group, or any plan of any kind. Words - that's all they had - empty words. I tend to be a little verbose at times, but at least I know that words are supposed to mean something. The people in charge don't even act like they're trying - all they do is talk. WTF??!!

Ok, so this post has turned into a full blown rant...Hell, a situation like this deserves a rant. Rant away, Mumbai bloggers!

Mumbai falls to its knees...

This was going to be a long rant on the devastating rains a couple of days ago. Unfortunately, the comp unexpectedly restarted when I was writing it, so I'm gonna be writing the whole thing from scratch. To save time, I'll just give a blow-by-blow description of what happened to myself and the rest of my family, followed by a little something on the rest of the city.

Let's start with me. Having set my priorities right, I decided to bunk college after lunch for a TopCoder SRM. This decision turned out to be providential - there was only a light drizzle at the time I reached home, but shortly after that the heavens unburdened themselves and blasted the city. In less than an hour, my building compound started flooding. The roads followed suit in minutes.

Anyway, I was sitting pretty and doing the SRM, pretty happy that I'd escaped the deluge. Just before I was about to submit the room's fastest 250, my net went down. My reaction: WTF!!! Luckily it came back a minute later, but I'd lost the first place and had to be content with second. I started up the 500 and finished coding it up faster than the rest of the room. I'd just finished testing and was making a minor change before submitting, when BOOM - my net was down again...My mom was reluctant to let me use dialup for fear of blocking the phone lines, but that idea went down the drains(which were already filled to their limits) when the phones went dead a couple of minutes later. Having no choice left, I went off and watched TV for about 15 mins, giving up the SRM as a lost cause.

My mom had been trying to get through to my sister in college for quite some time, but the Orange network went down soon after it began pouring. Eventually my sister got through to me and told me that getting out of college was impossible - the entire area was flooded. She planned to wait it out. What eventually happened was that a big group of about 5-6 people went wading through knee deep water to her friend's place, and ended up staying overnight.

Meanwhile, the ground floors of all the buildings in the area were flooding - people living there were moving upstairs in a hurry. Worse still, power failed a little while later - and remained gone for about 24 hours. The net was gone even longer, more's the pity...

More horror stories:

1. My cousin walked from Juhu to Bandra in what he claims was 'neck-deep' water.
2. My dad got home the next day at around 2PM - apparently they got to Vile Parle in a colleagues car, which they had to abandon since the roads were blocked by cars left behind from the previous day. The owners had apparently decided that walking was more practical and left their cars behind wherever they could. Since it was pouring terribly and the street lights were out(there were power outages all over the city), they didn't exactly park by the curb...So my dad and his friends ended up walking from Nanavati hospital to Bandra.
   
3. My aunt took 7 hours to get from Colaba to Bandra. I thought this was some kind of a record, but listening to the radio disabused me of that notion when someone mentioned that it was the 21st hour of his commute home...
4. My other aunt couldn't even get home to Andheri - the roads are still littered with cars so it's pretty difficult to get through.

Thankfully my entire family is safe, and I haven't heard of any casualties among friends, except for one who slipped and hurt his leg in a manhole...Unfortunately, the same is not true for everyone - Thite mentioned that a friend of a friend of his was killed by a falling wall, and another friend's friend's mom was drowned in Kalina...Terrible.

I ended up missing my TOEFL, which was scheduled for Wednesday. There was no way I could have actually reached Saki Naka under these conditions, but we found out later that there had actually been a land slide somewhere there. Once again I am miraculously saved - though of course, it only looks that way in hindsight.

Schools and colleges have been declared closed for 2 days. This leaves only Friday, and most people have decided to give it a miss, just in case something happens again...and for other, not so cautious reasons...like another TC SRM!

Things are returning to normal, but all is not yet well in Mumbai. It's gonna be a few more days yet...still, the legendary Mumbaikar spirit will pull through as it always does. Just goes to show - Nature's blind, insane fury can destroy us and our creations, but it can never permanently defeat the combined power of the human spirit and human intellect. Nature, thou shalt be humbled yet!

The pillars come crashing down...

This has got to be the strangest TopCoder SRM I've ever been in...What follows is a short description of what happened, as seen through the eyes of yours truly.

Halfway through the match, we lost the ability to compile code - people who talked to the admins were told that the servers were experiencing load problems - a little later there was a broadcast about this matter. A bit later, testing became slow, and a couple of times my compile requests also timed out.

A bit of background about my position - I'd gotten off to a bad start on the 500 - while the C++ coders simply used the famous next_permutation() function and waltzed through it. Planning to write my own version for later matches now...Anyway, I came up with a workaround, and got to work on the 1000, which was around when the problems started.

A little later, my connection to the arena was lost - this used to be pretty routine earlier, but a few days ago my ISP finally decided to come to its senses and fix it. I wasn't expecting to see it again, so I was slightly bugged, but not too much - the fact that my 1000 had an odd bug wasn't helping either...

I logged back on, and noticed two things:

1. Instead of the usual 5-10 people in the chat room when you enter, there were dozens - and more were pouring in every minute. The place was filled with urgent sounding messages in at least 5 languages.
2. I went to click on Active Contests > Enter - and it was grayed out! My reaction is aptly summarized as: WTF??!! About a dozen other people expressed similar sentiments in exactly the same way...

So there we were - happily coding away - and the match came to a grinding halt.

A minute or so later, it started up again - unfortunately, I had chosen that very moment to head for the loo, not expecting the admins to fix things so soon. Of course, unlike some people, I didn't log off in sheer frustration...

Got back in, tried in vain to do the 1000, and then sat bored throughout most of the challenge phase.

Eventually the admins sent out a broadcast apologizing for the inconvenience. The good news was that they weren't going to rate this match - no prizes, no rating changes - zilch. Got an email a few minutes ago that said the same thing...

All in all, it was a very odd experience - definitely going down in TC history...

That wasn't all of it - after the match I was lurking in the arena and chatting with a friend, when I noticed that the System Testing readout was actually changing - they were testing again! The word was that there was something wrong with their solution of the Div 1 500 - causing widespread failures in systests...After that ended, it started again, about five mins later - as my friend commented - "Systests have gone into an infinite loop...."

Ah well, it's pouring outside and I've decided not to go to college...Time to do something useful...

Sleepy ramblings...

Our time table sucks. And I mean big time.

Four days a week, 8AM to 4 or 5PM. Only 2 hours of college on the 5th day, but that's still too much. The only saving grace is that we have Monday off - that's supposed to be project day...The upshot of this is that my class is full of sleepy people - and I'm one of them...

Something seems to have put the fear of God into my college people - or at least the Computer Department - someone in high places seems to have made it clear that they aren't very happy for some reason. Consequently, things are rather different from the usual beginning-of-term experience - no cancelled lectures, no missed practicals - everything is running in high gear from day 1.

It's almost pathetic to see the way the teachers reacted - they seemed to understand what was behind the decision, but we weren't able to get much out of them - one of our teachers said, "The reason is that there is no reason!" And no, she doesn't practice Zen Buddhism, that was just a very badly formulated sentence - not surprising really...

It never ceases to amaze me how transparently servile some people are. One of the big shots is angry, so word goes around - "Tighten things up, we want a tight ship - chop chop!" It's so bloody obvious that they're trying to appease someone. I always find this sort of performance disgusting. I've said it before and I'll say it again - so much for subtlety...

Why do I find this so repellent? Probably because I don't have much humility - I find it utterly impossible to defer to my so-called 'superiors'. I can feel admiration or respect on the basis of skill, knowledge, character, and so forth, but I feel nothing at all for people who just happen to be above me for some random reason. It's a stupid world, after all - not many of them deserve to be where they are...

Because of this weird bent of mind, I don't know how to beg, grovel, blah blah...Can't figure out how people do it. This thought always brings to mind Howard Roark from the Fountainhead - in the passage where he's begging Guy Francon - the man just can't do it, and the begging turns into an insult to Francon - now that's cool...Of course, Howard Roark was incredible, but what's wrong with that?

Ok, so I'm bitching around because I'm rather drowsy, but there's usually a lot of truth in my perceptive complaints...And I'm modest too.

Been reading Zen and the Art of Motorcycle Maintenance again. Might just be an illusion, but I seem more receptive to it now than I was earlier. And as I've said to at least a dozen people, the book doesn't say much about Zen Buddhism, nor is it much of an authority on the maintenance of motorcycles...

It's got me thinking about all sorts of things - the old 'being vs doing' thing that I mentioned in earlier posts, Paul Graham's views on art and hacking, and some recent thoughts on the nature of excellence, the fact that all men(and women) are not really equal(except before law, God and the usual yada yada...), the nature of excellence, and so on. Maybe I should consider becoming a professional philosopher...

Also got my hands on book 2 of Tamora Pierce's Daughter of the Lioness trilogy - Trickster's Queen. Pretty good stuff. Maybe I should read other stuff by her. One thing really interesting about her universe - the gods don't really care about humans suffering or dying - they just think of them as tools for the satisfaction of their desires. They're pretty alien in that way - you can't blame them for not being worried about humans - it's just not relevant to them. Of course, they aren't really omnipotent, or even omniscient - just enormously powerful. Plus they fight each other and stuff like that - but the implication seems to be they can't kill each other. All they can manage is to kick each other to the other side of the universe - and the only reason that is undesirable is because the millennia it'll take to come back will be very boring...Even the power to do that depends on the victories of their worshippers...weird, but at least it's believable. Presumably they weren't responsible for the creation of the universe either...

Really should be getting some sleep now or I'll end up hallucinating in class...

Back to the rat race...

So college is on again. Not really happy news - it's mostly a boring waste of a lot of time that could have been profitably wasted instead...Case in point: I'll end up missing my TopCoder SRM tomorrow, because we have an 0800 lecture, and this prof is not the kind of person who turns up late. Looks like I've been reduced to just the weekend matches. Darn it all...

Note to Thite: All the best for your first SRM - just don't oversleep and miss it ;-)...Your notorious lack of punctuality might also work against you - be sure to be there at least 10 mins early - registration for an SRM ends 5 mins before the match begins.

I've made a couple of changes to the comment system - it always bugged me that comments could only be viewed on a new page if you were reading the main page. With a little help from Blogger Hacks, I've fixed it so the comments will kinda unroll when you click on the link...Be sure to gimme some feedback on it!

Looks like we've got Digital Signal Processing and Advanced Microprocessors this semester. Bad - I really don't like the electronics related subjects so much - software is still my major interest. I hear DSP is mostly maths - hope that's true, because I don't have much of a memory for circuit diagrams.

Began writing a little Java program this afternoon to do the Mumbai Mirror's daily Sudoku challenge. I've got it deducing things to the point where it correctly fills up about half the grid - the only problem is that it can't go any further. Looks like my friend Sagar was wrong - as far as I can see, there isn't enough information in the problem to uniquely determine each grid value. At some point, you probably have to guess and see if things work out that way...Of course, the other option would simply be to use a brute force combinatorial approach - generate all possible grids, and pick out the one that matches the puzzle data - but where's the fun in that? At least this way I'm still using logical reasoning - I've just outsourced the details to my computer. Maybe there's some kind of reasoning that I can't put my finger on just yet....

Hmmm....Wikipedia says that the general Sudoku problem on an n x n grid is NP complete - luckily, the simple case of n = 9 can be managed using state machines, so at least I'm not wasting my time...

This is interesting...Turns out that Sudoku is a variant of graph coloring problems - no wonder I kept thinking vaguely of graphs while I coded...Maybe I can use this - and it'll be a good excuse to read up on graph coloring and other such stuff. Will report future progress in a few days...

In other news, I have the TOEFL scheduled in 2 weeks time - not that it should be too much trouble, but it never hurts to be prepared...

And now to sleep, perchance to dream...

Got into Infy!

So we had the Infosys placement yesterday, and guess who got in...

This was supposed to be a rather in-depth look at the interview process, but I'm a little tired right now, so let's skip the details and go to the gist of things...If this seems a little below my usual post standard - chalk it up to fatigue and boredom...

As interviews go, this was a bit of a deviation from the norm. Of course, Infy is a deviation from the norm as far as companies go, so this just reflects that. There's this huge emphasis on puzzle solving and creativity, which is great, at least as far as I'm concerned. This eliminates a pretty sizable amount of people - but that's hardly a bad thing.

Speaking of the people that Infy seems to pick up - only a handful of them were toppers - by and large, the lot of us were pretty good students, but not excellent ones. Supports what I say about the imperfections of our system.

The aptitude test was pretty good - actually had me scratching my head in a few cases. Fell victim to bad policy - should have answered everything, not just those I knew, since there was no negative marking. Anyway, I made it past their cutoffs, so I'm not complaining...

The really fun thing was their HR interview - there was the standard HR spiel, but it was spiced up with some real interesting questions and puzzles - one puzzle in my case, but up to 3 in some other cases...I'll save the questions for another time...suffice it to say they dealt with stuff like planning and high level strategy, project management, leadership skills, etc. No dirty details, just zoomed out, big picture stuff...

They ended up picking up about 22 people from my college, 7 or 8 of whom were from my class. Apparently, these guys really follow through on their mantra of "We hire for potential." So even guys who are studying Civil/Auto/Production Engg can and do get through.

In other news, I nearly won my room in the last TC match - and lost it when my 500 pointer failed because I misunderstood the problem statement. The really sad thing is that if I had read it properly, I would have actually ended up in the match editorial for the fastest div 2 500 solution...The upside is that my rating went up anyway! Go figure....

Really sad thing now - college begins tomorrow morning, which means I'm gonna miss some TC matches for sure unless Wednesdays and Thursdays have sensible time tables...Worse, I'll have to start getting up early routinely, and there's no more chance to goof off - not that I had much time for that - what with placements and CS GRE stuff. The only consolation is that the CS is enormously stimulating - but now time is really going to be an issue...

Time to sleep - should manage 5.5 hours or so...and then the rat race begins again...

Here be dragons...

During the Wimbledon finals match, I happened to be channel surfing and ran into Hallmark's adaptation of Earthsea. With Federer demolishing Roddick with consummate ease, I didn't get to see the whole of it, but I managed to catch a bit of it in the breaks and during the drizzle...The following rantings deal mostly with Earthsea, language, sorcery and coding, and so on...

A bit of background on the Earthsea universe: Magic in Earthsea is done by speaking words of the True Speech, which was the language used to create the world. In the True Speech, word and deed are not separate, and words are more than just sonic representations of things. The great wizards(or mages, to use the correct term) are highly versed in the True Speech, and know the true names of things. Knowing a true name gives a mage power over the thing(or person) that the name represents. As a result, the inhabitants of Earthsea go by another name for practical purposes - use-names, as they call them. True names are hidden and told only to those who one really, really trusts.

BTW, parents don't know the true names of their children either - the names are given at around the age of eleven by a wizard who can sense the child's true name. Thereafter, the child may choose who he will tell the name. No one ever asks you for your true name - you decide to give it to someone. The Master Doorkeeper of Roke(the Isle of the Wise, where gifted students are taught magic) is the only person who asks for a true name - no wannabe wizard gets through the doors of the School without revealing his true name.

The first book of the trilogy - A Wizard of Earthsea - is about a young goatherd from the island of Gont, who eventually becomes both Archmage(the big boss man of Roke island) and a dragonlord. The guy's use-name is Sparrowhawk and his true name is Ged. Unfortunately, in the Hallmark version, they've turned this around - apparently they thought that 'Ged' is not a fitting name for "One who may become one of the great wizards of Earthsea". So everyone calls him Ged throughout the TV version, and he ends up telling the Master Doorkeeper that his true name is Sparrowhawk. Sad...And their idea of the Master Doorkeeper was a bit of a let down - he was nothing like the character the book showed - he looked like a bored court jester. Nothing like the wise and serene old chap from the book.

To top it off, Ged enters and runs into Jasper, an aristocrat and fellow student who proceeds to ridicule him in a highly arrogant tone - "You have the honor of addressing Jasper of Eolg, of the house of Havnor..."

Ok, so the guy in the book is a jerk too, but in a slightly different way - he doesn't actively put down Ged - it's just that his manner is subtly superior, without actually shouting it from the rooftops. It grates on Ged because Jasper has the manners of a royal courtier, and he is a goatherd from a little village, with rough manners and no style...It's the kind of insult that the British manage superbly, but Americans have never quite got the hang of. Like it says at the top of the page - so much for subtlety...

The Archmage Nemmerle isn't true to the book either - he's supposed to be a withered old man - one of the oldest of Earthsea. Instead, he's a pretty vigorous elderly fellow with a long beard. Worse, he doesn't die saving Ged(for more on that - read the book), but ends up merely fainting after spending all that power. Add to that the fact that Jasper betrays them in the TV version, while he just vanishes into obscurity in the book, and you've got a pretty screwed up piece of work.

After that they screw up the timing of the Kargish invasion, neglect to mention the fact that the Kargs distrust and shun magic, and turn Tenar of Atuan into a perfect contemporary of Ged. She must have been at least ten years younger, if not twenty.

Didn't see what else they messed up though - it was too much fun watching Federer trounce Roddick.

Here come the abstractions - as I mentioned a couple of posts ago, I'm actually drawn to this magic business because of coding...This really solidifies the analogy - just as a mage uses the True Speech to manipulate the world, a coder uses a programming language to manipulate a computer. The real difference, of course, is that we have dozens of languages, at different levels, with different goals and uses.

Those who know me well are familiar with my weird brand of laziness. On the one hand I hate doing some things, and will keep on putting them off. On the other hand, I can spend an infinite amount of time and energy working on something really interesting - as long as it's mostly mental. Just yesterday I sat up till 2 AM trying to figure out a recurrence for a problem. The painful thing is that I wound up proving no such recurrence existed...

How does this tie in with wizardry, coding and computers? Computer languages are like the True Speech in another way - doing and saying are really the same thing. For a lazy bum like me, this is ideal. Unlike other types of engineers, I get to work with thought-stuff - no heavy lifting or sweaty work for me...To paraphrase the Qu'ran, I need only say 'Be' and it is. Anyone like me, with a closet hankering for superhuman powers, can't resist being the God of his own private universe. Of course, the architecture of my computer determines the extent of my powers, so the analogy isn't exact - or is it? After all, we've never seen any real miracles, and there isn't any real evidence that any of the famous ones really happened. To the best of human knowledge, there isn't any breakdown in the laws of nature - nor has there ever been one as long as we humans have walked the earth. Is God's power limited by the architecture of the machine he's running our Universe on? That's something for a future blog post...

And here's another interesting allusion that just popped into my head...The Flash ROM on the motherboard that sets the ball rolling when you switch on the computer basically contains a bunch of machine instructions. As they say in the Bible, "In the beginning was the Word."

Here's the last bit - the dragons of Earthsea are not animals like the typical Hollywood variety. They are a far older species than humanity(there is a twist to this tale in book 5), and speak the True Speech as their native tongue. Plus they can fly, breath fire, and are so terrifyingly powerful that only the most powerful mages can kill them.

When I read this bit, I had an obvious question - Are dragons taught the True Speech? This wasn't answered until I polished off book 5 today, and it's a pretty interesting answer.

Human beings are unique among all animals for one reason - we have the power to choose a course of action. Because of this, we have concepts of morality and good and evil, and we can measure someone by his actions. Animals don't do - they just are. It's the same with the dragons - speaking the True Speech is not something they do - it's what they are. As Ged mentions, as he gained wisdom and became Archmage, he learned to choose to do only what he had no choice but to do.

Remember how I mentioned Federer's apparent lack of intensity in the previous post? Let's take a look at the match through the lens of the previous paragraph.

Roddick was busy acting - he went madly after the ball, he fought as madly as he could, struggling to do something, to make the right choices so he would win. But he kept on doing. Against a lesser opponent, that might have worked - it would have then been a battle of two mages, and the one with greater skill would have won. But Federer went through the entire thing without really doing anything - he was just being Roger Federer.

And that's why Roddick couldn't have touched him - not as long as he kept doing what he did. Because as far as tennis goes, Federer is not a man.

In tennis, Federer is the dragon.

Federer conquers!

The title says it all, really...Federer took the Wimbledon championship in straight sets, and I managed to watch almost the entire match. Roddick put up one hell of a fight, but Federer was inhuman - such mastery of the game is insane - and therefore a great pleasure to watch...

Here's the lowdown on what I found interesting...If I begin rambling on about seemingly unrelated things, please put up with it - as all my friends will testify, I'm the kind of guy who says, "That reminds me..." and brings up a topic that no one else can connect with the current subject. Sometimes the weirdness of the connections frightens me, but I suspect it's just normal associative memory in the hands of a somewhat flamboyant mentality...

The first item to note is (obviously)Federer's devastating skill. No matter where you put him on the court, he usually has an answer for anything anybody can throw at him. And he does it with such ease...eerie. It's impossible not to admire such talent.

This relates directly to the second item on the agenda - the contrast between Roddick and Federer.

Anyone who's seen Roddick play knows the way he barrels around the court, leaps in exultation, and clearly displays frustration. Even his returns are characterised by manic energy, and he leaps clear across the court to get impossible shots. He even took a shot from underneath his leg at one point, like a young show-off might...except with him, that kind of response is a natural reaction.

Federer, on the other hand, is moderation itself. His expressions of emotion are few and far between, usually reserved for the real big things. In today's final his expression barely changed throughout, but at the final stroke, he fell to the ground in sheer exaltation. He even broke down for a minute or so - and since this is his Wimbledon hat-trick, I don't blame him. Otherwise, he's as cool and collected as Mr. Spock.

While Roddick rushes all over the court, Federer is practically somnolent. Instead of rushing to meet the ball, he's magically in the place where it turns up. Hell, he practically strolls over while the other guy is cocking his racket to take the shot. The man is economy in motion - no wasted movement. When he returns, it's just a casual movement of his racket. Only the 'killing stroke' seems to have some kind of intensity.

To really see the contrast, you need to see a close up of a slow motion replay. Watch the eyes of both players as they follow the ball. Roddick gave me the impression of a zealous tiger, preparing to spring upon his unsuspecting prey. Federer's eyes don't project that kind of intensity - they seem...lazy. Like watching the ball is as natural as breathing.

Wow - there's a comparison: Crouching Tiger, Hidden Dragon. Just about sums up the two players. In fact, a quote from the same movie comes to mind - "True skill comes without effort."

Roddick makes real great comments, though. Probably comes of being American...Loved his famous one about the kitchen sink and the bathtub last year.

So why do I happen to find tennis so interesting? There's a certain ephemeral quality - not confined to just tennis - that draws me. And then, of course, there's Maria Sharapova and the bevy of Russian babes...

Seriously though, I'm not exactly sure what the quality is - it's there in Halo to some extent. Football has it too, but not in the same degree as tennis.

Just had a sudden epiphany - this ineffable thing is related to outmanoeuvring the opponent. That's why I think of it when I sidestep an Elite's melee attack and counter with one of my own, followed by a barrage of bullets into his skull. Or that time when a well placed plasma grenade forced a stupid Elite to jump right off a bridge to escape. Too bad they don't scream on the way down...It's the same thing when Federer casually sends the ball past Roddick, who ends up wrong footed and unable to take the shot. There was this really cool rally where Federer forced Roddick into one corner of the court. By the time Roddick figured out what was happening, the ball was whizzing into the other corner...

Of course, this leaves me with the question of why outmanoeuvring someone is so much fun...

Time to get some shut eye...tennis fans, drop a few comments...

Of stuff, nonsense and other things...

Time for another set of disconnected, incoherent rantings from yours truly. Here goes...

First up - I always thought that people as dumb as Joey(from Friends) could not exist. Was proved wrong yesterday. Apparently people can be that dumb, at least in some areas of their lives. Ironically, Joey himself revealed my sister's mathematical dumbness to me...A dramatic reenactment of the scene follows:

(Sis and I just finish watching Friends. Conversation begins - the subject being - you guessed it - Friends.)

Sis: Remember what Joey said to Phoebe's brother a few episodes ago?

Me(quoting Joey): "You're 28, she's 44. When you're 56...she's gonna be 88!"

(Aside: Joey is trying to convince Phoebe's brother not to marry a woman 16 years older than him...In the process, he displays mathematical stupidity...)

Sis: That's wrong - what he said was, "When you're 36, she's gonna be 88."

Me: What? But that kills most of the joke then!
(Getting an idea of what's going on...)
Me: Hang on - just what do you think is funny about that statement?

Sis: He tries to figure out their ages and does it wrong! It's funny!

Me: Yes, but he doubles their ages - that's why it's so funny!

Sis: No, if he doubled their ages then he would get it right. That's why it's 36, not 56.

Me(laughing helplessly on the sofa): !!!!

So there you are. Some of my friends have heard me complain about my sister's lack of mathematical skills, but they never seemed to believe me. Here's the proof...11 years of studying Maths and this is what she thinks. No wonder I contemplate suicide whenever her Maths exams come around - guess who has to teach?

Moving on...A couple of days ago I was pondering the religious mindset. People with a strong belief in religion seem to think that there's some kind of cosmic balance, and that Nature is essentially good, but will respond terribly to the "crimes" of humanity, punishing the wrongdoers with terrifying fury.

*ANTI-RELIGION RANT BEGINS*

Let's take a look at last December's tsunami. Dozens of religious leaders and theologians worldwide showed themselves to be consummate idiots when asked about the tsunami. The majority of them said something about "divine retribution" and "punishment for our sins", or words to that effect.

WTF?! We're supposed to believe that a bunch of unfortunate tourists, fishermen, and villagers died horribly as a result of divine retribution? Or that this divine fury chose to kill several innocent children, orphan even more, and lay waste to the homes and livelihoods of people who have no inkling of why they were 'punished' so brutally?

Apparently, no one had the nerve to go up to one of these dumb believers and say, "There's a little Thai girl whose entire family was killed in the tsunami. Her village was completely wiped out. In one stroke, she has been orphaned and rendered homeless. And she hasn't even learned to speak yet. She has no sins to speak of. Why did this happen to her?"

God moves in mysterious ways? Oh please...God, please repeat after me, "You do not punish the sinless, and you don't punish a person for someone else's sins."

Pretty elementary concepts of justice. You'd think a perfect being would have figured it out by now...

So what's my answer? Why did the poor Thai girl have to suffer?

Chance. Wrong place, wrong time. That's all there is to it. Bad things happen, but not necessarily to bad people...they're just random events. Nature is blind. She blunders along, with nary a thought for the creatures that suffer and die in the process.

Just take a look at natural history. Thousands(probably hundreds of thousands, but I'm no biologist) of species have been wiped out over the 4 billion years of Earth's history. The only reason is that they failed to survive as things changed. For most of their lives they were locked in a struggle against the elements and each other, competing for food and room to reproduce. Cruel, painful, and seemingly pointless...

So the ones who survived were the real badasses - the ones tough enough to take whatever conditions came their way. The ones right at the top - the predators - they survived because they could kick butt.

And eventually, from a long line of such hardy survivors, came an ape who decided that standing on two legs was where the action was, and the trees weren't that much fun after all.

This chap and his relatives still weren't human. The first human came a little later, when one of these apes looked around him, realized that things really sucked, and yelled "It's not fair!" and set out to do something about it.

And from the loins of this band of discontents came the deadliest predator in the history of the planet - the human. The other creatures only had claws, teeth and speed. What we had were brains(and as Sagar pointed out, spears) and an insane wish to make things fair and just, even though they weren't.

So remember this - whenever someone complains that people are trying to impose their will upon nature, take a moment to think about the difference between nature and human will. Eventual death after a painful struggle to survive - or a driving desire for fairness and justice, an unwillingness to submit and the power to do better.

Take your pick. I chose long ago.

Reading again...

Looks like I've found something interesting to read again...this time it's Ursula LeGuin's Earthsea Trilogy. I've just devoured the first two books - A Wizard of Earthsea and The Tombs of Atuan. Two more to go...If you happen to like fantasy, this comes highly recommended. LeGuin has a rather strange style, or so it seems to me. On the other hand it might just be typical of the fantasy genre - I haven't read much fantasy, so I wouldn't know. In any event, the story holds the attention superbly.

I always used to wonder why fantasy titles were grouped together with Science Fiction in bookstores - they seemed like opposites to me. I've since come to realize that the difference between SF and fantasy is like the difference between physics and mathematics - physics(the theoretical part) is essentially concerned with axiomatic systems that are isomorphic to the real world, whereas mathematics concerns itself with all possible axiomatic systems, irrespective of the realities they might correspond to...People interested in the weird interplay of physics and maths should look at this paper by the Nobel Laureate Eugene Wigner.

The odd thing is that I never used to appreciate fantasy a couple of years ago - why the sudden change? I wonder if this has something to do with my immersion into programming - after all, wizards weave spells and coders write classes - both of them manipulate what seems(to outsiders) to be a strange and mysterious universe...On the other hand, this might just be one of those specious analogies that you could make to relate any two things...

Also saw Batman Begins today, and the verdict is: this is definitely the best Batman movie ever made! Emphasised all the right aspects - the dark side of Batman, the way he uses the enemy's fear to his advantage, the elevation of Batman from man to symbol - brilliantly done. Katie Holmes' role is nicely downplayed - the other 'Bat babes'(Mr. Bond, forgive the paraphrase...) had too much screen time and played too central a part. Here the central character is always Batman/Bruce Wayne - the others are important, but not really central - as it should be. Add in the ninjutsu angle and the awesome Batmobile, and you've got a rocking movie. Hats off to Christopher Nolan for creating the first movie truly worthy of the Dark Knight. I hear a sequel is in the works - if it can live up to this movie, it'll be well worth the price of admission.

Wow, I'm starting to sound like a film critic...

TopCoder news: Pushed my rating up to 1100, coming in 3rd in my room. This time I heeded the lessons of the last few SRMs and didn't rush. It paid off - I still pulled off the fastest 250 and a fairly quick 500. Just have to keep this up now...

And now to dinner and The Farthest Shore.

Bugged by Shaping Regions

Some time ago I got through to section 2 of the USACO training gateway. For those not in the know, it's a pretty cool website where you can learn algorithmic programming. They basically give you a few problems to solve, and as you do them, you can go on ahead, learning more stuff along the way. Very nice way to do things...

Anyway, section 2 is basically graph theory, and I was expecting something to do with flood fill algorithms on the first problem - Shaping Regions. What I found instead was a really painful question involving stacking different coloured rectangles on a large rectangular white sheet. Each new rectangle covers something up, and what you have to do at the end of this is to figure out the visible colors and the associated areas.

My first thought on seeing this was - It's too easy! The most obvious technique is to have a matrix(read 2-D array) holding the colors of every unit square on the sheet. Initialize it to the sheet color to begin with, and overwrite the relevant sections with the color of each rectangle as it comes in. At the end of it, just iterate through the matrix and count the entries for each color.

I would have solved it right there - but with newfound wisdom, I looked at the constraints, and ruled out my solution - the sheet size can go up to 10000x10000...that adds up to a whopping 400 MB of memory! No chance there...

So I looked at their hint, and they said: only keep track of the rectangle bounds and chop up rectangles as new ones are added. Since there are only a maximum of 1000 rectangles - this sounded like a good idea. But how to chop up the rectangles? Figured that out yesterday - there's a neat way to do it by imagining that the new rectangle is completely inside the one you're intersecting with. Then just check all the newly formed rectangles and rule them out if they're not viable...Coding this is a little dirty, but I wanted to get it over with. Fate however, had other plans...

Ended up looking through the Java Collections framework for something useful to hold rectangles - started with an ArrayList and ran into a concurrent access exception. Briefly considered using some kind of Set, then gave up and used an array instead. Not as clean, but no concurrent access problems...

I submitted the solution - it barrelled through a couple of test cases. Then along came the killer - and my program produced some crap results...

So now we come to the central dilemma - how the hell do you debug something so damn ugly? I'm at sea...

Last night, after doing the Mumbai Mirror crossword, four words suddenly flashed through my mind - window to viewport transformation - straight out of Computer Graphics. And that gave me a way to use the original idea - why keep the whole sheet in memory? Instead, break it up into smaller sheets and only keep one in memory at a time. Apply the old algorithm in each case. Simplicity itself...

Coded it up last night and submitted - this one was much cleaner than the other one. It ran all the way through 10 test cases(and really fast too - 0.06 seconds was the slowest one), then failed on the 11th one - weirdly enough, it threw an ArrayIndexOutOfBoundsException at an index value of 1000...and there doesn't seem to be any way that my array indices can ever exceed 999...I fixed that up with a couple of half hearted Math.min()s...but the answer to 11 gets screwed up. To top it off, my IDE began doing weird stuff at the same time. At this point I gave up and decided to try my luck the next day.

Haven't really given it a try yet, though I did reinstall the IDE. Maybe I'll do the other 3 problems first - at least I'll learn some graph theory in the process...From what I've read on the net, I'm not the only one who hates Shaping Regions...

What really gets me is that I can't stop thinking about this damn thing - I have this way of spending an infinite amount of time trying to crack something interesting, but this is getting way out of line. It's not even difficult - but the bloody thing just doesn't work in one case!

Hopefully I'll get it to work...there's probably no way to get out of section 2 without finishing it...

The only other interesting piece of news is that my wisdom teeth are starting to give me trouble...one of them on the left side has begun to painfully lacerate the inside of my mouth.

Can't resist ripping off Confucius...here goes, with bad Chinese flavored English too:

Confucius say: If man know he grow wisdom teeth, he never bother to grow wise. This beginning of wisdom, and so he grow wisdom teeth anyway. When man realise this vicious circle, he become truly wise. But only when he have wisdom teeth removed do he become great sage.

Confusing? Try making sense of these Zen koans then...

Of Mindsport and other things...

A couple of weeks ago, one of my posts mentioned Mindsport, which for those who came in late, is a weekly puzzle column that turns up every Sunday in The Sunday Times. Anyway, the subject of my post was my sending in a ludicrously simple solution to one of the puzzles. Now every week the writer complains about people demanding that their solution be published, since they've sent in 3000 solutions already, etc...Apparently only a few make it to the actual column - not surprising, since it's so tiny.

Anyway, you can imagine my surprise when I began reading yesterday's Mindsport, and found a suspiciously familiar train of comments. Sure enough, there it was - my solution, along with my ranting that it was too easy, barely worth five minutes, etc...Wonderful - my first solution, and it gets published too!

For those who want the question, here it is:

Consider N chairs, numbered 1 to N, arranged in a circle. Two people, A and B, are initially in chair 1(don't ask me how...). At every stage, A moves 'a' chairs around the circle, and B moves 'b' chairs around the circle. How many moves before A and B end up in the same chair again?

It's fairly simple, took less than 5 minutes to work out...(Note to Sagar: This might be good practice for the CAT, provided you can work it out in less than a minute...Of course, they'll probably give you real numbers...)

Check out my solution in the Sunday Times if you don't get it...and if you don't get the Sunday times, drop me a line...

News Flash: Had my first bhutta(Corn on the cob, Indian style) for this rainy season...Yum!

Next up: solve the recurrence Q_n = (1 + Q_n-1)/Q_n-2, where Q₀ = α and Q₁ = β...Interesting, it repeats in cycles of 5...

For those greedy for more intellectual stimulation, here's a little variation on the Towers of Hanoi problem that I was working on yesterday: Move n disks from the left pole(A) to the right pole(B), but without direct moves between A and B. All moves must be to or from the middle pole(C). The layout is obviously A C B. As usual, larger disks cannot be placed on top of smaller ones.

Final verdict: Recurrences rock!

Follow the white rabbit...

Just finished reading Nick Bostrom's thought provoking paper - Are you living in a computer simulation? He makes a terrifying case for the possibility that we might be simulations in a computer run by our posthuman descendants. I didn't really take this possibility seriously until now, but his arguments are quite compelling.

Basically, he claims that at least one of the following is true:

1. A very small fraction of all human level civilizations eventually reach posthuman levels.
2. A very small fraction of all posthuman civilizations are interested in running ancestor-simulations.
3. The fraction of all people(real or simulated) with our kind of experiences, that are living in a simulation, is very close to one.

Excuse the mathematical style, but the argument hinges on a nice little equation, which produces these three possibilities. Basically, the gist of the idea is that a super advanced future civilization(the posthumans just mentioned) will have a mind boggling amount of computing power available to them. If they do decide to run ancestor sims, then chances are that there will be a much greater number of simulated ancestors than real ancestors. Thus it is overwhelmingly likely that we are living in a simulation rather than the *real* world...If this isn't the case, then chances are that very few posthuman level civilizations really develop, in which case we either die out, or fall back to primitive levels. Finally, it may be possible that posthumans simply don't want to run ancestor simulations. We can't say why this is so - trying to understand their intentions is comparable to an ant trying to figure out ours...Frankly, it's hard enough today to figure out the intentions of our elected representatives, let alone future humans with expanded minds...

Now here's a really interesting concept which most readers who survived the last paragraph should have seen coming - how do you know that the chaps simulating you are not simulations themselves? Their level of *reality* may just be another simulation run by an even more advanced civilization...and so on. Russian babushka dolls, anyone?

BTW, a really interesting take on this is David Brin's short story Stones of Significance. I highly recommend it.

Time to get back to Halo...

Down came the rain and washed the spider out...

As I mentioned some time ago, the monsoons have finally begun in earnest. In fact, for the last two days or so, it's been raining almost nonstop. This bugs the hell out of my sister, who has to go to college and coaching classes. Meanwhile, I can relax like the lazy bum that I am and spend all my time indoors...and watch the steadily growing puddle(about the size of a small pond) in front of the park outside. Thankfully the other half of the road is clear, so people can move around without trouble.

Yesterday a rather weird thing happened to my monitor - I turned it on and things were weirdly out of focus. Following the time tested First Law of Computer Fixes, I turned off the machine, jiggled the appropriate cables, and turned it on again. Presto - instant fix.

The same thing happened again today, and this time I fixed it with two restarts. Provisional theory: excess moisture content in the air is causing dew formation on the electron guns. The heat from turning it on is enough to fix it... Solution: stick silica bags around the monitor. Anyone else who has had this problem, drop me a line...

And now, on to cryptography and recurrence relations...

Me and my big mouth...

As promised, here's the lowdown on the TCS experience. It's just a short bit, as my posts go, but it should showcase my monumental foolishness wonderfully...

The entire recruitment process was divided into three sections: an aptitude test, a technical interview, and an HR interview. Most of my friends correctly predicted that the first two would be no trouble for me at all. Most of them also said something similar about the HR interview - and that's where the real interesting stuff happened.

Some background - at the time the HR interview took place, those who flunked the tech interview had already gone off home, and the rest of us were sitting and getting bored, waiting for the HR to start.

I got lucky - I was the second person sent in. There was a panel of two people, and they did the usual HR sort of stuff - questions that are obviously meant to see how well you'll fit into the company, work with a team, etc, etc...

Then the bombshell - "Any plans for further studies?"

Me: At some point in the future, perhaps. I'm thinking of picking up some experience first.
(Not strictly true, but not strictly false either...)

Them: Have you given the GRE?

Me: Yes. (Foot on an intercept course with mouth...)

Them: How much?

Me: (Foot enters mouth...) 1600.

Now unlike the tech guys, these chaps knew the significance of this kind of GRE score - plus the shock value of a perfect score is enough to grab anyone's attention. Consequently, the two chaps, who had showed no emotion whatsoever, suddenly seemed to become slightly more animated...

Then they began the usual thing - "So you'll definitely be going abroad then? After all, with this kind of score..." and I'm struggling to dance around the subject, equivocating like a politician.

They actually stayed on this subject for a few minutes. That should have tipped me off. No HR guy wants to get his company to spend money on a chap who is almost sure to be gone within the next 4 or 5 years at most - never mind attrition rates. My dad says this has something to do with not looking like a dumbass in front of your boss...

Should be obvious what happens now - at the end of the day, when they finally announced the people they'd picked up - I wasn't one of them. I had a sneaking feeling about this - one of the Electronics guys was talking to someone about how they'd grilled him about his sister being in the US. Stuff like "You can always go there now...what prevents you from going there to study..." and so on. If that was what they were thinking, no wonder I got eliminated. I suspect that a significant fraction of the people selected don't actually accept - under these circumstances it makes sense to eliminate anyone who has a good reason to reject their offer...

Looks like I'll have to learn to keep my big mouth shut, or rather, to lie with a straight face - I never brought up the topic - they asked me. If this is a common campus placement question, then the truth is one thing I can't tell them...

Impaled upon the sword of my own achievement - who ever said honesty was the best policy?

Moving on to more interesting topics - looks like I'm finally coming out of my TC rating slump. I passed over the 500 in favor of the 1000 this time(500 had a closed form combinatoric solution, which hit me in a flash of inspiration - about ten minutes after the match ended.), but for some odd reason, I couldn't get the 1000 pointer to work. The solution was perfect - but it just kept doing weird things. A little debugging showed that certain sections were seemingly not getting executed, but for the life of me I couldn't understand where the problem was...

I've actually had this kind of problem a couple of times before - something is obviously screwy, but you can't figure out what. The only solution I've found that works is to code it all over again. Never mind if it's identical - the second time it always works, and the first time it doesn't...

No points for guessing what happened when I rewrote the solution...

The interesting thing is that I finally made my first challenge - I've never challenged anyone's code before(25 point penalty if your challenge fails). This time I saw a solution that just had to be wrong, and pocketed 50 points.

Next SRM is more than a week away...better do some training until then...

The best laid plans of mice and men...

So there I was in the TC Arena, ready to attack the problems they threw at me, and tear them limb from limb. With my newfound ability, I was ready to destroy the opposition, jump to division 1, and maybe make the leader board...I was gonna kick ass.

Did it happen? Not on your life.

Instead, I came out of this SRM with my lowest score ever, and dropped to my lowest rating yet. To add insult to injury, it wasn't because I was unable to solve all the problems - I actually did all 3, including the 1000 pointer. Carelessness and stupidity killed the medium and the hard in systests, and sent me spiralling into the void...

The truly unforgivable mistake I made was the 500 pointer - under other circumstances I would have cracked it instantly. Instead of seeing the obvious solution, I came up with an ugly approach that eventually failed systests...Even worse was that it managed all three examples from the problem statement. What should have tipped me off was the inordinate complexity of the solution - no div 2 medium could be that weird. If I'd been a little less impatient, I'd probably have seen the obvious attack and been the first to submit a solution. Since I already had the first submission for the 250 pointer, I could have comfortably finished somewhere at the top, even if I didn't get the 1000.

The 1000 was really sad - the solution was correct in every detail. It just so happens that it took into account one extra item of input, and so returned 0 where it should have returned -1...I'm still surprised by the cavalier way in which I read the problem statement - unforgivable!

NOTE: I was gonna write a lot of stuff here, but I accidentally navigated away from the page and lost my post. No longer in the mood to rewrite everything, so the gist follows...

Here's a quote from Jonathan Livingston Seagull that perfectly sums up the lessons of SRM 247:

The gulls who scorn perfection for the sake of travel go nowhere, slowly. Those who put aside travel for the sake of perfection go anywhere, instantly.

It's about seagulls, but the symbolism should be obvious...

And here are a couple of guidelines I've come up with to improve my approach:

1. Never get caught up in the sheer excitement of your power, newfound though it may be. If you do, your delusions of grandeur will remain just that - delusions.
   
2. Forget details like timing, ratings and rankings. Focus on the problems - if you master those, all else will follow.
3. The point value is usually a pretty good guide to the difficulty level of a problem. If your solution seems overly complex by that measure, then it may be worth exploring alternative approaches.
4. Read the problem statement - pay specific attention to constraints and details - your solution may break if you miss something.
   
5. Forget about your speed of coding relative to other coders - just code. (This is properly a part of (2), but it's worth mentioning as a separate point.)
6. All this is easier said than done. Internalize it - reduce it to instinct.

Let's hope this works out - I'm getting rather tired of being a humble green coder...

*The writer suddenly experiences a moment of transcendental enlightenment.*

Hey, all this writing has suddenly made the true problem clear - in fact, it's summed up wonderfull by Morpheus in The Matrix when he tells Neo:

There's a difference between knowing the path, and walking the path.

For those who haven't understood this - you're either extremely dense, or I'm not a very clear writer. Either of these is possible, but I lean towards the former...

I have a feeling blogging has actually improved my coding and problem solving ability - presumably because it helps identify problem areas. And of course, writing stuff down cements your understanding of it.

Okay, time for other news - I have TCS placements tomorrow. Unfortunately, this means we have to go over to RAIT in Nerul, and rather early in the morning. Huge pain, but no choice...

There's been an ugly side to this recruitment thingy - the form they've put up on the website for campus recruitment registrations - it's a sort of resume - it's a marvel of bad design. Rather surprising, considering the size and quality that TCS is known for. It has serious compatibility issues with Firefox - you can't see the cursor - stuff is rendered in grey...not exactly a good intro with all the techies using Firefox these days. When I finally got around to opening it in IE(yecch!), it turned out to be weirdly set up - all sorts of useless details were mandatory for submission, and there were unexpected maximum size restrictions on some fields as well. I suppose 'campus recruitment' is a fairly wide ranging thing, involving people who haven't yet graduated, those who are just out of college, and postgrads as well - so you can chalk up the useless details to that aspect. Still, if anyone from TCS happens by, please tell the guys in charge of the website to fix it...technical incompetence from such a reputed company is a real turnoff.

I suppose that's it for now. Will blog about the TCS experience tomorrow or day after...

The monsoons make an entrance...

Looks like the rainy season has finally begun in earnest, announcing its presence(to me, at any rate) with a thunderclap so loud that it seemed to come from right outside my window...The rain started a few minutes later, and for the first couple of minutes, the word 'torrential' would have been an understatement...

Mumbaikars have a weird love-hate relationship with the monsoons - on one hand, they welcome them as salvation from the inhuman humidity of May, and on the other, they curse them when the streets begin flooding up and staying dry becomes a virtual impossibility. And yet, year after year, I see dozens of people in college fleeing without any kind of protection. I neatly avoid this problem by tossing my umbrella in my bag at the first sign of rain, and keep it there until the monsoons are long gone. The last part isn't really caution, just laziness...

On the algorithms front, the TC arena is working again, and I did manage to solve the 1000 pointer in the practice room. Once again I was a little astonished by the ease with which I did it. It was a simple brute force attack which involved generating subsets of the input, but the way the solution just seemed to develop itself was unbelievable. This might have something to do with the fact that I've really got the hang of recursion now. After I solved it, I was going through the match editorial to see their solutions, and I saw the magic word 'bitmasks'.

For seasoned algorithms people, this doesn't hold any mystery, but this doesn't apply to me. I've been seeing this word on and off for a while in the match editorials, but I never really knew what it was. Most statements I've seen were of the form, "$CoderName wrote a nice solution using bitmasks." Back then I never had much time to follow them, and somehow I came to the conclusion that a bitmask was an array of booleans...not sure how that happened...

Anyway, I finally found out that a bitmask was a single number whose bits you wanted to piddle around with. Since I'm rather fascinated by the way binary numbers fit into all sorts of mathematical applications, I had to take a look. Turns out there's a nice iterative way to generate subsets by simply incrementing an integer and looking at its bits. I'm surprised I hadn't thought of that, since I've always noted the neat way in which binary numbers count up...In fact, the solution is far cleaner in this case. Generating subsets involves choosing whether to include an element or not, so you have to divide and conquer - include in one recursive call, exclude in another. With bitmasks, all that is handled implicitly by incrementing the counter. The 1's and 0's manage this perfectly.

This abstraction seems a little superior to the recursive one - though the recursive one shows you the choice explicitly(which you might want - though I don't see why), the bitmask implementation handles all that without you having to bother - which in the end is what an abstraction is all about - hiding the fancy details. Plus you don't have the overhead of recursive calls, which doesn't hurt either...

Now to sit back, eat, enjoy the cool weather, and learn flood fill algorithms...

Life goes on...

It's been a couple of days since I last posted - fairly eventful days actually...finally got down to doing some USACO algorithms training now that the vacations are on. Just finished off section 1, and the good news is that I've improved spectacularly. I've been musing on what caused the sudden improvement, aside from high spirits due to sudden influx of freedom into my system...

It's so much better than intuitive hacking, where all you really do is think about the problem until you get ideas, which you then have to think about implementing...Algorithmic programming expands your perspective hugely. Earlier I would have thought something like, "This looks just like that one I did earlier..." Now I think, "Hey, depth first search with memoization!"

What amazes me the most is the way a few simple abstractions clean up things - naturally, you expect them to simplify stuff - that's what they're there for - but you don't realize the true extent of it until after you've internalized the concept and put it to use in a problem solving situation. Unbelievable...

Just tested out my improved skills in the TC practice room(SRM 153, div 2 in case anyone's interested). Finished off the first two probs with no difficulty at all. Was about to start on the 1000 pointer - the real challenge - but something went screwy with my connection, and now I can't get into the applet long enough to see the problem statement...Just my luck. Ah well, I'll give it a whirl before tomorrow's match...I'm planning on solving all three this time - but let's face it - my new skills are limited to a few new abstractions related to search problems - I haven't had time to do much graph theory, and haven't reached dynamic programming yet. My rudimentary skills with those two might be my downfall in the third problem...and let's not even start about computational geometry...

Looks like Kill Bill 2 is on tonight...missed it during the exams, so looks like it's katana time! Might catch Fist of Fury too, just to pass the time.

Fabulously rich...NOT!

As my last post might have mentioned, I had a little meeting today with my GRE prof. Turns out he was making good on the promise he'd made during all his seminars - the first of his students to get a perfect GRE score wins an all expenses paid trip to Goa! Since yours truly managed to get lucky(damn I'm good!), the Goa trip was mine!

By now, anyone who knows me is thinking, "Nadeem in Goa? Have unicorns been spotted walking the streets of New York?"

Let's face it - I'm one of those people for whom Goa doesn't hold any real attraction. My idea of a fun place is probably the Googleplex...anyway, since this was the case, I ended up with a check for Rs. 12000...Whoopee!

OK, cancel that. The truth is, I'm not gonna be using that money for anything fun...It's all gonna go towards registering for the CompSci GRE and the TOEFL, so my poor pals aren't gonna receive a treat(though they've been begging for it like hungry dogs...).

The other interesting thing is the formation of a little study group for the CS GRE...my prof has decided to form a little group of 10-12 students, who'll learn all this stuff together and teach each other. Guess who's in on the fun...For more details, you might want to see http://www.kiceducation.com. And the fact that there's a bad photo of me plastered on the front page has absolutely nothing to do with this...

Other than that, today was rather eventful - I did a couple of interesting coding problems and kicked up my algorithmic skills a notch. Still stuck on one - surprisingly, it's not the algorithm that's giving me trouble, but the implementation...coding up all the fancy abstract actions with which I conceived the solution is a doozy. That's rather odd, since it's a greedy algorithm, and those are usually pretty simple to code...

Still, I'm looking forward to the next TC match on Saturday. All the stuff I've done should stand me in good stead. By then I should have got a lot more practice in, too. Maybe now I'll be able to get out of division 2 permanently...

Back to discrete mathematics - counting was never so much fun!

PS: BOFH has been updated! And all this time I never noticed...shame.

Back again...

Got back from our weekend trip to Pune a few hours ago. Pretty ok, as trips go - especially since we took one of the airconditioned Volvo buses back and forth. Did some interesting reading en route - and actually solved a couple of TopCoder problems from the last SRM(which I sadly missed).

Unlike some places I've been(like Lucknow - blech!), Pune has a lot of stuff to read - my uncle has a Ph.D in Geography, so National Geographic is all over the place, plus other stuff. I lugged over three books to be on the safe side, but thankfully there was no trouble on that front.

The real trouble was the lack of computing support - halfway through the stay I had already begun to experience acute withdrawal symptoms...

Also got a call from my GRE class - have to go over tomorrow for something to do with CompSci GRE that I plan to give. Looked that up a while ago - except for software engineering stuff, all the stuff covered is related to what we've already done in college. Nothing surprising there - the design of our syllabus is perfect - it's the implementation that fails miserably...Anyway, the test is multiple choice, so no need to sit and cram - I've made a point of absorbing most of that sort of stuff anyway - it's the useless details that kill me...

I suspect the real challenge for MU students will come in the mathematical background that they expect us to have - our computer engineering and IT courses don't emphasise it to any great extent - and the maths that we were taught was almost completely unrelated to computing. Thankfully I've already begun a program of increasing my skill in algorithms, discrete mathematics, problem solving, data structures, and so forth...

So here's my itinerary for the vacations:

• Go through all the stuff we've learnt over the past 2 years(First year was a complete waste) and absorb the stuff that really matters.
• Pay special attention to the mathematical aspects. This should be no trouble - TopCoder will take care of algorithms, data structures, complexity, and discrete mathematics.
  
• Start hacking Greasemonkey.
• Do some more Python - in particular, learn some of the libraries so I can do advanced stuff.
• Read like blazes.
• Do puzzles and problems, and actually generate new problems if possible - this skill comes in real handy, and cements understanding.
• Last but not least - watch Revenge of the Sith, Batman Begins, Kung Fu Hustle, and so on...

All this business about generating problems reminds me of a certain thing from Dune. For those unfortunates who haven't read this magnificent saga, here's a little background. The thing I'm talking about involves Mentats - human beings with minds trained to the greatest extreme so they can function as computers. Back story - all thinking machines were outlawed after humans defeated a bunch of AIs that had enslaved them for generations. Since people still felt the need for computational help, the order of Mentat was formed...All this is set in a general atmosphere of humans forsaking a lot of technological help and developing their own capabilities...

Anyway, the thing I'm talking about has to do with a certain attitude that Mentats adopt. This quote from Chapterhouse: Dune should be a good introduction:

Mentats accumulated questions the way others accumulated answers. Questions created their own patterns and systems. This produced the most important shapes. You looked at your universe through self-created patterns -- all composed of images, words, and labels(everything temporary), all mingled in sensory impulses that reflected off your internal constructs the way light bounced from bright surfaces.

Notice the bit about accumulating questions. I think it's true that most of us go through life gathering answers - not many of us consider shifting focus to the questions instead. Indeed, such a shift might really shake up one's mental moorings. Everything would take on a temporary flavour - every fact would be reduced to the status of 'the current answer' and few absolutes would remain. Dune actually cautions against absolutes - adherence to too many absolutes can cause terrible problems in the long run...

Here's a little bit more on Mentats from the same book - the person mentioned in it is Duncan Idaho, who received Mentat training in several incarnations, and gained access to his old memories and training in the last book:

A Mentat's real skills lay in that mental construct they called "the great synthesis." It required a patience that non-Mentats did not even imagine possible. Mentat schools defined it as perseverance. You were a primitive tracker, able to read minuscule signs, tiny disturbances in the environment, and follow where these led. At the same time, you remained open to broad motions all around and within. This produced naivete, the basic Mentat posture, akin to that of Truthsayers but far more sweeping.

"You are open to whatever the universe may do," his first instructor had said. "Your mind is not a computer; it is a response-tool keyed to whatever your senses display."

The fleeting, ephemeral nature of a Mentat's world view is captured here:

Doing this, you never thought of yourself as clever, that you had the formula to provide the solution. You remained as responsive to new questions as you did to new patterns. Testing, re-testing, shaping and re-shaping. A constant process, never stopping, never satisfied. It was your own private pavane, similar to that of other Mentats but it carried always your own unique posture and steps.

"You are never truly a Mentat. That is why we call it 'The Endless Goal.' "

And in conclusion, one of my favourite parts:

A Mentat came at his universe fresh in each instant. Nothing old, nothing new, nothing set in ancient adhesives, nothing truly known. You were the net and you existed only to examine the catch.

I'm thinking about twisting my consciousness into this mold. Wonder if it's humanly possible...The image of an annoyingly precocious kid asking "Why?" at every opportunity comes to mind - only now, the kid is in your own head, and the questions aren't as limited.

The kid metaphor actually has another important characteristic - the famous Mentat naivete. That is the real challenge - throwing away preconceptions and older knowledge, and developing a sense of idealism that we lose all too easily today...As the Mentats learn, it isn't old age that prevents learning, but an accumulation of "things I know."

Socrates would have loved this...

That's about it for this post. Confusion to your enemies...

PS: The 'the' experiment - see previous post - turned out as expected. The posting was named blog-post.html.

This says it far better than I ever could... 

the

If you happen to be one of those hawk-eyed readers they talk about, then you'll have noticed the rather interesting title of this post. Before you give in to the impulse to instantly scroll down and post a dozen comments on this subject, you might wanna read the explanation below...

Some time back, an interesting chain of events transpired, with the result that I began to notice the filenames that Blogger gives my posts. For example the URL of the post that brought this to my notice is http://abstractwhiz.blogspot.com/2005/06/i-can-see-finish-line.html. For nontech readers, the thing I'm talking about is the bit after the last slash. Apparently they took the title of my post, cut it down to lower case, stuck '-' characters between the words, and(this is the most important thing) removed the word 'the'. A little study of the previous posts showed that this is normal policy.

It should be obvious where I'm going by now...If all 'the's are removed, what happens when the title is a big fat 'the' itself? I don't have any idea now, but I should know once I publish this post.

Since we're on the subject of definite articles, I have to mention an interesting phenomenon. For some reason, Indians have a huge amount of trouble with 'a's and 'the's - the latter is especially misused left and right. I once had a prof who could not string a sentence together without using 'the' at least 3 times. At least two of them would be wrongly used, and that was on a good day...There are rumours that he once used over a thousand in just half an hour. Example: "Why for you are the late? Is this the time to make the entry in the class? You will find the great difficulty in the exam..."

We waited for an entire year to hear him say "Get the out." Sadly it never came. Sigh....

The other extreme is represented by a guy who taught me Marathi back in school. At one point he was explaining some sort of passage in which some guy picks up a grain of rice. His translation: "He picked up a rice." WTF?!!!

Then there was the other guy who taught me maths and never pluralized anything. When he wanted a bunch of people to stand up, he would say "Stand up boy." In fact, his entry into the class went something like this....

Him: "Stand up boy."
(We stand up)

Him: "Say good morning boy."
(We resist the temptation to say "Good morning boy" and manage a weak "Good morning sir")

Him: "Sit down boy."
(We sit down and start hunting under our desks for pens that have *accidentally* been dropped. An observer with good ears might have noticed the faintest sound of stifled snickering from beneath the desk. Why this observer would be in a seventh standard maths class, I cannot say.)

There was an interesting incident when he caught some guys chatting nineteen to the dozen while he was trying to teach us congruence of triangles. This is what happened:

Him: "You boy, get out."
(One of the culprits sheepishly slinks out. He seems almost happy...)

Him: (to another of the offenders) "Why are you still here? I told you to get out."

Offender: "Sir? I thought you were talking to him."

Him: (roaring with rage) "I was talking to both of you! And that fellow behind you - both of you boy, get out!"

(The proceedings are interrupted by someone who can no longer take this and gives a devastatingly loud SNORT! Thankfully he manages to convert his guffaws into hacking coughs just in time to avoid detection...)

Of course, once you could translate his *singular* argot, he wasn't a bad teacher after all...

This isn't entirely restricted to non English speakers. My 10th standard geography teacher, who certainly never spoke a word of anything but English, once said "Please may I have the this?"

And to top it off, I myself am not immune to the odd attack of linguistic ineptitude...

Ah well, off I go to mess around with union-find algorithms...

Current browser name: Mozilla Seaturkey.

I can see the finish line!

Just one more exam left, and I'll be a free man once again! Free to waste my time, sleep at odd hours, hack all day, watch a bunch of movies, read some more books...the list goes on.

Thursday evening is when I'll finally be able to start doing all these things - once Computer Graphics is over. I suspect Thite and Sagar will probably produce a blog post each(at least if Thite's exams end tomorrow too....). Looks like I'm the only one who blogged during the exams (and produced my biggest post yet!).

Before I forget again, this is for my uncle in New Zealand - Happy Birthday! Forgot to put this in earlier, but since he's one of the most avid readers of my blog (he says it's his homepage at work!), I had to do something...Family record: First person in the family to get wished on a blog! Of course that makes me the first person in the family to wish someone on a blog...What the heck, it sure beats searching for ecards online...

Seriously, whatever happened to the times when free ecards were all over the place? Nowadays, you surf over to any of the *free* sites and all you get are a bunch of substandard cards. The good places which used to be free (BlueMountain!) are all paid sites now. This sucks...

Just noticed a tiny moth sitting on the wall of my room. Can't resist painting a picture of my sister's reaction...

Me: "Check out that moth on the wall...."

Sis: "EEEEEEEEEK!" (flees in terror...)

(Reappears ten minutes later at the door peering around anxiously)
Sis: "Is it gone yet?"

Me: "Nope, but it's not even a moth, just a butterfly without the usual Nerolac color scheme...Oh look, it's on the curtain right next to you!"

Sis: "EEEEEEEEEK!" (flees once again)

The day usually ends with her demanding that I kill it, or catch it and throw it out or something...

Incidentally, what is the difference between a butterfly and a moth anyway? Anyone in the know, drop me a line...I'm feeling too lazy to search around...

Time to chow down. Expected time of next post: Thursday evening.

Current browser name: Mozilla Powerape!

Home stretch

Looks like my ordeal is almost over. Two more exams to go, and the first of those is only about14 hours away. Then it's one last day of studying, followed by the last exam, and then - freedom!

To my complete lack of surprise, I find my mind brimming over with ideas on stuff to do in the vacations - and for once, they're all unbelievably geeky, involving lots of coding, mathematics and puzzle solving...Looks like my True Self(see Heretics of Dune - Miles Teg's training on Chapterhouse) is awakening. Long overdue, but since most major evolutionary jumps in my life seem to come a year or two after those of my contemporaries, that's about par...

Naturally I have to try and control myself - don't want to mess up these last exams just because they're so close to the end. I already have a feeling that I haven't really done enough for OOAD, but thankfully our teacher grilled us on that quite well. At least some of our teachers are really competent...

Better buzz off to bed now - plan to get up early and do some studying. The weirdest part is that you can actually bone up on the entire theory section pretty fast. All you have to do is learn to see past the repetitions. So if I wake up at around 8, I should be able to bone up on the remaining fancy theory, cast a practiced eye over the diagrams, turn on my MeaninglessParagraphGenerator^TM, activate the NearlyEndlessRepetition^TM module, and we should be all set.

Off to rest the mental circuitry - next post probably due tomorrow night...Stay tuned.

Halfway through...

This just in - the exams are officially half done. Three more and freedom will be mine! In fact, I'm only really concerned about the next one (Operating Systems) - the remaining two aren't exceptionally large or difficult to remember.

I was considering ranting a bit about our OS syllabus, but on second thought - forget it. Suffice it to say that we, who should properly have been trained on BACI and Nachos, are reduced to memorizing useless facts about modern operating systems in the guise of so called "case studies."

Back to more(or less) mundane things. Interestingly, I've actually read two books during the exams - Eragon by Christopher Paolini and Trickster's Choice by Tamora Pierce. Brilliant pieces of work, both of them. I'm rather looking forward to reading the sequel, since both are parts of trilogies - the Inheritance trilogy for the first, and Daughter of the Lioness for the second. Looks like my taste in reading now incorporates fantasy as well. Not that that's odd for a hard core SF fan - the two go together quite well - that's why it's often called SF&F.

I remember someone once asking me why I read so much SF when they were so many other good books around. I don't recall having much of an answer back then, aside from "It's interesting!" A couple of days ago, I remembered this incident, and then a little thing I'd read in an interview of Marvin Minsky.

The interviewer asked Minsky what kind of books he read, and his response was "Aside from technical literature, only science fiction." When pressed a bit, Minsky remarked that all other types of literature were horribly cliched - they've all been done thousands of times over. It really isn't worth reading anything except SF, simply because it's the only truly original genre of literature around.

This idea wandered around in my exam addled mind for a while, and eventually connected with another one(yes - my mind really does work this way - and so does yours...maybe), which at first sight seems rather antithetical to it. It came from a small article I'd read about Frank Herbert - the guy who wrote Dune. His greatest insight - and the reason he revolutionized SF forever - was to realize that SF wasn't the newest of literary genres, but the oldest. It's just a modern repackaging of the oldest type of story around - the fantastic tale. Remember all those old myths about gods and heroes and dragons, with wizards and witches tossed into the mix? Guess what - it's SF! The Ramayana and Mahabharata - SF! Homer's Iliad and Odyssey - SF!

So that's why SF appeals to people - because it stirs ancient memories of tribes gathered around the campfire, listening to the storyteller. Dune fans - doesn't this sound oddly familiar?

Looks like it's time to get back to work now. Loads to do, and miles to go before I sleep...

PS: Current browser name - Mozilla Seajaguar.

A brief respite...

This little post is meant as a bit of a break for me. Systems Programming is as devastating as always, and having to cram it into one's head in a single day is not a feat to be taken lightly. Anyway, the story so far: exams are on in full swing - 2 down, 4 to go. The exams themselves aren't that bad - it's the mind numbing drudgery of studying for them that gets you. After that, it's all autopilot really. Over 10 years of doing memory intensive exams like these does that to you. Probably a subconscious defense mechanism designed to protect more important areas of the brain...

And now the part we all love, Firefox extensions! Whoopee...

Epsum factorial non deposit quid pro quo hic escorol. Olypian quarrels et gorilla congolium sic ad nauseum. Souvlaki ignitus carborundum e pluribus unum. Defacto lingo est igpay atinlay.

Before you start trying to translate that, a word of advice - it's just gibberish. Part of this cute little Firefox extension called the Lorem Ipsum Generator. Not exactly useful, but then computers were made for goofing off anyway...

In the same spirit, another interesting extension is the hilarious Firesomething . This little piece of work generates a new browser name every time you open a new window. Which is why I'm currently typing this in Mozilla Hypnosalmon...

People with an overdeveloped aesthetic sense, Nuke Anything is just for you. With this little baby you can remove annoying objects from pages - kill ads, revolting graphics, or just manifestations of really ugly design...In case you get the wrong idea, this doesn't *really* change the page, just your view of it. So don't yell to everyone, "I deleted the Google logo! Come and see!" Sorry chaps, you'll need to learn how to hack for that...

If you're anything like me, then you have music playing while you're surfing, coding, studying or just messing around. FoxyTunes gives you the power to control your favourite player through Firefox, via this little toolbar that appears in the status bar at the bottom of the screen. Of course, the toolbar is only for novices - the true geek will only use keyboard shortcuts!

Note to those who're falling over each other to download it: You might want to reconfigure the default shortcuts - some of them interfere with the kind of keyboard work you do while typing into text areas(like when you blog).
(PS: If you aren't the kind of person who can select multiple lines of text using the keyboard, this preceding warning does not apply to you.)

Time for me to get back to studying. Feeling nice and refreshed now...Macro processors, here I come!

BTW, I recommend Yanni's Flight of Fantasy and Swept Away while studying. No words to distract you, and a superbly measured dash of optimistic elements to keep your spirits up. Hats off to the master...