Some of the most interesting algorithms in Computer Science are involving trees. They are simple and often leverage recursion. For instance, pre-order traversal of a tree, of any complexity, can be written as follows:

void preorder(tree t)
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

For a hobby project, I was faced with an interesting problem of converting a flat representation of a tree into a nested data structure. A flat representation of a tree looks like this:

0
0
1
1
2
3
2
1

Each number refers to the nesting level within a tree. After conversion to a nested structure, it should look as follows (square brackets is the Python syntax for a list):

[ 0,
  0,
  [ 1,
    1,
    [ 2,
      [ 3 ],
    2],
1]]

I expected this algorithm to be fairly easy to find, but I didn’t have much success with Google. So, as any self respecting programmer would, I rolled up my sleeves and wrote a Python implementation:

def treeify(cs):
    cur = 0
    tree = []
    stack = [tree]
    for c in cs:
        if c['level'] > cur:
            l = [c]
            stack[-1].append(l)
            stack.append(l)
        elif c['level'] < cur:
            while 1:
                stack.pop()
                cur = stack[-1][0]
                if c['level'] == cur['level']:
                    break
            stack[-1].append(c)
        else:
            stack[-1].append(c)
        cur = c['level']
    return tree

I have tried to make the best use of Python lists by treating them like lists in LISP. Basically, both languages treat variables as references to actual data. So the lists are nothing but lists of references. This leads to some very useful properties. For e.g. in the above code:

• cs: Flat tree structure. This is slightly different from our previous example. It is a list with elements which are hash tables or dictionaries of the form {‘level’: 0, …}. This is better if your node contains other data that can be easily stored in a dictionary.

• tree: Nested tree structure. This is what we would finally return back

• stack: A stack of trees. Top of the stack is the lowermost node of the tree where the next item of the same level can be added as its child. Next element is the stack is its parent node and so on.

Go ahead and read the source for a mind bending experience!

One of the most adventurous things we did after marriage was to go to Kashmir for Honeymoon. Right opposite the Mangalore STP office we have Swastika Tours, a friendly operator whom we have trusted for many tours in the past. In 2008, when we approached him we had all sorts of exotic places in our mind like Maldives, Mauritius or Europe.

But with the memory of the Tsunami fresh in our minds, we quickly ruled out all islands and sea facing locations. The hill-stations and snow covered locales in the northern hemisphere remained. But it was Santosh from Swastika who planted the idea of Kashmir in our minds. In 2007, Kashmir was considered to be a dangerous place to visit, thanks to the media reports of fresh gun fires or terrorist attacks. We were hesitant. “Why not?”, he asked, “My sister just visited the place and she liked it better than her Switzerland trip. It is completely safe these days.” We looked at each other silently. We both knew that we were up for the challenge.

The one week Kashmir trip indeed turned out to be one of the best trips we have ever had. It was a land completely different from South India both in terms of people or weather. But one of the most memorable incidents involve the purchase of the much coveted spice found in Kashmir - Kesar or Saffron.

Until we reached Kashmir I had no idea what Kesar was. I came to know from the locals that Kesar is an extremely rare and expensive spice that has many Ayurvedic properties like making you fairer. In fact, they claim that Kesar is the secret behind a Kashmiri’s fairness. It was hard to disprove that claim since they mixed Kesar in almost every dish like a regular spice , even in a specially brewed tea called Kahwah . Both of us became big fans of delicious Kahwah and used to have it whenever we could.

So very soon, it was obvious that the must-have souvenirs to bring from Kashmir was a small stash of Kesar. Now, we were staying on a house boat in Dal lake. By evening, as they took us for a boat ride in a Shikara around the lake we used to find goods of every kind being sold by vendors on boats. You can find boats carrying milk, vegetables, fresh flowers, shawls, handicraft items and of course, Kesar.

Every day our Shikara used to change and one day it was an old man who used to affectionately call me Beta (son). Since, I managed to converse in broken Urdu (thanks to Bollywood movies), we got to know each other quite well. During our ride, a Kesar vendor approached us offering Kesar in various grades and quantities. We hesitated but the old man said that he knew the person well and you would anyways buy some so it might as well be from him. The seller showed us various grades of Kesar held in small clear plastic boxes. They looked authentic and had a lovely aroma. We bought two small boxes of the best grade he had for about two thousand rupees. The old man carried an affable smile all the time and went about extolling the virtues of Kesar.

The next day, our driver suggested that we visit a Kesar farm. Kesar blooms only in one month in an entire year. Fortunately for us, we were in the right time of the year and saw fields filled with rows of violet flowers barely above the ground. There was a small shop right in front of the farm. A very old man with an overflowing white beard sat behind a desk. He enquired if we are interested in buying some Kesar. I politely declined saying that we had already bought some from a Shikara.

