Sunday, December 21, 2008

My match with Vishwanathan Anand


On the sidelines of the PanIIT Alumini meet being held at IIT Madras, Vishwanathan Anand - World Champion of Chess put in an appearance and played 14 boards of chess in a rapid mode of play. This was the sequence of moves played at table 4 by Narendranath (a 2000ish rated player and captain of the IITM chess team whom I met while playing chess at the InterIIT sports meet held earlier). It was real fun. Have a look.
White: Vishwanathan Anand
Black: Narendranath (IITM)/Divye Kapoor(IITR)

1. e4 c5      ; Sicilian Defense
2. Nf3 Nc6
3. Bb5 a6     ; push the bishop
4. Bxc6 bxc6  ; have a doubled pawn
5. O-O d5     ; try opening the doubled pawn
6. d3 Bg4     ; try pinning the Knight
7. h3 Bh5     ; push back the bishop
8. Nc3 d4     ; push the Knight and block the center
9. Na4 b3     ; Knight threatens entry
10. Bg5 h6    ; Push the Bishop
11. Bxf6 Qxf6 ; Bishop v/s Knight exchange
12. g4 Bg6    ; Break the pin on the Knight
13. Kg2 h5    ; Support the white pawns
14. g5 Qf4    ;
15. Qd2 Qc7   ; Push back the Black Queen
16. Nh4 Bh7   ; Push back the Black Bishop
17. f4 Bd6    ; Develop the Black Bishop
18. Nb2 Kd7   ; Break Black's Castling
19. Nc4 Raf8  ; Bring rooks into play
20. a4 Qb8    ; Start supporting the White Knight at the hole at b6
21. a5

Match abandoned due to lack of time.

Tuesday, November 11, 2008

Is Heysan.com a clickjacking attack, virus dropper or something else?

For those of you who have been regularly using GMail, the recent arrival of unexplained chats from your friends might have piqued your curiosity. A chat lands up in your GMail Inbox claiming to have been sent to you by one of your friends bearing some sort of cheesy one liners and that you should click on the link to view them. Something like this:

Though usually I'm highly suspicious of these sorts of clicks, I went ahead and clicked it. (After all, Firefox, my favourite web browser has quite a decent track record as far as security is concerned).The site that opened up looked like:
Now, I'm not going to be giving up my Google Account password to any site that just asks for it. No Way! Not a Chance! Not even if it boasts of the Google Talk logo. But then, there are all kinds of people in the world and some are likely to enter their Google ids and passwords due to ignorance. In my opinion, this site is a fraud that is directly and obviously obtaining access to userids and passwords of GMail accounts and using them to perpetuate a mass mailing campaign from within the comfortable confines of your GMail inbox. The fact that there exists a hidden link to admob.com (a highly SEOed advert site - see image) by means of a 1px x 1px image, bolsters my gut feeling about this site. Beware all of you who get a link to heysan.com - I think that its just the tip of a very large iceberg. Recent reports of a click based vulnerability in all browsers is a further cause for tension. Be on your toes everyone! More information on clickjacking is available here.

The hidden links on the GTalk page is:
And the heysan.com home page looks like this:
All links on this page lead to login areas of different popular e-mail and IM sites. So beware the casual web surfer: this does not augur well for the web. Currently, the best known safety solution is to install the NoScript addon for Firefox and use it to disable iframes.

Friday, October 10, 2008

Permutations of a string containing duplicates (C++ Version)

Update: This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See: Recursively printing all permutations of a string containing duplicate characters.

Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not).

int dup_permute(char *str, size_t length) {
    int count = 0;
    std::sort(str, str+length);
    do {
        ++count;
        cout <<  str << '\n';
    }
    while(std::next_permutation(str, str+length));
    return count;
}


Of course, since the major work of this function is being done in the C++ standard library, an explanation of the standard library functions is in order.
First up is the std::sort function. Located in the <algorithm> header, true to its name, it sorts the given range of elements (in this case the string, specified by pointers to its first and last elements). std::next_permutation is a tough one to deal with. The working of this function is too convoluted to explain in a couple of sentences, so, I would recommend you look up this reference and this MSDN article. In short, next_permutation generates the next lexicographically ordered permutation of the given elements using no more than a constant amount of extra space. All that work is done using comparison, swapping and reversing a subset of elements in the array itself. Also, since there is no copying involved, this function is blazing fast. So, the next time someone asks for all permutations of a string, forget about recursion and look at this iterative version. Not only is it correct for the distinct elements case, it works even when the string does contain duplicates. If you liked it, don't forget to leave a comment.

Wednesday, September 17, 2008

Selected!!!




After 5 hours of mind wrenching tension and reams of code later, I've finally been selected for the internship programme at the Microsoft India Development Center (better known as Microsoft IDC). The internship is going to last for atleast 8 weeks and I'll be getting accomodation for 15 days and travelling expenses in addition to my internship stipend. Looking forward to going to Hyderabad, anybody going to meet me there?


The 'Said' Problem

I came across this cool piece of text on a patents website.

