Generate Palindrome by Appending Characters

I was recently asked this programming puzzle at an interview:

Given a string as input, construct the smallest length palindrome from that string by adding 0 or more characters at  the end of the string.

So for input "abb" it would be "abba" with only one character added at end; for "abcdaad" it would be "abcdaadcba" with three characters added to the end. Of course in the worst case all n-1 characters have to be added as in "abbc" and the best case is if the string is already a palindrome like "abcba".

This is what I wrote: (note that the first question was about checking a string for palindrome, so I kind of thought it would be cool to reuse that piece of isPalin() function that I had already written)

Coming back home it occurred to me that I could have made the code smaller by writing an strrev() function to reverse a string and checking for palindrome with a combination of strcmp() and strrev(). This would furthermore allow me to reverse the beginning non-palindrome part of the input string, which I could directly copy to the end of the newly created palindrome string using strcpy(). Then I came up with this:

Unfortunately it seems that the length of the code did not change much. Or in other words, my innovative idea was no so cool after all.

PS: it seems that there is some issue with the terminating NULL charracter ('\0') of C and PasteBin. Please go through the RAW source code.

Adding until and unless to C

I have been looking into Ruby recently and find its keywords "until" and "unless" very interesting. So I thought what was a good way to add similar keywords into C/C++. Initially I attempted writing functions and then it struck me that this can be done with a simple macro. This is what I came up with:

#define until(x)    while(!(x))
#define unless(x)   if(!(x))

To illustrate my point here is a short factorial program:

I know that hacks like this do more harm than good in a large code base involving many programmers. But sometimes for small programs this can improve understandability dramatically.

Computing Pi to trillions of digits

Some fellows attempted a world record for computing Pi to 5 trillion digits. The page gives a fairly detailed outline of how they achieved this feat. The detailed specifications of the hardware and software used have also been included. Contrary to my assumption, this attempt ran on a PC with server class components instead of some cluster. Although they did use software for bit error correction.

Many people think of the question "why?" when they come across a record like this. None of the current technologies require Pi to this degree of precision. These folks have answered the question of "why" like this "Because it's Pi ... and because we can".

I have often wondered how (but not why) the digits of Pi are calculated. Some of the world records boast of trillions of digits accuracy. So far the only formula I knew was one discovered by Ramanujan

This blog post attempts to shed some light on the state of the art algorithms employed for this feat.

In case you are still wondering why would one compute Pi to so many digits of accuracy. Rest assured, AFAIK there's no real use !!

This is a combined re-write of two of my buzz posts:

1. Algorithms employed for the world record holder calculations of Pi
2. Attempted world record for computing Pi to 5 trillion digits

Thanks to all my friends who added lots of information to my knowledge base through comments in Buzz, Facebook and Twitter.

 

Happy Holi

Wishing you all Happy Holi.

May this festival of colours bring new hues to you life.
 

Fountain pen of a left-hander

These days its becoming increasingly rare to see fountain pens. Very few people seem to be still using them on a regular basis. Personally I like the comfort associated with it, but dislike the fact the ink is not waterproof. So one drop of water in the paper, and whatever you have written is gone.

It was a pleasant surprise for me to find out that a PhD student of IISc, Abhijit Khopkar uses a fountain pen, that too on a regular basis. One day for some reason, I borrowed his pen. "Something is wrong" was my first reaction trying to write with it. After some thought, I figured out that the nib of the fountain pen was tilted at an unnatural angle. Finally it dawned on me that Abhijit is a lefty and his writing angle does not match that of mine.

This was something which is quite obvious, but is hard to figure out by itself. Later I tried doing some research on this in internet. Seems this is quite an established fact. However the same is not true for other variety of pens like ball-point, roller, hi-techpoint due to a variety of reasons like the overall symmetry of the nib and the low usage of the nib compared to fountain pens.