Subho Bijoya

ঢাকের উপর ছিল কাঠি,
পুজো হল জমজমাটি,
আজকে মায়ের ফেরার পালা
জানাই তাই এবেলা

শুভ বিজয়া

Counting unique values in Open Office

The spreadsheet program, Calc (equivalent of MS Excel) in Open Office does not have a function to count the number of unique numbers in a range. Here is a quick hack that I have been using for quite sometime for doing the same:

SUMPRODUCT((Data<>"")/(COUNTIF(Data;Data)+(Data="")))

When using this hack, replace "Data" by the range of values from which you want the number of unique values like "A2:A10". This applies to Libre Office too, which is itself a fork of Open Office.

I would be very happy of Open Office or Libre Office developers took a note of this and implemented a simple COUNTUNIQUE(range) function in some next release.

Bengali font on Max OS X 10.6

Mac OS X 10.6 does not come with default support for Indian languages. Being a Bengali, I want to read and write in my mother tongue. Here is a step by step procedure to get Bengali support in Mac OS X 10.6.

1. Get bengali fonts in a format supported by Mac OS
• by default Mac supports the ttf format and not the newer Open Type format
• one of the best in terms of readability is "Ekushey Lohit" (একুশে লোহিত)
• download the font and save it in your Mac
2. Installing the font in your Mac
• Open the application called "Font Book". It comes by default with OS X 10.6.
• Drag and drop the saved TTF font file to the Fonts column of Font Book
• The font will get installed within 5-10 seconds
3. Using the bengali fonts
• Usually the font should be used immediately by applications like Firefox and Safari, so you should be able to see any bengali text like "বিজ্ঞান ভড়"
• In case you cannot see bengali text, just restart the system for the fonts to load

Please note that basically this is a technique for adding fonts to the OS, as default support for Unicode is already present. So in essence this same methodology should also work work with other languages.

More fonts for Mac can be found using a variety of online resources. Bangla Onkur a project that converts Open Type format fonts to TTF format for Mac.

Organizing clothes using Data Structure

Due to lack of hanger space in my present wardrobe, I have to keep my clothes folded. I usually pick up something from the top of the pile for wearing. Which means I keep wearing the a small subset of my clothes repeatedly. Ideally I would have liked to wear all the clothes. But its too much trouble to take a tshirt out from middle of a pile; the entire pile gets disheveled.

The solution is actually quite simple. Think of the tshirt pile as a stack. What I want is basically a queue. So all that is left to do is to somehow "implement a queue using a stack". The CS grads have already faced this problem in their Algorithm and Data Structure courses. I applied the same technique.

I used two stacks, one for putting the washed clothes in (enqueue) and another for taking out the clothes for wearing (dequeue). If the pile for wearing is empty, [and here comes the important step] then turn the washed clothes pile upside down and keep it in place for the wearing pile.

Its good to know that Data Structure knowledge is useful beyond computers too !!

Confessions of an Ebook Pirate

Today I found this article, titled "Confessions of a Book Pirate". Its an email interview with a bibliophile who is also a book pirate. The person in question has a name "The Real Caterpillar" in one of the many book sharing communities that he participates. He makes quite a few points which seemed logical and worth noting. The article is a definite recommend from me for anybody who loves books and is aware of ebooks and piracy.

However, some of the arguments seem feeble. Like "I would probably still grab a book if I stumbled across the file and thought it might interest me – or if I wanted to check it out before buying a paper copy". Well both of these can be very well accomplished in Google Books (partial book) or in the local bookstore (full book).

Personally, some of my interests fall into pretty much the tail end of the curve; and often finding books on some of these topics are quite difficult. Sometimes the books themselves are out of print. But I guess the ebook industry is moving towards the correct direction. With ebook readers flooding the market and big players like amazon coming in, bibliophiles like me are having a good time. Still it will take quite sometime till the entire spectrum is covered.

Follow links to land in Philosophy

A couple of days back, the a cartoon was posted on xkcd titled "Extended Mind". In the mouse-over text, Randall Munroe wrote the following:

Wikipedia trivia: if you take any article, click on the first link in the article text not in parentheses or italics, and then repeat, you will eventually end up at "Philosophy".

I decided to test this theory and indeed managed to land to Philosophy every time !! Here is a demo run for the same:

Snickers > Candy Bar > Cocoa Solids > Chocolate > Mexico > Federation > Sovereign State > State (policy) > Social Sciences > List of Academic Disciplines > Academia > Community > Interaction > Causality > Event > Philosophy

I would be very interested in knowing if somebody find some topic that does not eventually lead back to Philosophy.

