A recipe for Vegetable Biryani

Here is a recipe for Vegetable Biryani that has been well received by others so I thought I will post it here.  Why am I adding yet another Biryani recipe when there are literally thousands already on the web?  The reason is that most recipes seem to assume that everything will just work.  Reality is however different.  In real life

• after following the recipe, we may find that the rice has remained uncooked and we have to figure out how to recover from that problem
• we may not have all the ingredients so we may start wondering what to do
• the recipe may not explain what advance preparations might be required
• and so on ...

In this recipe I have tried to explain the rationale for various steps in the hope that this will help you extricate yourself if (when) you encounter something unexpected besides encouraging you to depart from the book.
First a high level view of the process of making Biryani:

• Cook the vegetables that will ultimately go into the Biryani
• Shallow fry the onions along with cumin seeds and ground cumin powder.  This will ultimately be mixed into the semi-cooked rice in the next step
• Partly cook the rice in water infused with various spices and mix the onions in the rice
• Interleave layers of semi-cooked rice and vegetables in a vessel and then cook this over low heat

Advance preparations

• You will need Basmati rice - I have never tried this recipe with any other rice and would hesitate to suggest that you use any other rice variety since getting the rice right is one of the key elements of a good biryani
• You will need a good thick bottomed vessel in which to slow cook the Biryani since a think bottomed vessel will result in the Biryani getting burned at the bottom.  If you do not have such a vessel you need not despair - you could simulate this by placing your actual Biryani vessel in another vessel while doing the slow cooking but then you will need another wider vessel for this.  My experience with rice cookers has been mixed so I will not recommend them  (although you will find some tips for how to use a rice cooker as well)
• You will need a lot of Indian spices.  While it may be O.K. if you are missing some of these , you would want to have most of these spices available.  In the ingredient list below I have labeled the ingredients as "essential" or "desirable" to help you plan.
•  You will need lots of vegetables - my rough rule of thumb is that for every unit of uncooked rice you can safely use three times the quantity of raw vegetables by volume.  Vegetables that go well with the Biryani are:
• Tomatoes
• Cauliflower
• Green Beans
• Green Peas
• Bell Peppers (also called Simla Mirchi or Capsicum).  Apart from the green colored variety, feel free to use the red and yellow versions too
• Potatoes in limited quantities but if you want to use these, use the ones that will not get mashed but will retain their firmness when cooked.  Also, you would be better off using somewhat large pieces (say cubes of size 3/4th of an inch ?)
• Cilantro for garnishing (also called Dhania leaves or coriander leaves or kothimbir)
• If you are not cooking on a rice cooker, it will be useful but not essential to have some yogurt around

Ingredients

• 175 ml (approx. one cup) Basmati rice (essential)
• Three times as much of vegetables (essential)
• handful of green beans
• 90 ml green peas
• 3 bell peppers
• 180 ml of cauliflower
• One large tomato chopped (essential)
• 2/3rd cup chopped onion (essential)
• (Optional) a teaspoon of heavy cream for adding to the vegetables
• (Optional) six teaspoons of yogurt (dahi or curds)
• 4 spoons cooking oil (essential - I usually use peanut oil but any cooking oil without a strong smell should do)
• 1/2 tsp roasted and crushed cumin seeds (essential)
• 1 spoon cumin seeds (essential)
• 2 tsp grated ginger (essential)
• 2 or 3 leaves of garlic chopped finely (essential)
• 1 tsp turmeric (essential)
• 1/2 tsp chilli powder (substitute green chillies if unavailable)
• Salt to taste
• 5 cloves (Laung)
• about 4 inches of cinnamon (Dalchini) stick (highly desirable)
• about 6 cardamom (elaichi) pods slit (highly desirable)
• 4/5 bay leaves, aka Tamalpatra  (highly desirable)

Making the Biryani