The moment I said that, the old man and my driver exchanged worried looks. It was as if I did something really wrong. The old man requested if he can see some of the Kesar I’d bought. I looked at the driver and he nodded affirmatively. Fortunately I was carrying the small plastic boxes in my pocket. I handed over one of them to the old man.

He carefully opened the case and took a few stigmas out with a tweezer and gently placed them on his wooden desk. He took out a magnifying eyepiece, perched it one eye and began examining them carefully. We were all waiting with bated breath. Finally, he looked pleased and placed the eyepiece down. “Fake”, he said. I did not believe him.

“Let me prove it to you. A real dried stigma of a Kesar flower never completely dissolves in water”. He let a few drops of water fall on his desk and with tweezers hovered a stigma slightly above it. “With your permission?” I nodded. The stigma fell on the drops and began rapidly dissolving. After slight stirring, the stigma lent no more color and the water had a dull orange tinge.

He took another, nearly identical, small plastic container and proceeded to repeat the test. As the stigma fell, at first, it barely dissolved. Slowly a yellow region formed around the stigma and then it began to turn to an orangish tinge. The process took several more seconds and the color seemed keep effusing out of the stigma. The test was simple yet shocking in its effectiveness.

What was even more shocking was what he said next. “He cheated you”, he screamed. “It was a scam. He sold you colored paper and charged you by the nose. He cheated you”, he kept on saying. Since we had another day left, we decided to figure out how to recover the loss later. Meanwhile we bought some ‘genuine’ Kesar making sure that we tested it properly this time.

That night we spoke to the owner of the house boat about the incident. He too got quite agitated (we were now getting used to the temper of Kashimiris :) ). He wondered why anyone would buy anything from Shikaras since they were targetted at luring naive tourists. After he calmed down, he suggested that I speak to the old man and try to return the goods and recover the money. Making a police complaint would not be a good idea since we did not have much time left. I realised that it was probably the only sensible option left.

That evening, the old man was summoned for a ‘casual’ conversation. I boarded his Shikara alone. He started moving the boat and started his usual banter with his constant smile. After some conversation, I casually mentioned that we had a change of mind after speaking to our relatives and we wished to return the Kesar that we had bought. The old man’s expression changed. He started arguing that Kesar would last a long time and it would be good to keep it. But I was adamant that I wanted to return it and since the vendor was his friend, he would need to find him somehow.

At this point we were in a dark and secluded part of the lake. I could barely see the man’s face or guess what he was thinking. But from the way he spoke, he was clearly agitated. After much arguing, he finally agreed to speak to the vendor. He rowed to another area next to a house and left me at the boat. I waited for what seemed like eternity. I could hear some loud and vocal arguments from inside. Finally the old man came back in a hurry.

As he rowed he explained that he can only take back one container and that was the best he could convince the vendor. Since I had no expectations, this was actually a big deal. But I appeared displeased and grudgingly accepted. He took one of the containers and repaid the amount.

I felt relieved when I returned to the house boat. The old man must have realised that we fell for his sweet words. But at least we had a partial victory now. The box of fake Kesar would be a true souvenir, reminding us of Caveat Emptor!

“Chaos often breeds life, when order breeds habit.” – Henry B. Adams

It was a breezy, luminescent and quiet evening in planet Terra. Perhaps too quiet for an eventful day such as this. Perhaps that’s why emperor Kilter ordered a Pan-D911. Soon random bright spots popped all over the planet like an attack of pimples. Soon it smeared itself onto millions of other bright dots turning into something like an attack of rash.

Like a huge tidal wave the dots arose and swiftly spiralled upward into the cloudy magenta skies. With militaristic precision, the dots arranged themselves into concentric rings in space. From Terra, it was a magnificent spectacle. However, it didn’t impress the Queen, Triara. Made of sixty billion nanobots, Triara was by far the most exquisitely complex being in their planet. That meant she was female and extremely attractive, not to mention that she was undoubtedly their Queen. Even though Kilter was called the mighty Emperor and launched vain crusades that displayed his prowess, it was obvious that it was the Queen upon whom the future course of events rested upon. She scoffed at this ostentatious waste of Nino. Nino, being the hydrocarbon fuel, which powered everything on Terra including the nanobots themselves.

In less than a minute, the gigantic aerial structure resembling a football stadium composed of million of individual nanobots was completed. They slowed to a standstill and waited for the grand entry of Kilter. However when Kilter morphed from a giant ball of light to a octopedal being, it wasn’t as dramatic as he would have hoped. That was because most of the nanobots were thinking that the ball of light was simply a huge floodlight for illumination purposes. After an embarrassing pause, the swarm of nanobots erupted into a cheery mechanical drone.