"The computer-readable medium of claim 23 wherein said workspace is used by a database system to create a plurality of run files, each of which contains a plurality of variable length records from said set of variable length records, as sorted by said database system using said workspace, said step of selectively removing comprises writing a next of the plurality of variable length records that are stored in said workspace out to a run file in a predetermined order, said method further having computer-executable instructions for performing steps comprising:
determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace;
creating one or more run files on a data storage medium; and writing out to said run file only those variable length record selected by said step of selectively removing subsequent to determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace. "

Now we know why we need lawyers for legalese, don't we? ;-)

Monday, September 08, 2008

Easter Egg in Google Chrome

Try typing about:crash in the title bar of Google Chrome and see this cute cross eyed robot! :-)
Of course, you do know by now that Chrome is hottest new entrant on the browser block, don't you? Well, now you do. :-D

Have a look at this review of Chrome on ZDNet.

Saturday, August 02, 2008

in.com - India on the world stage

Its rather rare that you come across a site with content really geared towards Indians with a look and feel matching any world class website. Take a quick look at the layout and source code of sites such as CNN-IBN and Aaj Tak and you will realize that we are really retards as far as decent site layouts and navigation is concerned. However, in.com was a really refreshing change. The interface is quick and snazzy and the site runs on blazing fast servers - in fact, I would go as far as to state that I had a better experience with their quick registration and speedy interface than I had with GMail on Google servers. Oh and just not to forget, they've gone onto internet overdrive and I'm constantly receiving targeted ads that lead me to their site. Well, what can I say - you have me hooked! :-)

The first thing that I tried out was their radio service - its awesome! Have a look at the screenshot below:

Despite it being an obvious ripoff from last.fm, I really don't mind. They've got more Indian songs in such an accessible format that it took me less than 10 seconds to start listening to Kabhi Kabhi Aditi. The best part of it is that its free and delivers songs on demand and their Bollywood song collection beats the living daylights out of any other service on the internet. Thats not to say that they are lagging in the english songs department - there's plenty of fare for all metal and rock addicts. A point to note is that I did not receive any lag while switching songs and there were no annoying "buffering..." issues. A quick traceroute showed me that its because they are hosting the site on dedicated servers on the VSNL backbone. That gives a really stellar experience for Indians. All that money that's gone into making the site is really being spent intelligently.

The mail was not bad at all - a complete GMail ripoff - right down to the drop down contacts list. Have a look:


The cool colour combination, the smooth fonts and especially the news and radio services makes me feel that I'll be visiting it much more often. Also, the short and sweet id I registered for - divye at in dot com is the icing on the cake. I loved their service and if you are an Indian (or even otherwise), you will too. So, what are you waiting for? Rush!!! Go (listen to) Talli on this site ;-)

Thursday, July 31, 2008

Enjoy Everything You Do

Live the life of a dolphin,
Travel the world without fear,
Whether to the top of a mountain,
Or where the water ain't clear.

Fear not to push the ceiling,
Try to reach for the sky,
Go with the flow if you want to,
Or be left high and dry.

Speak your words with feeling,
Enjoy everything you do.
Play from dawn to the evening,
Is that not everything you do?

Follow the world in its footsteps,
Or make the world follow you.
Do everything with feeling.
Enjoy everything you do.

Bird of Fire

Fly, Fly, Fly little bird in the sky.
You own the heavens - the Earth and the Sky.
Lie, Lie, Lie, asleep in the clouds,
Free from cares, from worldly bounds.
You creature of mirth, of joy abound.

Live, Live, Live, a life full of dreams,
Unchecked by dearth of form or means.
Pray, Pray, Pray for a life full of song,
For finding a rhythm to play along.
You creature of milk, to heavens belong.

Say, Say, Say, the words in your heart,
Bring a smile with a kind remark.
Day, day, day a day in your life,
Opens a door from formless night.
You warrior of words, of shape and light.

Inspired by - To a Skylark by P. B. Shelly

Monday, July 21, 2008

Wordle and SEO


An image is worth a thousand words. This image is a tag cloud
generated by Wordle from the text at
http://www.drkapoorsclinic.com . I don't need to tell you
how such a map is helpful for SEO - do I?

And yes: despite my earlier post on Mac v/s Vista - that *is* a screenshot taken from my laptop running Vista. You might call me a hypocrite, I just call myself a pragmatist - if you can't beat 'em, join 'em. ;-)

Friday, July 18, 2008

Walking through your first template metaprogram in C++

From the Wikipedia article on Metaprogramming:
Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data, or that do part of the work at compile time that is otherwise done at run time. In many cases, this allows programmers to get more done in the same amount of time as they would take to write all the code manually.
Unfortunately, metaprogramming is not directly supported by C++ and resources on template metaprogramming are few and far between. I'll try to document my knowledge of metaprogramming as I learn it and hope that it proves useful for one such as myself hunting the web for information.