1. Chop the onions and the vegetables.   Remember to string the beans and throw out the seeds from the bell peppers.  You may mix all the vegetables at this point except for the tomatoes and the cilantro which you should keep separately.
2. Wash and rinse the rice, soak it in plenty of water.  After about 20 minutes drain the water. 
3. While the rice is soaking, roast the cumin seeds till they appear to have become crisp and then crush these seeds into powder. 
4. In a thick bottomed vessel (or a non-stick container) heat about two teaspoons of oil.   When the oil has heated, lower the flame and add about a teaspoon of cumin seeds and make sure that the oil has heated sufficiently by looking at the effect it has on the cumin seeds.  Then add the chopped onions and the ground cumin powder and sautee' this mixture together, occasionally stirring.  Do this until you see the onion changing color (this should take about three to five minutes ).  Important thing to remember is that you should not burn the cumin seeds - remember to lower the stove before putting in the cumin seeds.
5. Gather the following ingredients in a plate:
• grated ginger
• chopped garlic
• 1 teaspoon turmeric powder
• 1 teaspoon cumin seeds
• About three teaspoons of salt - remember that you need to put enough salt to compensate for the fact that the rice in the Biryani has no taste of its own
• Chilli powder according to your taste
6. You could reuse the vessel used in the last step for cooking the vegetables.  Just make sure that it is large enough to hold all our vegetables and still leave room for stirring the vegetables.  Take about two teaspoons of cooking oil and heat it in a fashion similar to the previous step.  Once the oil has heated sufficiently lower the heat, add the ginger and sautee' it for about 30 seconds.
7. Add the remaining ingredients from the plate, stir them for another 15 seconds.  If you feel that things are close to getting burnt, turn off the heat and add the tomatoes before turning on the heat again.  If needed, add a teaspoon of water to ensure that nothing burns and sticks to the bottom.  After about 30 seconds, add the remaining vegetables except the cilantro.  Stir the vegetables and cook on high heat for about three minutes. 
8. Lower the heat and place a lid on the vessel to minimize loss of heat and water vapor.  The idea is that by heating the vegetables on high heat we have already heated the moisture in the vegetables and given time and a minimal amount of heat, the vegetables will cook of their own accord.  Also note that we do not need to add any water - the vegetables we have chosen contain enough moisture to begin with and this is released in the presence of the salt when heated. 
9. Let the vegetables cook for about 15 minutes (please resist the temptation to take off the lid and stir !) .  Take off the lid and raise the stove heat.  The idea is to evaporate the water from the vegetables while simultaneously ensuring that the vegetables have got cooked.   Stir occasionally and cook until the water has mostly evaporated but do not let the vegetables burn at the bottom.  Initially when you take off the lid it may appear that the vegetables are uncooked.  Do not worry - by the time the water has evaporated the vegetables would have got cooked. 
10. If you are using heavy cream, you could add this to the mixture at this time.  Also add the cilantro leaves.
11. With the vegetables prepared, it is now time to cook the rice.  For every cup of rice, take two cups of water and add the cinnamon, cloves, cardamom, bay leaves to it.  Add a teaspoon of salt and bring the water to a good boil.  When the water has started boiling, add the rice and cook it for about three minutes.  Then turn off the heat and drain the water.  Remember that the rice will not be fully cooked at this point.  Remove the various spices from the rice since you want to provide a pleasant eating experience for the consumers of your Biryani.  Add the previously fried onion to the rice and use a fork to mix it in the rice without crushing the rice grains. 
12. We are now at the final step of  the Biryani making process where we will slow cook the rice and the vegetables together.  This is the most critical part of the recipe.  In this step we have to ensure that the rice gets cooked properly but that is does not get burnt.
13. The safest utensil to use for this step is a heavy bottomed non-stick container.  Smear the bottom with some ghee (or butter or oil) to reduce the chances of the rice sticking to the bottom.  Divide the rice into three parts and spread the first part at the bottom of the vessel.  Then spread half the cooked vegetables over this.  Repeat this once more and top it off with the third portion of the rice. 
14. This step is optional - add just enough water to the yogurt so that it forms a thick paste.  Heat this on low heat for about a minute and then pour the yogurt on top spreading it evenly over the rice.
15. Apply a tightly fitting lid and cook on a low flame for about 25 minutes.  Open the lid and check to make sure that the rice at the top has got cooked - if not, heat it some more until this is done.  Add some more cilantro leaves and serve.

Additional tips

If you do not have the "perfect" utensil for doing the slow cooking of the rice, I have a good workaround - in fact the workaround results in an even better Biryani but is a little clumsier.  The workaround is to cook our Biryani inside an outer container.  Take a  utensil wide enough to hold our Biryani container and boil some water in it.  Put the container containing the Biryani rice into this container in such a way that the water does not spill.  Then heat this combination of containers as described above.  The advantage of this method is that the Biryani container gets heated from the sides as well as the bottom.


My experience with using a rice cooker for cooking Biryani has not been a particularly happy one.  For one, the result depends on the make of the rice cooker so I cannot make general recommendations.  However if you are using a rice cooker, I would recommend against using the yogurt since it often leaves the rice at the top uncooked.  Also, I would suggest cooking the rice a little longer when we pre-cook the rice (say 5 minutes).  You need to run the rice cooker on the "white rice" setting.   Finally, do not trust the cooker when it says that the rice is ready - open the cooker and inspect the rice at the top and if it is uncooked, cook it some more for another 10-15 minutes using your judgment.

How to Print large number of files automatically

Despite being in the second decade of the 21st. century when bits have replaced pages we still have to occasionally print out large numbers of documents when dealing with banks, government departments and the like.  I recently had the need to take printouts of a few dozen documents of assorted types - Word documents, pdf files, jpg images, tif files etc.  Doing this manually would have been quite painful and would involve