Kilter expressed signs of pleasure and allowed the cheer to take its own sweet time to die down. He loved public appearances. He initiated a multi-channel broadcast with the bots. “Bots, we have assembled here for a historic moment. For the first time in twenty hundred thousand years, we are about the witness the execution of an alien trespasser”. He paused for effect. “As the most intelligent sentient beings in this galaxy, it our foremost duty to protect our planet and our civilisation. From our bitter experiences with other violent life forms we have realised that it only by containing the knowledge of our existence, that we can achieve this.”

“Hence, I am sure you would understand why I ordered the immediate execution of this alien terrorist whom we found under suspicious circumstances. Behold we show you, the vile subject in question”. A beam of light shone into a spherical crystalline sphere. Atop this brightly illuminated sphere was a blue-green algae of microscopic proportions. Triara grew concerned as she observed that it was not half as animated when she had last seen it.

The crowd was becoming increasingly fascinated with this exotic brightly-coloured being. Rumours say that this algae was actually first spotted by the Queen in her last inter-galactic vacation. She found it’s pulsating locomotion so mesmerisingly attractive that she had to have it as her very own pet. Rumours also said that after her vacation, the Queen spent an unhealthy amount of time with her pet that it almost became an obsession of her’s. This annoyed Kilter to no end. His Queen seemed to be excitedly raving about its “simple yet radiant green design”, “organic fluidity” and “long filamental extremities” all day. However, what pushed him over the edge was her secretive plan to build a reproduction chamber to “conserve” her pet. Kilter declared the “pest” as a threat to his, most conveniently, civilisation leading to the current state of affairs.

As Kilter continued his long meandering monologue, back in Terra, the Queen was slowly withdrawing herself into a coccon-like crystalline structure. It was hard to imagine what she was thinking, but it might have been something along the lines of - “this farce has been going on for far too long. Maybe a little competition would do a lot of good”. Slowly the exquisite form seemed to seamlessly blend-in with the hard brownish red rocks of Terra.

“And I hereby declare the alien to be vapourised with a single beam of focused rays until every part of its material being has been vapourised.”, concluded Kilter rather emphatically. Suddenly a bright red laser beam hit the tip of the crystal ball. The swarm broke into a noisy drone as the microscopic algae vaporised almost instantly. In its place, a white puff of vapour slowly rose up.

What happened next few microseconds is a sequence of events, like most major celestial events, that cannot briefly explained nor fully understood. It appears that the Hydrogen clouds that covered most of Terra could become incredibly unstable even with trace amounts of water. In fact, even a drop of water could seed a chain reaction that could transform its entire atmosphere. The algae vaporised by the whim of the Emperor had just the right amount of water to unintentionally change history.

It had been raining quite heavily in Terra for the last several days. The reddish brown rocks looked damp and muddy. Millions of nanobots were scattered lifeless all over the planet. They however didn’t have their characteristic steel-blue colour. Instead, they seemed to be covered in a bluish green fur.

Footnote: Written on the occasion of ‘World Water Day’ (Mar 22). Rather it was an experiment to find out how far one can take the topic of ‘Last Drop’ ;)

Thank you for the great feedback on my first screencast about building a blog in Django 1.3. A lot of people told me that they found the video helpful in understanding what Django is capable of.

As promised earlier, I have recorded a short video (7 mins) that explains how you can use an HTML5 template to improve the appearance of your blog. You can use any free template or create your own.

Django’s (version 1.3) static files app is being used here. Unlike prior versions, there are no changes to urls.py required here. Linking to the admin site is also demonstrated.

It is best to watch it directly at Youtube in HD.

UPDATE: The blog with the updated template has been uploaded to github

Just uploaded a quick screencast showing how to build a blog in Django in just 30 minutes (plus a couple of seconds :) ). It shows off a lot of new features that we have in Django since 1.2.

It basically covers:

• Using django.contrib.admin to create fully-featured admin pages
• Adding tags to posts easily using taggit app
• Class-based generic views for rapidly building pages (New in Django 1.3)
• Using template inheritance and filters
• Leveraging django.contrib.syndication for a simple feed

It is best to watch it directly at Youtube in HD. This was my first screencast so I apologize if something is not properly done.

I plan to add a short bonus video soon demonstrating how this bare-bones blog can be restyled into a modern-looking HTML5 site (UPDATE: Bonus video is up now).

UPDATE: The source code for the created project has been uploaded to github