First, lets get the preliminaries out of the way:
  1. Templates are used to create generic code (but you already know that, don't you?)
    Code like:
    template<typename T> std::string to_string(T const & object) {
    return object.to_string();
    }
    is used to allow the to_string function to be called on all objects that have a to_string() member function.
  2. Template specializations are created to handle certain datatypes in a special manner (or in technospeak - to provide a custom instantiation of generic code)
    So, code like:
    template<> std::string to_string<int>(int I) { std::ostringstream o; o << I; return o.str(); } ensures that calls to to_string that take an int for a parameter will use the second definition of to_string and not the more generic first definition. This allows us to provide a string representation of an int even though it does not have a member function named to_string. Thus, the body of a templated piece of code can be changed completely from its generic counterpart in a template specialization.
  3. The compiler always chooses the most specialized definition of a function. This is somewhat akin to function overloading. So, given a choice between to_string<t> and to_string<int>, it will always choose to_string<int> for an integer parameter.
Well, how does all this help?
It allows us to do a compile time recursion and that's what I'm going to show you.

Look at this piece of code:
template<int N>
struct factorial {
static const long value = N*factorial<N-1>::value;
};

Doesn't that look dandy! Its that same old factorial function again! So, what's new? Firstly, notice that instead of templating the structure via a typename, we have chosen to template it over a compile time constant. So, creating an object of this structure will require code such as:
factorial<5> five_factorial;
But why would you want an empty object? Remember: static structure and class variables do not occupy any space in objects and factorial<N> has only static members. So, what's the use of the static member?
The static member allows us to directly access values that are calculated at compile time. In essence, you can think of it as the return value of the computation. Before we move further into the analysis, let me answer a couple of questions that can arise:
  • Where's the computation taking place?
    • It is taking place at compile time when the template is initialized/instantiated and its being done by the compiler while the templated code is being compiled. Effectively, the compiling process is the runtime for template metaprogramming.
  • Where's the recursion in the code?
    • The instantiation of factorial<N> requires the value of factorial<n-1>::value which is of-course a static member in factorial<N-1>. So, this template is also instatiated and the recursion takes place.

Sharp programmers might have noticed that there is no base case in this piece of code: You're right!
So, here's the base case:
template<>
struct factorial<0> {
static const long value = 1;
};

So, when the compiler tries to instantiate factorial<1> and comes across factorial<0>::value, it will choose this base case and terminate the recursion. Once all the constants have been determined, they are multiplied by the compiler and the result is stored in the resulting executable. So, the value of 5! can be used at runtime without any computation of any sort, all it requires of you is to substitute factorial<5>::value wherever you need it.

A side-effect of this evaluation is that all lower factorial structures are also instantiated. Thus, when you instantiate factorial<5>, you get for free the values of factorial<4>, factorial<3> etc. Also, use of factorial<4> later in the program will not cause additional template instantiations because C++ compilers follow a single template instantiation rule: viz. no template will be instantiated more than once. This allows for a very important optimization: memoization that's right memoization and not memorization (though the two are pretty similar). You can have a look at the Wikipedia entry on memoization for info, but for the impatient, it allows you to code a fibonacci number generator like this:

template<int N>
struct fibonacci_term {
static const int value = fibonacci_term<n-1>::value + fibonacci_term<n-2>::value;
};
template<>
struct fibonacci_term<1> {
static const int value = 1;
};
template<>
struct fibonacci_term<0> {
static const int value = 0;
};

If you had coded an analogous recursive function for evaluation at runtime, you should have been spanked by your computer science/engineering professors because that's the worst way to evaluate the fibonacci series as it has a time complexity of O(2^n) which is exponential in the size of the problem. However, because of the one template instantiation rule, its perfectly alright to do this at compile time. While evaluating fibonacci_term::value , the compiler has already instantiated fibonacci_term and that instantiation is simply looked up from a table, thus saving computation time and making the compile time program linear in time and space complexity.

Meta-programming is not just about compile time computations and tricks like this. Its far greater application lies in the capability of manipulation of the C++ type system. Most metaprogramming techniques are applied to make libraries hide their implementations better and allow you to write simpler, cleaner code without reams of types in angle brackets.

Type manipulation tricks are best left to another blog entry. For now, you can check out:
[1] C++ Template Metaprogramming - Concepts, Tools and Techniques from Boost and beyond
This is a book by the authors of the Boost.MPL (the Boost Meta-Programming Library). The MPL has loads of tools to make metaprogramming easier as well as hacks to work around the deficiencies in various C++ compilers.
[2] The Boost TypeTraits library - This library makes type manipulation a breeze, thanks to the consistent interface and excellent documentation.

Hope you liked it. Comments always welcome.

The files for the examples are listed below. All of them have been compiled and tested using the Visual C++ 2005 compiler and should work with most other compilers. In case you have troubles, let me know.
[1] factorial.cpp
[2] fibonacci.cpp

The commplete source code including makefiles can be found here. A Jamfile is included for those who use Bjam.

Monday, July 14, 2008

I'm Back

Hey all,
Its been ages since I last posted on this blog and its been rather sometime since this blog had been taken off the internet. However, I'm back on the internet after being *really* busy at college and the blog is back online.
Well, in the time my blog was offline, I was completing my second year at college and in the summer vacations was developing a website for my dad and mom's Ultrasound clinic. You can see the final result at their home page: http://www.drkapoorsclinic.com .