PS: To verify this theory I wrote a small Python program which starts from a random page and then traverses the first links until it finds loop or reaches Philosophy (or some threshold # of hops, say 1000). It ran for one night and gave me this loop:

Republic of India > Official names of India > Names of the Republic of India in its official languages > Republic of India (loop)

Why do people latch doors without lock?

I often see people pulling the latch of a padlock without actually putting in a lock. This is usually done when the person intends to come back after a short time. However I have always wondered about this practice.

The only plausible reason I find for doing this is preventing infants, toddlers or small animals from entering the room. However, in places where I observe this behavior (hostel and department) none of these can be the reason.

Another reason might be to show the immediate unavailability of the person who is usually behind the door. However a latched door without a lock is a clear sign that nobody is there in the room and to a thief this might be an opportunity.
 

SSH without password

Ever since I joined IISc, ssh-ing into other machines seems to be a daily task. Its hard to type in passwords every time. So this is what I did to avoid typing passwords for ssh.

Lets call the machine you are connecting from as "home" with your user name "homeuser" and the machine you are connecting to as "server" with your user name as "serveruser". Please note that in case the account in your "home" computer is compromised, the attacker can effectively login to the "server" as well. So use this with caution.

First you have to generate an RSA public-key, private-key pair. The public key will be placed in the server computer so that it can identify your computer when you ssh to it. Thankfully Linux installations come with all the tools that you require to do this. So all you have to do to generate this key pair is open a terminal in "home" and type:

homeuser@home:~$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/homeuser/.ssh/id_rsa):
Created directory '/home/homeuser/.ssh'.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/homeuser/.ssh/id_rsa.
Your public key has been saved in /home/homeuser/.ssh/id_rsa.pub.
The key fingerprint is:
3e:4f:05:79:3a:9f:96:69:bf:89:0a:37:16:e9:25:e2 homeuser@home