• opening the file by double-clicking on it
• choosing print
• clicking on print

And I would have to repeat these steps for every file.  Instead I wrote the following Powershell  function to automate this:

function Print-Docs 
{
    Begin { $shell = New-object -comobject Shell.Application }
    process {
        $parent = (Split-Path (Get-Item $_))
        $file = (Split-Path -Leaf (Get-Item $_))
        
        if($parent -and $file) {
            $folder = $shell.NameSpace($parent)
            Write-Debug ("Printing file '{0}' from folder '{1}'`n" -f $file, $parent)
            $file = $folder.ParseName($file)
            $file.InvokeVerb("Print")
        }
        else {
            Write-Warning "Missing file $_"
        }
    }
}

After this it was a simple matter to do something like

PS: 64 > ls *.xlsx,*.docs,*.jpg | Print-Docs

and  I had my documents printed out thus saving me at least fifteen minutes.

Note - this will work only on Windows 7 and newer versions of Windows (unless you installed Powershell on an older version). 

Food for thought:

• Some of the programs (e.g. the jpg program) prompts the user for some input.  How can this be modified so that the program is truly automated?
• How would you do this in a UNIX environment (I remember vaguely that you could do automation of GUI programs through wish and TK)?

Powershell commandlet to select a random subset from input stream

The problem:

Given a stream of incoming objects, we want to select a random subset of size "count".

This has many applications - for example, in my work as a software tester I could use this to do something like

cat alltests.txt |
Select-Tests-Meeting-Some-Criteria |
Modify-Tests |
Select-Random -Count 100 |
Run-Tests

This pipeline modifies all tests meeting some criteria and then selects a random subset of just 100 tests out of the (say) millions of modified tests in my test repository and executes those tests.

The obvious brute force solution would be to save all incoming objects into an array, shuffle the array and select the top "count" objects from the array. But this has a number of problems including:

• Storage requirement of O(N) where "N" is the size of the input
• All the processing starts only after all input has been read in so that there is a computational peak right at the end of input and no computation happens while reading the input

We can instead adopt a different approach that involves iteratively discarding input as it streams in and retaining only "count" objects at any given point of time. Of course, while doing so we have to ensure that all input objects have an equal chance of being selected. To ensure that we do this correctly, we will need to bias our selection to favor objects that have already survived previous eliminations rather than the new incoming object that has not yet been subjected to previous eliminations. This is easy to achieve if we maintain the invariant that the nth. input object should have a probability of survival equal to count/n for n>= count.

Here is a Powershell commandlet that encodes this logic:

function Select-Random {
param ($count) ;
   begin {
       if($count -le 0) {
           throw [System.Exception]
       }
       $num_seen = 0;
       $rand_generator = New-Object system.random;
       $selected = @();
   }
   process {
       if($num_seen++ -lt $count){
           $selected += $_;
       }
       else {
           #Get a random number between 0 and ($num_seen -1)
           $random = $rand_generator.Next(0,$num_seen);
           if($random -lt $count) { #Choose the new number and add to $selected
               $selected[$random] = $_ ;
           }
       }
   }
   end {
       $selected;
   }
}

And here is a test to make sure that our algorithm works correctly - our input consists of the integers from 1 to 11 and we select 10 of these. In other words, the probability of selection for any number is 10/11 = 0.9091. We repeat this test 10000 times and check the frequency of occurrence of each number in the output - it should hover around 0.9091 * 10000 = 9091

for ($i = 0 ; $i -lt 10000 ; ++$i) {
   $list += ((1..11) | Select-Random -count 10)
}
$list | Group-Object | Sort-Object -Property Count

PS: 44 >.\select-random.ps1

Count Name                      Group
----- ----                      -----
9051 4                         {4, 4, 4, 4...}
9056 7                         {7, 7, 7, 7...}
9070 1                         {1, 1, 1, 1...}
9079 2                         {2, 2, 2, 2...}
9083 8                         {8, 8, 8, 8...}
9088 10                        {10, 10, 10, 10...}
9094 9                         {9, 9, 9, 9...}
9094 6                         {6, 6, 6, 6...}
9099 3                         {3, 3, 3, 3...}
9133 11                        {11, 11, 11, 11...}
9153 5                         {5, 5, 5, 5...}

Some things I learnt from this exercise:

• How to initialize an empty Powershell array
• How to add an element to the end of a Powershell array
• The Group-Object commandlet
  

Importing mh mail into gmail

From 1990 until approx. 2004 I used the UNIX based mail client "mh". Around 2004 I got an invitation from my friend who worked at Google to try out gmail.

I had never used any web-based email service for a number of reasons:

• I had assiduously collected all my personal email across a period of more than fifteen years and wanted the security of knowing that all my email would always be available to me even if the "free" email provider were to close down
• As an mh user I was accustomed to the power of being able to do stuff such as "scan +inbox | wc -l" and no web based email would allow me to do that
• I did not care to read email accompanied by flashing advertisements etc.

The downside of my intransigence of course was that I could not take advantage of the universal access to my email that web based email providers offered besides having to ensure secure storage all my email myself.

gmail was a refreshing change however since it was the first email provider to also allow pop-based access to email stored there. With gmail I now had the choice of accessing my email anytime I had internet access while still permitting me to retain control over my email since I could always download it onto my local machine and I opened an email account (which was then "invitation only" :-).

The reality turned out to be different however. While it was true that I could download my mail in gmail using POP that had its own problems since all my emails got downloaded (including once I had already downloaded) every time I fetched mail from my gmail server. Furthermore gmail had added a number of cool features such as keyboard shortcuts, tagging, searching etc. that I was fast getting addicted to. Also I had taken up a job that involved working in a Windows environment so that it was no longer very feasible for me to use my Linux laptop at work. Before I knew it, I had already accumulated a substantial amount of mail in my gmail account in addition to my substantial mail on my home machine. Furthermore with the evolution of email I have to regretfully acknowledge that mh (or its graphical successor exmh) no longer cuts it and I have accepted that I have to move on from my past love ...

I am now trying to import my old mail from mh into gmail and here is how I was able to successfully achieve this:

• download the python script "gml" from http://marklyon.org/gmail/old/gml.tar using "wget http://marklyon.org/gmail/old/gml.tar"
  
• Extract the file gml.py - "tar xvf gml.tar"

I then wrote a bash script to upload all my old email to gmail and here is what it looks like:

folders -noverbose -all -recurse -fast -noheader -nototal | while read folder
do
#Remove the old mbox file
/bin/rm ./msgbox
#Pack this folder into an mbox format file
packf +$folder
#Mail the contents of this file one mail at a time while preserving
#original headers and simultaneously add folder-related information
#for use in gmail
python gml.py mbox ./msgbox  address+$folder@gmail.com outgoing_smtp_server_address      
done

Just in case you were not aware of this, gmail allows you to create multiple aliases for the same email address e.g. (messages to foo@gmail.com, foo+bar@gmail.com, foo+baz@gmail.com are all delivered to foo@gmail.com) - see http://mail.google.com/support/bin/answer.py?hl=en&answer=12096 for more details.

