Thursday, April 21, 2011

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.

Saturday, April 16, 2011

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.