Next you have to store the public-key in "/home/homeuser/.ssh/id_rsa.pub" to "server". For this first create a directory on "server" by ssh-ing to it: (don't worry if the directory is already there):

homeuser@home:~$ ssh serveruser@server mkdir -p .ssh
serveruser@server's password:

Next copy the public key from "home" to the "server"

homeuser@home:~$ cat .ssh/id_rsa.pub | ssh serveruser@server 'cat >> .ssh/authorized_keys'
serveruser@server's password:

Now you are done. Try ssh-ing to the server and you will be directly greeted with a prompt:

homeuser@home:~$ ssh serveruser@server
serveruser@server:~$

Please note that:

• This method kind of identifies your "home" computer to the "server", so in case your account in "home" is compromised, immediately delete the corresponding key from .ssh/authorized_keys at the "server".
• You have to do this every time you install a new OS in "server" or "home".
• I have only tested this on the machines that I use ... so this should work well in Fedora, Ubuntu and Mac. Sometimes your version of ssh might differ and you might have to put the public key to ".ssh/authorized_keys2" and change its file permissions to 640 and change file permissions of ".ssh" to 700.

Thanks for reading through. If you have any further questions/comments, just post it here. 

Edit [2011-09-30] For all the lazy people (like me) out there, here is a simple one liner that will do the same trick. Just type in the server password twice when the terminal asks.

ssh-keygen -t rsa; ssh-keygen -y; ssh serveruser@server mkdir -m 700 -p ~/.ssh; scp ~/.ssh/id_rsa.pub serveruser@server:~/.ssh/authorized_keys

 This simple and very effective one-line idea was given to me by my colleagues at amazon.

Cell array to matrix in Matlab

Having used Matlab for machine learning work, I often face this problem. Typically while working with some classifier like "TreeBagger", the "eval()" function for computing labels of test data returns a cell array where each element is '1' or '-1'. The problem is that my original labels were numeric {1,-1}, so comparing these become a big problem especially if one is interested in things beyond accuracy.

Here is a simple technique to convert this cell array to a matrix. Say the original cell array is:

cellArr={'-1'; '-2'; '3' ;'6' ;'5'};

Now to convert this into a numeric array, all you have to do is:

mat=cellfun(@str2num,cellArr);

This calls the function str2num for each element of the cell array and returns the resultant matrix in numeric format.

replaceTab, an utility program

I use PasteBin for all my online code snippets. However there is one small problem which I find about their service:

Tabs expand to 8 spaces

While many might not understand the fuss, I find this quite annoying. I use Tabs for my code and the default number of spaces I use  for Tab is 4. Expanding Tab to 8 spaces, makes my code look ugly (kind of stretched). Being a programmer, I wrote this following piece of code in C which replaces the Tab by as many characters as one wants.

I designed the program to read and write to stdin and stdout so that I can use it as a pipe for further programs (mostly to facilitate joining multiple files). The syntax is simple:

replaceTab 4 < inpFile > outFile

The first argument is the number of characters I need per Tab. The default value is 4 which is assumed when there are no arguments.

Here is the C source code for the same (yes, I have posted it in PasteBin):



PS: Before writing the code, I tried using the unix command line utility "tr" for this, but could not get it to replace one Tab by multiple spaces. However as it was pointed out to me by a friend this is simple using "sed". The corresponding command is: "sed 's/\t/    /g' < inpFile". ... Looks like I should be spending more time learning Unix utilities than writing simple programs.

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.

Project Euler Level 1

I have been interested in puzzles since I was little. After learning programming I would search out puzzles that could be solved by coding. Few years back while I was pursuing my B.Sc. I encountered Project Euler:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I got hooked on solving these problems. Sometime along the line I gave up due to exams or some other commitments. Now that I have started learning Python, I was again hunting for puzzles that I could solve with my Python coding skills. This is how I encountered Project Euler for the second time. I managed to pick up from where I had left duing my B.Sc. Today I managed to reach level 1. While its not much of an achievement considering a lot of people before me have successfully done it, but nonetheless it feels great.

I tried to solve most of the problems in Python. But sometimes ended up using good old C. Sometimes I would just use Java or C++ for the rich template libraries that these languages have. Some of the solutions lent themselves to Matlab and (surprise, surprise) Calc (open office version of MS Excel). Only 2 could be solved by analytical reasoning alone.

Lets see how many I can solve. But its great fun to develop a solution and in the process explore some of the unknown language features and libraries.

Feynman's answers to Lateral Thinking puzzles

Late physicist Richard P. Feynman was well known for answering questions in a typical manner unique to him. Here are a few humorous takes on what he would have replied to the so called "lateral thinking" questions that are asked routinely at software company interviews these days.

Here are two examples of the quirky answers that he might have given to these trick questions:

• Why are manhole covers round?
• 3 switches are placed in one room and there are 3 corresponding bulbs. in another. Which switch lights which bulb?

What is amusing is that all the answers are all valid but differs from what the interviewer wants to hear. So the interviewer can neither refute the answers nor be satisfied by them.

A reader gave me this link in which Feynman is answering the question "Why do magnets attract or repel each other?". This is also a classic example of the fact that any fool can ask questions which the wisest man cannot answer.

Algorithm for finding square-root

It always intrigued me how one could find the square-root of a number. In school I was taught a digit-by-digit method to calculate square-root. I did implement it using BASIC in Std IX, but the solution did not seem elegant enough. By Std XI I had actually figured out the Bisection method by myself and used it to find any root of a number. This again was implemented in C++ (... and I still have the code !).

Then in my B.Sc. I was formally introduced to the Newton-Raphson method and I have been using that ever since. At about this time only a classmate told me of the logarithm based method, which (if Wikipedia is to be believed) is the method of choice for most implementation of sqrt().

Recently I have been going through the MIT open course, Structure and Interpretation of Computer Programs. While watching the original 1981 videos, I came across this brilliant algorithm which was supposedly invented by the Babylonians around 2000 years back. It is also often attributed to Heron of Alexandria, who was also a great inventor (the link to his biography in Wikipedia has a section on his inventions ... looks impressive to me).

Heron's Algorithm can be derived from the Newton-Raphson method and can be considered to be a special case of that. The brilliance however lies in the fact that it precedes Newton-Raphson by 1600+ years. The algorithm is very simple:

1. Guess a solution for sqrt(x), say g
2. Check whether the current value of guess is "good enough" (square roots can be irrational, so exact value is often not achievable)
3. If the guess is not "good enough", compute the new guess by updating  g=(g+x/g)/2
4. Go back to step 2

You know from my last post that I have recently been learning Python. So here is a python implementation of the above algorithm.

Once again, please let me know if you find any bugs in the implementation. I am a Python newbie and your suggestions can help me improve.

My first Python program

I heard of Python in my final year of B.Tech. at CU. Since then I have tried many times to pick up the language. Unfortunately most of the efforts have not gone far mostly due to lack of a particular problem to attack.

This time however it went differently. First I came across this brilliant and simple way (Monte Carlo technique for computing Pi) to compute the value of Pi from some CS magazine that I ran across in Dept of CSA [1]. Then I wanted to implement it. Matlab and C would have been the perfect choice for writing this simple code, but I just had enough time for trying it out in Python.

Here is the result of that (after 50mins involving mostly Google and the Python website):


Maybe I could have improved the code a lot had I been an "evolved Python programmer". But I am pretty happy with the initial results that I got. The great thing is that with iteration count 100K or so the program almost always computes upto 3.14 correctly.

[1] Maybe Communications of the ACM, some issue of 2010, however the link given before also explains the same technique

Weird Idea

I have a trolley with small plants.

When I feel mischievous, I often take out the trolley to the verandah. Then I watch it from a distance. After a some bee find the flowers on the small plants. He goes back to the hive to inform the other bees.When he is gone I take the trolley away.

I love watching the swarm of bees coming to my verandah for no reason. I imagine they must be cursing the first bee. I just love embarrassing the first bee.