As a result I can now (theoretically) transfer all my old email to my gmail account. I will now need to figure out how to automatically label them based on the old source folder name (which I am embedding into my "To:" address field. I have not yet figured out how I can do that. Watch this space ...

Adding binary files to CVS

I recently added a few Excel files to CVS and suddenly found that the files had become unreadable when I checked them out again. Excel would complain that the files were corrupted blah, blah, blah ....

The last time this had happened to me, I had been dealing with files that were over a decade old and that contained very important information and I had almost got a heart attack. At that time I had figured out the solution after a lot of tense web research but had omitted to document that since I assumed that I would remember it. Now I wish to correct that omission of mine.

The problem happens because CVS by default assumes that files are non-binary and does stuff like keyword substitution on non-binary files when you check them out. The solution is therefore simple. Just let CVS know that the files in question are binary. For example suppose you have a directory foo in your CVS repository that contains (say) some .xls files that you mistakenly checked in without marking them as binary. The all you need to do is:

• cd foo
• cvs admin -kb *.xls
• cvs update

and you are all set.

To prevent this in future, go to the highest level in your repository and edit the file CVSROOT/cvswrappers just like you modify any other file in CVS. Modify it so it has the following lines at the end:

*.xls -k 'b'
*.xlsx -k 'b'
*.ppt -k 'b'
*.pptx -k 'b'
*.doc -k 'b'
*.pdf -k 'b'
*.docx -k 'b'

Then just commit that file and CVS will remember that all these files are binary files.

Note that this change will only apply to this particular repository. If you have multiple repositories you will need to modify this file in all your repositories, of course.

Shuffling a table in Excel

Here is a problem I faced recently - I had an Excel table that I wanted shuffled randomly (no, I was not dealing a bridge hand as people who know about my association with the game might conclude). As a matter of routine I was going to do it the way I knew how to do these things - by copying this into a text file and writing a Perl script to do the shuffling but I just decided to see how one could do it in-place in Excel itself. The answer is very simple and elegant! Just create a pseudo column in the table and set the value for each cell in that column to "=RAND()" and sort on this column! Excel is cool - I want to learn all about it.

Sometimes the old ways are the best ...

I woke up this sleepy Saturday morning and decided to check out what was happening on Twitter. My network on Twitter consists of one friend Dhananjay Nene who twitters regularly (http://twitter.com/dnene) coupled with many others who have done nothing other than twittering "Test" or "Checking this out" and then tuning out completely. Anyway, to come back to the point, I saw this entry by Dhananjay

"Brian Kernighan "Sometimes the old Ways are Best" - http://tinyurl.com/c2ydgc - Precisely the reason why I cant stop using Linux. 10:37 AM Jan 22nd from TwitterFox"

Reading Brian Kernighan's name brought back many happy memories. I think he must be the best writer on programming and I will recommend that anybody who has not read his writings should definitely do so. I hastened to read the link and it turned out a fairly so-so article by BK's standards. I did not find nothing very new in it that I had not already read. He talks about how typical UNIX tools are so effective and often do a much better job than most supposedly advanced toolys such as IDEs. I couldn't help relating to his angst given how I had suffered very recently with trying to achieve a fairly straightforward task in Windows simply because Windows and Windows tools aren't designed neatly (unlike UNIX tools of old).

What I needed to do was the following:
- Write a program P1 that set the permissions on a certain Windows directory (say "d") so that user "U" had full permissions on "d"
- Write another program P2 that would be invoked at a later point of time that would restore the original permissions whatever they might be.
One could assume that P1 would be followed by P2 so the conditions are fairly straightforward. Essentially the scenario was that I would run P1, run some tests and reset the permissions on "d" by invoking P2.

Under Linux this would be so straightforward:

• P1 would consist of one line : getfacl d >oldacls
• P2 would consist of one line : setfacl -f oldacls d
  

In Windows on the other hand I had the following problems:

• Windows has at least three programs that manage file ACLs, not all of which work on all versions of Windows - cacls, xcacls, icacls
• Except for icacls that is only supported on Vista and later, none of the programs provide a convenient way for storing current ACLs.
• cacls is available on all Windows platforms post-2000 (which was o.k. for me) but not all cacls had a "/S" switch that prints current ACLs
• In settings where I can use "cacls /S" to get the current ACLs I still need to parse the output which looks something like c:\dir1\dir2\currentdir: "a long ACL string". Unfortunately parsing this string and extracting the ACLs for d1 is not at all trivial in Windows, unless of course we were using UNIX tools such as grep or perl or awk.

Unfortunately for me, using any of the UNIX tools was not an option so I had to end up writing over 100 lines of C# code! Can you believe it?

Predictions

In my life I have heard a number of very sweeping predictions that have or have not come true. For example, I remember that in the year 1981 someone (initials AV) had very authoritatively asserted that the U.S.S.R. and China would come close in a strategic alliance within a decade. This person (who is very knowledgeable and whom I hold in high regard) offered as evidence a number of events such as veiled statements made in "official" "party" publications in those two countries. Remember that in those days both these countries were extremely secretive and one had to very carefully parse comments made in these official news organs in order to understand what the powers-that-be wanted the world to hear.

What actually happened was that the U.S.S.R. crumbled under the costs of a costly war in Afghanistan coupled with an extremely inefficient agriculture plus a very expensive arms race with the U.S. and ultimately saw a collapse of the economic and political system that hitherto held sway there. China, on the other hand also underwent a significant transformation, albeit in a totally different way. Today both countries are solidly capitalist (but still very undemocratic) although China continues to pays lip service to communism. But the point is that the prediction turned out to be totally untrue or at least irrelevant. On the other hand, I know of nobody, literally nobody, who foresaw the collapse of the Soviet Union, neither people on the right nor those on the left!

I just thought it might be worthwhile to keep track of predictions people make and preserve them for posterity and this is what I want to achieve with this blog. I may not live long enough to know how some of these predictions turned out. As an example, I think I remember having read an Arthur C. Clarke book a long time ago wherein he had predicted that human beings would achieve immortality by 2100 A.D :-). I am pretty sure I cannot test that (unless we achieve this by 2022 when I will be 60 years old).

I had assumed that there would be a site http://www.predictions.com/that would have such a list but I was disappointed to see that as of December 15, 2008 it only had predictions about:

• football prediction
• college football predictions
• pro football picks
• football odds
• psychic reading
• psychic online
• tarot reading
  

For what it is worth, wikipedia.org has a page that is relevant - it is http://en.wikipedia.org/wiki/Famous_predictions (as of December 15, 2008)

Anyway here is the list of predictions that I will update on an ongoing basis:

• My friend SB, a hedge/mutual fund manager predicted that the U.S. economy will be worse off in 2018 compared to today (2008). This was in response to my observation that the quality of goods and services obtainable in the U.S. today is significantly inferior to what I saw in the late 20th. century. In general, I think the U.S. population feels much poorer compared to ten years ago. And this is something I noticed in 2007 before we had the country going into recession.
• On April 7 2009 Michael Stonebreaker predicted that "in the next decade the database market will shift from elephant one-size fits-all databases to specialized databases". In other words people would be using specialized databases for different types of workloads such as transaction processing, data warehousing, text data oriented applications, scientific applications, streaming applications etc.

Successful Predictions

And here are some predictions that people I know had made in the past that turned out to be true:

• In 1989 my friend Deepak Khemani had made a prediction that I had been extremely dismissive of then but has proved to be remarkably prescient - he said that by the year 2005 software would be the dominant technology. I think he also went on to say that by 2020 it would be the only technology. Incidentally, Khemani is now a Professor of Computer Science at I.I.T. Madras and his web site is http://www.cs.iitm.ernet.in/khemani/ (correct as of December 15, 2008)
  
• The Bridge World predicted in 1957 that Canasta would not displace bridge in its popularity (but see below under "Failed Predictions")

Failed Predictions

• The Bridge World predicted in 1957 that the new fad called "Television" would not displace bridge in its popularity
  

Designing overflow-safe algorithms

I was thinking about an old interview type problem: "Given a set of N-1 distinct integers from the range 1 .. N, how will you detect the one missing integer?". Needless to say, the input contains no duplicates and the input is unordered. There are numerous solutions, with different problems/limitations:

• Sort the input array, go through that array and locate the missing element. Problem is that this is O(NlogN)


• Maintain an array (or a bit vector) of size N initialized to 0. As you read the input, mark the corresponding array element as 1. Then make one pass through the array and detect the missing element by looking for value "0" in the array. This algorithm is O(N) but requires investment in memory


• A cute solution that interviewers often look for involves summing up the input and subtracting this from the sum of numbers from 1 to N ( which is 0.5 * N * (N + 1) as any high school student knows). The difference between the two is the integer missing from the input.

The last solution is quite neat except that if one were to attempt to write such a program in most commonly used programming languages one would run into overflow problems. One could use special libraries that allow one to use arbitrarily large numbers (e.g. Perl's Math::BigInt) but they come with overheads that are really unnecessary for the problem at hand. The solution I propose involves keeping a "running difference" between the sum of the input and sum(1 .. N) making sure that this difference is always within the range (-N - 1 .. N - 1). Essentially we are going to iteratively calculate the value of

missing number = sum(1..N) - Sum(input) = 1 + 2 + ... + (N-1) + N - sum(input).

The first cut implementation might be something like

i = 1; diff = 0;
while (not end of input) {
    diff += i - input element;
    ++i;
}
return (N + diff);

The problem is that this could lead to an underflow if (say) the initial numbers in the input are all very high. If we instead start from the top like:

i = 1; diff = 0;
while (not end of input) {
    diff += N - i + 1 - input element;
    ++i;
}
return (diff + 1);

we could have the opposite problem that we could overflow on the higher side.

The solution to this is to make sure that diff is always within bounds - if we find that it is negative, we compensate by using an unused number from the higher end of the range (1..N) whereas if we find that it is going too high, we use an unused number from the lower end of the range (1..N)

Here is my Perl implementation:

sub with_summing {# @input
    my $high = @_ + 1; #Higher end of range = #elems in input + 1
    my $low = 1;
    my $diff = 0;
    foreach my $next (@_){
        if($diff < 0) {
            $diff = $diff - $next + $high ; --$high;
        } 
        else {
            $diff = $diff - $next + $low; ++$low; 
        }
    }
    return $diff + $low; #At this point $high should equal $low
}

This technique of iteratively calculating a bounded value without creating intermediate values that might overflow is useful in a number of other situations. Such solutions have the additional advantage they can also give visibility into the value the input is tending to as more and more input is read. For example, we could use this technique to calculate the average. Rather than using the formula average = sum of input/cardinality of input that is susceptible to overflow, one could instead use the following iterative solution

average_so_far = 0;
num_input_elements = 0;
while (not end of input) {
    average_so_far = average_so_far * (num_input_elements/(1 + num_input_elements) +                    new_element/(1 + num_input_elements);
    ++num_input_elements;
}

And we could wrap this into a nice class as follows:

class average {
public double average_so_far();
public void add_value(double new_value);
}

We could then use this class in (say) a chemical plant application where two threads share this object with one thread adding readings from a data feed while another thread could be displaying the summarized average to an operator. Notice the technique we used to update the average - we took care not to use the formula
average_so_far = (num_input_elements * average_so_far + new element)/(num_input_elements + 1);


We actually used this technique for keeping track of the results of a long running experiment we conducted as part of our work doing Performance testing at Aztecsoft, my previous company.

One might wonder how far one can go with this idea. How about calculating Standard Deviation anyone? My gut told me that this wasn't possible but it turns out that my gut was wrong! Here is how we can calculate SD without causing overflows (this may not be very readable but I am not good with representing mathematical symbols on a blog :-(:

sd = sqrt((sum(square(element - average))/(num_elems - 1)))

Let sq(i) = sum(square(element - average(i))/(i - 1)

Then it can be shown that (this is an interesting exercise that I am leaving for the reader, mainly because I will go crazy trying to format the derivation in this extremely hard to use blogging editor):
sq(i + 1) = (i-1)/(i))*sq(i) +
(delta)*(delta) +
(element(i+1) - average(i+1))*(element(i+1) - average(i+1))
where delta = (average(i+1) - average(i)
)

Notice that none of the elements of this formula are likely to cause overflow issues. This lets us write the following code to calculate the standard deviation

sub sd { # input array of numbers
    my $average = 0;
    my $new_average;
    my $num_elems = 0;
    my $old_square = 0;
    my $square = 0;
    foreach my $new_elem (@_){
        my $old_average = $average;
        $average = $old_average*($num_elems/($num_elems + 1)) +
                   $new_elem/($num_elems + 1) ;
        my $delta = $average - $old_average;
        $old_square = $square;
        if($num_elems > 0){
            $square = (($num_elems - 1)/$num_elems) * $old_square +
                      ($delta ** 2) +
                      (($new_elem - $average) ** 2)/$num_elems;
        }    
        ++$num_elems;
    }
    return ($square ** 0.5, $average);
}

To sum up, many seemingly straightforward "correct" solutions can break down at high data volumes but there is often an elegant solution that can overcome the limitations of the straightforward solution. Be on the lookout for such opportunities.

How to send a mobile phone "business card"?

I always get confused about how to send a person's data saved in my mobile phone address book to another person who is also in my address book. For example, say my friend "seeker" wants to know the contact information about another friend "sought". On my phone which is an antiquated (pre-2003) model of Nokia (I cannot say which one it is since there is nothing on the instrument that tells me what model it is) I can follow the following steps:

- look up information about "sought"
- choose "options" and then choose "send bus. card"
- choose (say) "via text msg."
- look up information about "seeker"
- choose to "send the business card"

I always get confused which order to do my search in (do I lookup "sought" and send his info. to "seeker" or do I look up "seeker" and send him information about "sought"?) and I thought others too may have that confusion hence thought I should record this permanently.

- Rajendra Gokhale

Words containing letters in alphabetical order

My daughter Rama asked me this question the other day - which is the longest word that contains all letters in alphabetical order? For a dyed-in-the-wool UNIX hacker like me, the answer was quite straightforward:

grep -i "a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*" /usr/share/dict/words

Interestingly enough, I had left out the "*" at the end of the regular expression so all the words I found were ones ending in "z". That taught me a new word - "chintz" which interestingly enough originates from Hindi and is a type of cotton fabric. My daughter alerted me to my bug when she pointed out that the word "fix" did not appear in my output. I was able to correct my error and rerun the program. One of the longest words fulfilling the requirements of the problem was "biopsy".

Many of my posts may seem like nice ways to kill time but these skills really come handy in ones day-to-day work - for example, in my role as manager I was able to put my skills to good use in order to figure out the productivity of my (Research) group. But that will be another posting for some other day.

- Rajendra Gokhale

Solving the hexagon problem using Perl

Here is a problem that I see quite often in one of the afternoon papers such as the "MidDay". You are shown a hexagon, all of whose sides are labelled with one English letter (see above). There is another letter at the centre of the hexagon. The challenge is to make as many words of four or more letters from the letters of the hexagon.

In making a word, each letter must be used once only. Each word must contain the central letter. There should be atleast one seven letter word. Plurals, foreign words & proper names are not allowed.

Given such a hexagon (encoded in some format of your choice) and a file consisting of all acceptable words (e.g. /usr/share/dict/words), can you write a program to solve this problem?

See the Perl program below that does this job quite elegantly. A small point - when I used the dictionary on my Redhat Linux (Fedora Core 3), I could not find the seven letter word because it was missing from the dictionary - I had to figure it out manually. The word was "website" and we are talking of the year 2006 A.D. :-)!

Here is the Perl program:

use strict;
my $regex = '^b{0,1}e{0,2}i{0,1}s{0,1}tw{0,1}$';

foreach my $word (<>)
{
chop $word;
my $newword = join "", (sort (split //, $word));
if ($newword =~ /$regex/ && length($word) >= 4){
print "${word}\n";
}
}
__END__
As you can see above, the regular expression from the image shown was hardcoded into the script but anyone who understands this program will be able to trivially modify it so that the regular expression can be constructed on the fly. Also one small optimization that is possible involves precompiling the regular expression.

- Rajendra Gokhale

Pune passport office information

I needed to get my passport renewed from Pune, India and was not able to find much information about this from the we so I decided to describe my experiences here.

My passport expires in October 2006 but I needed to get it renewed since I needed to get a visa in May 2006 - most countries do not issue a visa unless your passport is valid for at least six months beyond the date of issue of your visa. My impression was that the Government of India did not issue a new passport more than six months before the old passport is due to expire but that is apparently not the case - you can renew your passport upto one year before it is due to expire. Anyway the fact was that I needed to get my passport renewed in less than a month so I needed to go the "Tatkal" route that enables one to get an emergency passport. Note that typical waiting times at Pune are a few months so by Pune (Indian?) standards if you need your passport in less than three months, it constitutes an emergency :-). Here are my experiences getting a Tatkal passport from the Pune Passport Office.



The GoI is one of the biggest enemies of the environment. In order to apply for my passport I had to submit an application along with an elaborate set of supporting documentation, all in triplicate! Some of the documentation I had to submit was ridiculous beyond words - for example, I was required to attach photocopies of eight pages from my old passport and although these pages contained my name and date of birth I still had to provide proof of my date of birth. When I submitted my application I had with me all the following documents, each one in triplicate:

• letter from bank confirming my address (I did not have a ration card, the ultimate proof in India)
  
• letter from "reputed employer" confirming my address
• bank statement
• School Leaving Certificate confirming my date of birth
• my degree certificate confirming that I was qualified for ECNR (Emigration Clearance not Required)

If you plan to submit the application in person, you have to also make sure that all these photocopies are signed by you - if someone else is submitting on your behalf, you must have all these attested by someone qualified to do so plus you have to submit some other statement.

You will need a large number of photographs but that was not a problem for me. I have lived in India long enough that I always carry about 50 photographs on my person at all times (my guess is that twelve should suffice). You will need to glue those photographs at various places and sign on those so that the signature spans both the application form as well as the photographs. Make sure that you have affixed your thumb impression at the right place on all the applications (left thumb for males and right for females).

Here then is the list of items you need:

• glue stick (one no.)
• stapler with extra pins
• stamp pad
• portable photo-copier
• two ball point pens (black or blue ink)
• scissors
• plastic bag to carry all of the above
• a friend to assist you
• a novel/video game etc. to keep you entertained while waiting for your number in various queues
  
• and above all, lots of patience ...
  

Armed with all the required documents and accessories, I reached the passport office on a Wednesday (I think). I will describe all that I learnt there in the form of factoids:

• there are three steps in the application process.
  
1. get a token number from the token number queue.
   
2. wait to have your application scrutinized. Since there is a token system in place, you do not have to stand in any queue for this. In this stage, your application will be scrutinized in order to make sure that all your papers are in order. In general, you would have missed out some documents that need to be submitted and you are asked to bring them. For example, I had a valid visa on my current passport and I was asked to get photocopies of that (there are numerous shops providing photocopying service in the vicinity of the office). If your old passport contains valid visas, the passport is cancelled and immediately returned to you - the horror stories about your passport getting stolen etc. seem to be fiction.
   
3. When your application has been scrutinized, you have to await your turn at the payment window (again, you do not have to stand in a line - you pay when your number is announced).
• as mentioned above, I wanted to apply for a Tatkal passport. When I mentioned this to the "scrutiny" lady, she asked me to meet the Passport Officer after I had made my payment. At the payment window they just took the fees for a standard passport from me.
  
• sign the token that was given to you at stage 1 of the process before you approach the scrutiny window - this is an undocumented requirement and will earn you brownie points with the lady at the scrutiny window.
• after paying the fees I went to meet the Passport Officer and told him that I needed my Passport in a hurry - he asked me to come after eight days. Note that by this time it was close to 1 p.m. so there was no line to meet the Passport Officer.
  
• I accordingly went to meet him after eight days. This time I had to stand in a long line (make sure you stand in the line to meet the Passport Officer, not the one leading up to the PRO :-) ). After an hour spent in the queue, I got an audience wth him. I had all the documents needed for getting an emergency application. He asked me to write a covering letter. After I did so, he asked me to meet him again after two days.
• I again met him after two days going through the same process as before. Surprise of surprises - he asked me to come and collect the passport in the afternoon!

I went in the evening and collected my passport. I had got my new Indian passport with a 5 year validity on the tenth day after applying. Not only did I not have to bribe anybody, I didn't even have to pay any special fees! Of course, I had to spend three mornings and one evening, but I guess we are still only in the 21st. century out here :-(.

Lest I sound very matter-of-fact here, let me assure you that the actual experience was extremely annoying for me. I had even exchanged words with the Officer on the first day. However the speed with which I got my passport ultimately was a really pleasant surprise.

I think I will stop now.

- Rajendra Gokhale