• Download books
• Share and read notes on text book topics
• Watch relevant videos

Notemonk aims to create a rich and fun learning experience around text books. For launch, we’ve included the higher standards in NCERT. Please take a look and spread the work. Your feedback is most welcome!

Looking back at early accidents
When I look back at my short life I can see distinct periods or chapters. The time when I moved to Chennai and joined a new school in 3rd standard was the beginning of discovery that I could do well at studies and be competitive. During that stage I found my interest in science and technology and aptitude for various extra-curricular activities like quizzing, painting, essay-writing and such. Another parallel phase started in 5th standard when I stumbled upon my interest for computers and programming. In 6th standard I realized my potential in being a leader and continued to be the class representative for most of school life capping it with my role as a School Pupil leader in 12th std. All these phases happened more or less without any conscious effort on my part. They just happened. I lot of credit goes to my family and teachers for guiding me through these. The point however is that the phase transitions were by and large accidental from my point of view.

Hmm… Can we make accidents happen?
The first time when I consciously ushered in a new phase was in 11th std. An incident at school made me introspect and got me to start the process of understanding myself and people around me. What motivates us? What do we all want? What elevates us into happiness? What drops up into the abyss of sorrow? I learnt to control my anger and to think more rationally. I learnt to observe people around me and look behind the eyes. It taught me to empathize and connect. That was when I realized that I could decide what I could do and be – that future phases in life need not be accidental.

Life is a powerful force that keeps pushing you around. I have not met anyone who is in complete control. I don’t even believe complete control makes sense in the framework of life. At best we can attempt to understand the forces behind life and learn to go with the flow. Whether or not we can influence the direction of it, we can atleast benefit from the interaction. We can learn and become better at it – at understanding. The one thing I decided not to do was to get too comfortable. Learning happens when there is a differential current in the river of life.

Undergraduation was a new phase filled with freedom, learning and fun. As opposed to school where your peers come from your immediate locality, in college, you get to meet a more diverse set. You meet people who think differently and are motivated by various ends. In understanding them there was a great opportunity to discover more of myself which I did.

Veveo – my first workplace
After college I was confused about what to do. Do I pursue higher education or should I get a job? The companies coming to my campus for recruitment were Wipro, TCS, CTS, Infosys and so on. I work profile being offered did not excite me. Pursuing MS was the option I was considering and started the application process. At that time I came to know of a startup in Bangalore who were looking to hire freshers. Having set my mind on MS, I applied to this company half-heartedly, more to experience the interview process than anything else. I was interviewed by two people from the company one of them a co-founder and other a VP. What hooked me was the way they interacted with me. From my point of view they were experienced professionals working in the industry having etched out successful careers and I was a little no-body – a fresher from a private college. For the first time I felt I belonged somewhere and could establish a relationship based on mutual respect. I had always detested the authoritarian nature of our society. In schools and colleges I saw a lack of reciprocative respect from the faculty. Our society has a lot to learn in terms of treating each other humanely. Anyway, that’s that. I got hooked and told my family. Despite their concerns about this being a “small” company without “security”, I decided to dive in head long to discover the “insecurity” of being in a puny startup. Thus I joined Veveo.

Veveo was a very productive experience. I discovered startup culture and rediscovered myself. I walked up to the co-founder who interviewed me after getting my first paycheck and thanked him for paying me for having fun at work. That is a double scoop. I could not believe that was happening to me. For the first time in my life, I felt I belonged in a group. I found people who thought like me with whom I could share my ideas and I found other smart people who were so different that I would spend countless hours bludgeoning their logic (and getting bludgeoned too . The 4.5 years of experience at Veveo feels more than the sum of what I had experienced before. Phew! What a ride it has been. The day I quit Veveo, I found it difficult to justify my decision to do so. Even today the thought is not extinct.

What next?
Looking back I realize that I was getting too comfortable at Veveo. A good work environment, nice people and wonderful pay — yummy! Time for an adventure. I came up with an idea for making a physics simulation engine to aid game devs in creating awesome destructible environments. That was slightly more than a year back. I worked on it part-time in the evenings and weekends and then in March last year I requested my superior to release me so I could do it full-time. Much to my surprise he offered a part-time schedule where I could work at Veveo three days a week and spend the rest working on my project. This opportunity was god-sent and I lapped it up. A friend of mine from college who was also my roomie quit his job and joined me to work on this full-time.

The period since March last year is easily the most productive and exciting phase of my life. I have learnt immensely on a multitude of subjects – technology, project management, startup fundamentals, spirituality and philosophy, business development etc. The experience has altered me as a person and opened up avenues of my brain which I thought inexistent. I decided to take a plunge into this world full-time and took that step. I quit Veveo to work on this full-time from Jan this year. The journey so far would have been but a dream had it not been for support from my family, friends and colleagues at Veveo. Thank you all for being there.

Startups businesses are difficult beasts to tame and most people get flattened. The promise of glory (and $’s ) is a worthy lure for a persistent one. I intend to succeed doing this but failure is no less a success considering the path you tread and the things you experience. I will keep you posted in the forthcoming articles on this blog. A new chapter awaits.

Aliaser works by monitoring your bash history. It analyses command frequency and suggests candidates for aliasing. It manages aliases so created. The feature I like most in Aliaser is that it reminds you to use the aliases you created by showing tips on opening a new terminal session.

Download Aliaser from http://aliaser.googlecode.com.

BASH function

# wiki

# eg: wiki India
#     wiki Apple_Inc
#     wiki Anglo_Saxon
wiki()
{
    dig +short txt $1.wp.dg.cx
}

Example usage

prashanth@prashanth-desktop:~$ wiki India
"India, officially the Republic of India ( '\; see also other Indian languages), is a country in South Asia.
It is the seventh-largest country by geographical area, the second-most populous country, and the most
populous democracy in the world. Bounded by t" "he Indian Ocean on the south, the Arabian Sea on
the west, and the Bay of Bengal on the east, India has a coastline of ... http://a.vu/w:India"

prashanth@prashanth-desktop:~$ wiki Anglo_Saxon
"Anglo-Saxons (or Anglo-Saxon) is the term usually used to describe the invading tribes in the south
and east of Great Britain starting from the early 5th century AD, and their creation of the English
nation, lasting until the Norman conquest of 1066. The " "Benedictine monk, Bede, identified
them as the descendants of three Germanic tribes: http://a.vu/w:Anglo-Saxons"

Usage

prashanth@prashanth-desktop:~$ translate bonjour
hello
prashanth@prashanth-desktop:~$ translate guten morgen
Good morning

Code

#!/usr/bin/env python
'''
Translates text into english using Google Translate.
Usage: python translate.py 
        (or)
       echo  | python translate.py

For convenience, make a symlink to this file from /usr/bin/translate.
'''
# derived from : http://code.google.com/p/py-gtranslate/source/browse/trunk/gtrans.py

import sys
import urllib2
import urllib
import simplejson as json

FROM_LANGUAGE = ''
TO_LANGUAGE = 'en'
BASE_URL = 'http://ajax.googleapis.com/ajax/services/language/translate'

def translate(from_language, to_language, text):
    langpair = '%s|%s' % (from_language, to_language)
    params = {'v': '1.0', 'langpair': langpair, 'q': urllib.quote_plus(text)}

    params = '%s' % ('&'.join(['%s=%s' % (k,v) for (k,v) in params.items()]))

    url = '%s?%s' % (BASE_URL, params)
    resp = json.load(urllib2.urlopen(url))
    try:
        return resp['responseData']['translatedText']
    except:
        return text

def main(text):
    if text:
        print translate(FROM_LANGUAGE, TO_LANGUAGE, text)

    else:
        lines = [l.strip() for l in sys.stdin.readlines()]
        for line in lines:
            if line:
                text = translate(FROM_LANGUAGE, TO_LANGUAGE, line)
                print '[%s]' % line
                print text
            else:
                print

if __name__ == '__main__':
    args = sys.argv[1:]
    text = ' '.join(sys.argv[1:])
    main(text)

However flash drives do not have sustained data transfer rates that hard disks have (i.e throughput). My thought process what that the throughput can be made up by slapping together two or more USB drives and applying software RAID 0 over them. Below are some performance results and they look encouraging.

Note that the timings are in seconds.

Single 8GB Dane-Elec USB drive
131.11 for 683MB (write)
44.62 for 683MB (read)

Single 2GB Transcend USB drive
204.50 for 683MB (write)
63.26 for 683MB (read)

Single 8GB Sandisk drive
197.61 for 683MB (write)
29.73 for 683MB (read)

RAID0 (two Dane-Elec 8GB USB drives)
61.177 for 683MB (write)
17.9 for 683MB (read)

I created a test file with 683 MB of data by funnelling /dev/urandom into it and then copied it to the USB drive(s) to measure write performance. Then I unmounted the USB drive(s) to make sure the buffer cache is emptied. On remounting I measured read performance by copying the test file back to the harddisk. The hard disk used was a Seagate Barracuda 320GB (7200rpm).

If four USB drives (say Sandisk 8GB) can be RAID’ed together on level 0 we would have a cheap SSD. One thing that prevents me from trying this out is the question of reliability. I have not used this setup long enough or stressed it hard enough to be comfortable using this for normal use.

To rig something like this yourself, read this article.

This algorithm has the following steps:

• make doc from html data (clean html)
• identify content nodes (nodes having substantial content)
• prune xml tree to remove irrelevant nodes
• get the most linked node from pruned tree (subtree contains relevant text)
• make the dot graph

I’ve pasted the relevant python module below for easy reading. However, if you want to download the code and hack it, you can get all the files from here.

Code files

• content_extract.py – actual work gets done here (file pasted below)
• cextract.py – cgi front-end which fetched url content and feeds to above script.
• cextract_config.py – cgi script configuration file. You have to adjust this to your environment.

Try it right here and right now

Some samples

• http://news.bbc.co.uk/sport2/hi/motorsport/formula_one/8169436.stm
• http://www.prashanthellina.com/cextract_data/640ca0b7c6e818b2b1bf952a206a6388.html
• http://www.telegraph.co.uk/news/worldnews/europe/france/5913494/Nicolas-Sarkozy-to-slow-down-after-collapsing-while-jogging.html

Please let me know if you find cases for which the algorithm does not work. Even better would be to download the code and hack it up and post back. I am eager to see what you can come up with.

#!/usr/bin/env python

import sys
from cStringIO import StringIO

from lxml import etree #http://codespeak.net/lxml/

IGNORABLE_TAGS = set(['script', 'a'])
MIN_TEXT_LEN = 50

def get_text(node):
    '''
    Given a XML node, extract all the text it contains.
    (does not recurse into children)
    '''
    text = [node.text or '']
    for cnode in node.getchildren():
        tail = cnode.tail
        if tail is not None:
            text.append(cnode.tail)

    text = '\n'.join(text).strip()
    return text

def get_xml(node):
    '''
    Convert the sub-tree from node downwards
    into string XML representation.
    '''
    return etree.tostring(node)

def create_doc(data):
    '''
    Construct XML tree datastructure from xml string representation.
    '''
    parser = etree.HTMLParser()
    doc = etree.parse(StringIO(data), parser)
    return doc

def get_content_nodes(doc):
    '''
    Identify nodes in the XML document that
    have substantial text.
    '''
    nodes = []

    for n in doc.xpath('//*'):
        tag = n.tag

        if tag.lower() in IGNORABLE_TAGS:
            continue

        text = get_text(n)
        if not text:
            continue

        if len(text) < MIN_TEXT_LEN:
            continue

        nodes.append(n)

    return nodes

def make_pruned_tree(content_nodes):
    '''
    Prune the whole XML tree by remnoving nodes
    other than content nodes and their ancestors.
    '''
    nodes = {}
    links = {}

    for node in content_nodes:

        nodes[id(node)] = node

        parent = node.getparent()
        if parent is not None:
            links[id(node)] = id(parent)

        for anode in node.iterancestors():
            _id = id(anode)
            parent = anode.getparent()
            if parent is not None:
                links[_id] = id(parent)

            if _id not in nodes:
                nodes[_id] = anode

    return nodes, links

def get_inlink_counts(links):
    '''
    Given the inter-node links, find out which
    node has maximum number of links coming into it.
    '''
    counts = {}

    for from_id, to_id in links.iteritems():
        count = counts.setdefault(to_id, 0)
        counts[to_id] = count + 1

    return counts

def get_most_linked_node(nodes, links):
    '''
    Identify the node which is most linked.
    (i,e) has most number of inlinks.
    '''
    inlink_counts = get_inlink_counts(links)

    mcount, mid = max([(count, _id) for _id, count in inlink_counts.iteritems()])
    node = nodes[mid]
    return node

def make_dot_graph(nodes, links, chosen_node, stream):
    '''
    Construct the dot format graph representation
    so that graphviz can render the tree for visualization.
    '''
    o = stream

    print >> o, "digraph G {"

    for _id, node in nodes.iteritems():

        tlen = len(get_text(node))
        tag = node.tag

        if tlen:
            text = '%s (%d)' % (tag, tlen)
        else:
            text = tag

        if _id == chosen_node:
            attrs = 'style=filled color=lightblue'
        else:
            attrs = ''

        print >> o, "%s [label=\"%s\" %s];" % (_id, text, attrs)

    for fid, tid in links.iteritems():
        print >> o, "%d -> %d;" % (fid, tid)

    print >> o, "}"

def main():
    # make doc from html data (cleans html)
    doc = create_doc(sys.stdin.read())

    # identify content nodes
    content_nodes = get_content_nodes(doc)

    # prune xml tree to remove irrelevant nodes
    nodes, links = make_pruned_tree(content_nodes)

    # get the most linked node from pruned tree
    mnode = get_most_linked_node(nodes, links)

    # make the dot graph
    make_dot_graph(nodes, links, id(mnode), sys.stdout)

if __name__ == '__main__':
    #Eg: wget "http://blog.prashanthellina.com" -O - | python thisscript.py | dot -Tpng -o /tmp/test.png ; eog /tmp/test.png
    main()

Code

import pprint
from difflib import SequenceMatcher

# http://python-cluster.sourceforge.net/
from cluster import HierarchicalClustering

# input urls to be clustered
urls = [
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814385',
    '#articles',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814335',
    'http://yro.slashdot.org/~drDugan/',
    'http://web.sourceforge.com/privacy.php',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28815123',
    'http://slashdot.org//slashdot.org/~Darkness404',
    'http://slashdot.org//radio.slashdot.org',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814429',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814457',
    'http://slashdot.org//slashdot.org/article.pl?sid=09/07/24/1545238',
    'http://slashdot.org//slashdot.org/comments.pl?sid=09/07/24/1545238&cid=28810581',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28815269',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814657',
    'http://web.sourceforge.com/terms.php'
    'http://slashdot.org//it.slashdot.org/search',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814581',
    'http://xkcd.com/612/',
    'http://web.sourceforge.com/advertising',
    'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814785',
]

# distance function compares two urls and finds the distance
# uses SequenceMatcher from python standard module difflib
def distance(url1, url2):
    ratio = SequenceMatcher(None, url1, url2).ratio()
    return 1.0 - ratio

# Perform clustering
hc = HierarchicalClustering(urls, distance)
clusters = hc.getlevel(0.2)

pprint.pprint(clusters)

Output

[['#articles'],
 ['http://xkcd.com/612/'],
 ['http://web.sourceforge.com/privacy.php'],
 ['http://web.sourceforge.com/advertising'],
 ['http://web.sourceforge.com/terms.phphttp://slashdot.org//it.slashdot.org/search'],
 ['http://yro.slashdot.org/~drDugan/'],
 ['http://slashdot.org//slashdot.org/~Darkness404'],
 ['http://slashdot.org//radio.slashdot.org'],
 ['http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814785',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814429',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&op=Reply&threshold=1&commentsort=0&mode=thread&pid=28814457'],
 ['http://slashdot.org//slashdot.org/article.pl?sid=09/07/24/1545238',
  'http://slashdot.org//slashdot.org/comments.pl?sid=09/07/24/1545238&cid=28810581',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28815123',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28815269',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814385',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814335',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814657',
  'http://slashdot.org//it.slashdot.org/comments.pl?sid=1314601&cid=28814581']]

The reason I bought multiple monitors is to maximize my work area so I do not have to keep switching between overlapping windows. Gnome it seems is ill-suited to effectively and effortlessly managing space.

When I maximize a window on a widescreen monitor, the window takes up the entire space on the screen. Although this is the expected behavior, I could not rest looking at the huge amount of space being wasted. What I would like better is having two windows occupying the height of the screen but sitting right next to each other (i.e. tiled). This way less space is wasted and you get to see both windows at the same time. I could do this in gnome, but with considerable effort, as closing a window and re-opening another requires another round of frantic window arrangement.

In comes a tiling window manager … Tiling window managers do not allow overlapping windows (except for dialogs). They are a good solution when you need to tile windows to occupy all available screen space. Also, most tiling window managers emphasize keyboard control over mouse control. If you are productivity freak you will love the keyboard shortcuts that do away with a painful context switch required in navigating with the mouse.

There are many Tiling Window Managers out there. Rat Poison, Stump WM, Ion, dwm, wmii and XMonad are a few. I chose XMonad because I was able to figure how to integrate XMonad into the Gnome desktop environment. Most of these window managers don’t play well with Gnome. I use a number of Gnome apps and I would hate to not be able to use them.

Okay, here is how you Install XMonad on Ubuntu to work within Gnome …

mkdir ~/.xmonad
cd ~/.xmonad
vim xmonad.hs

Then paste the following into the xmonad.hs file and save it.

import XMonad
import XMonad.Config.Gnome
import XMonad.ManageHook

myManageHook :: [ManageHook]
myManageHook =
    [ resource  =? "Do"   --> doIgnore ]

main = xmonad gnomeConfig
    { manageHook = manageHook gnomeConfig <+> composeAll myManageHook}

sudo apt-get install xmonad libghc6-xmonad-dev

Note that libghc6-xmonad-dev is a 200MB dependency!

vim ~/.gnomerc

Add this line .gnomerc file and save.

export WINDOW_MANAGER=xmonad

The installation is done. Now to experience your new Window Manager, log out and then log back in. You will see your usual desktop with Gnome panels.

To learn more about XMonad and how to use it, follow these links:

http://ubuntu-snippets.blogspot.com/2008/08/xmonad-tiling-window-manager.html
http://tombuntu.com/index.php/2009/03/17/introduction-to-the-xmonad-tiling-window-manager/
https://www.haskell.org/haskellwiki/Xmonad/Using_xmonad_in_Gnome/0.5

Recently, I went to Veveo’s main office near Boston, USA and had the privilege of experiencing a finger freezing winter! (Not to mention a three day power-cut which I spent under multiple layers of blankets).

A few weeks before I was going to return to India, I started shopping. One of things I bought was a Refurbished NVidia GeForce 9800 GTX+ by EVGA. It was the best deal I could find on NewEgg in terms of value for money. I bought it primarily to have a betterr experience when flying over Paris … in Google Earth.

This is the first graphics card I bought ever and was very excited when I received it. I was surprised to see how big graphics cards have become nowadays (compared to S3 cards of the decade gone past). While oggling at the card I noticed that it had two video outputs. I had heard of dual-head setups but always considered them a distant reality considering my cash-strappedness as a college student. This sparked off an urge to finally setup my own Dual monitor setup back in Bangalore.

I got back to India and promptly headed to SP Road in Bangalore. After some asking around, I figured that the best choice at the moment was two Samsung SyncMaster 2233SW’s each capable of 1920×1080 (Yes, HD). I bought both for about 22,000 Rupees (about USD 420).

I set them up in Linux and upgraded to the latest (at the time) Nvidia drivers (180.x). I spent a few hours trying to hide a satisfied smile lest people thing I had gone nuts.

Dual monitors give you more screen space to work with. They will help you reduce Window-Switching and Workspace-Switching which does save time as I have observed. Now that I have experience the dual-head setup, I am never going back to using a single monitor. It is painful So much did I feel this that I bought a low-end Nvidia GeForce card (7200) with dual-head support and stuck it into my computer at work

If you do not already have a dual-head setup, definitely consider an upgrade. You are worth it:)

To learn more about Microsoft Surface head over to:

• Microsoft’s page on Surface
• Wikipedia article on Microsoft Surface
• Watch a Youtube video on Microsoft Surface

Unboxing Pictures

Some observations:

• It is very heavy!
• and expensive (around $15,000)
• The power socket is hidden underneath and is very difficult to access. The power button is equally well hidden and difficult to find.
• Installation was non-trivial. The touch input did not start working out of the box. We had to use the bundled mouse to initial installation steps.
• The “surface shell” with the ripples in the water is a great way to understand the potential of this device. It feels like you are touching water! and your brain expects that water will drip when you lift your fingers up. I think it is more realistic (compared to devices with smaller touch screens) because of the size of the display and the fact that it is aligned horizontally making it more natural.
• Since rear-projection is used for the display, the viewing angle is very wide (nearly 180 degrees)
• The matte finish on the touch surface as a good feel (almost like paper).

Note that you will need to have Python installed to try out the script and the examples in this article. I believe that the code is simple enough to be understood with minimal or no understanding of the Python language. If any part of the article is not clear, feel free to point it out to me. Thank you.

Estimating difficulty

Let us take a look at the following problems.

Problem 1

5 +
3

Problem 2

99999 +
12345

Now, which problem is more difficult? It is quite obvious that Problem 2 is more difficult. But why? One answer would be – “because Problem 2 involves the addition of two large numbers”. Fine. Consider this now …

Problem 3

1000000 +
1000001

Is Problem 3 more difficult than Problem 2 because the numbers undergoing addition are bigger? The intuitive answer is “No”. But why? Because the time it takes to compute the result is lesser. Why? Because the number of operations performed during the course of solving Problem 3 are lesser than those of Problem 2? No.

Problem 3 is easier than Problem 2 because the nature of the operations performed in Problem 3. The operations there are simpler.

0 + 1,
0 + 0,
1 + 1

are arguably simpler operations than

9 + 5,
9 + 2,
4 + 9

I’ve attempted to capture the basic operations we perform while doing arithmetic and assign a level of difficulty to each. I’ve then emulated the algorithms we follow to compute solutions to such problems. By doing the following, it becomes possible to estimate the “difficulty” of an arithmetic problem (involving the basic operations).

Operation difficulties

Addition

addition_difficulties = {
    'digit_zero' : 1,   # any digit added to zero
    'even_even'  : 2,   # sum of even digits
    'odd_odd'    : 2,   # sum of odd digits
    'even_odd'   : 3,   # sum of even and odd digits
    'carry'      : 2    # difficulty of carry (for remembering and then adding)
}

Here is the function which computes the addition difficulty. It is a recursive function that can compute the addition difficulty for n numbers. It computes the sum and difficulty of the first two numbers and then inserts the sum at the head of the list of n numbers in place of the two numbers just summed. It then calls itself with the modified list.

def compute_addition_difficulty(*numbers):
    '''
    Generates a difficulty number and sum for given
    list of numbers for the addition operation
    *args - integers
    returns: (sum, difficulty)

    >>> compute_addition_difficulty(0, 0)
    (0, 1)

    >>> compute_addition_difficulty(0, 1)
    (1, 1)

    >>> compute_addition_difficulty(1, 1)
    (2, 2)

    >>> compute_addition_difficulty(1, 2)
    (3, 3)

    >>> compute_addition_difficulty(2, 2)
    (4, 2)

    >>> compute_addition_difficulty(19, 9)
    (28, 5)

    >>> compute_addition_difficulty(99999, 12345)
    (112344, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0

    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = num1.rjust(max_length, '0')
    num2 = num2.rjust(max_length, '0')

    difficulty = 0
    carry = 0
    r = reversed
    ad = addition_difficulties
    sum = []

    for index, (d1, d2) in enumerate( izip( r(num1), r(num2) ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)

        if not d1 or not d2: difficulty += ad['digit_zero']
        elif d1_is_even and d2_is_even: difficulty += ad['even_even']
        elif not d1_is_even and not d2_is_even: difficulty += ad['odd_odd']
        elif d1_is_even != d2_is_even: difficulty += ad['even_odd']

        dsum = d1 + d2 + carry

        if dsum > 9:
            carry = 1
            difficulty += ad['carry']
        else:
            carry = 0

        sum.append( str(dsum % 10) )

    if carry:
        sum.append( str(carry) )

    sum.reverse()
    sum = ''.join(sum)
    sum = int (sum)

    numbers = [sum] + numbers[2:]

    sum, sub_difficulty = compute_addition_difficulty(*numbers)

    difficulty += sub_difficulty

    return sum, difficulty

Subtraction

subtraction_difficulties = {
    'digit_zero' : 1,    # difference of zero and any digit
    'same_digits': 1,    # difference of same values digits
    'even_even'  : 2,    # difference of even digits
    'odd_odd'    : 2,    # difference of odd digits
    'even_odd'   : 3,    # difference of even and odd digits
    'borrow'     : 2,    # doing a borrow
    'twodigit_digit' : 4 # difference of two-digit number and digit
}

The subtraction function is also recursive and operates similar to addition in that respect. Before looking at the subtraction algorithm, take a look at how “borrowing” is implemented. Let us say we are trying to perform the following,

200005 -
     6

After borrowing the number would be, 19999(1)5. We would then subtract 6 from 15 and proceed. The do_borrow() function captures this aspect of substraction.

def do_borrow(num, index):
    if index == len(num)-1: raise Exception('cannot perform borrow')

    num_borrows = 1
    next_digit = int(num[index+1])

    if next_digit > 0:
        num[index+1] = str(next_digit-1)

    else:
        num[index+1] = str(9)
        num_borrows += do_borrow(num, index+1)

    return num_borrows

This implementation is a bit confusing so check out this example (do_borrow() applied to the problem mentioned above).

>>> x = list('200005')
>>> x.reverse()
>>> x
['5', '0', '0', '0', '0', '2']
>>> do_borrow(x, 1)
4
>>> ''.join(x)
'509991'
>>> x.reverse()
>>> x
['1', '9', '9', '9', '0', '5']

Note that do_borrow returned 4, which indicates that the difficulty of performing this borrow operation is 4. Also note that do_borrow takes a list of digits in reversed order. It takes a list because the result is provided in-place (remember that Python strings are immutable). Now that you have seen how the borrowing works, all introduce the subtraction function.

def compute_subtraction_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the subtraction operation
    *args (tuple) - integers
    returns: (difference, difficulty)

    >>> compute_subtraction_difficulty(0,0)
    (0, 1)

    >>> compute_subtraction_difficulty(1,0)
    (1, 1)

    >>> compute_subtraction_difficulty(1,1)
    (0, 1)

    >>> compute_subtraction_difficulty(2,1)
    (1, 3)

    >>> compute_subtraction_difficulty(4,2)
    (2, 2)

    >>> compute_subtraction_difficulty(4,3)
    (1, 3)

    >>> compute_subtraction_difficulty(100,1)
    (99, 10)

    >>> compute_subtraction_difficulty(5000007,9)
    (4999998, 22)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 0, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num1 = str(num1)
    num2 = str(num2)

    max_length = max([len(num1), len(num2)])
    num1 = list(num1.rjust(max_length, '0'))
    num2 = list(num2.rjust(max_length, '0'))

    difficulty = 0
    borrow = 0
    sd = subtraction_difficulties
    difference = []
    num1.reverse()
    num2.reverse()

    for index, (d1, d2) in enumerate( izip( num1, num2 ) ):
        d1 = int(d1)
        d2 = int(d2)

        d1_is_even = is_even(d1)
        d2_is_even = is_even(d2)

        if d1 > d2:
            if not d1 or not d2: difficulty += sd['digit_zero']
            elif d1_is_even and d2_is_even: difficulty += sd['even_even']
            elif not d1_is_even and not d1_is_even: difficulty += sd['odd_odd']
            elif d1_is_even != d2_is_even: difficulty += sd['even_odd']
            ddiff = d1 - d2

        elif d1 < d2:
            num_borrows = do_borrow(num1, index)
            difficulty += sd['borrow']*num_borrows
            ddiff = 10 + d1 - d2
            difficulty += sd['twodigit_digit']

        elif d1 == d2:
            difficulty += sd['same_digits']
            ddiff = 0

        difference.append( str(ddiff) )

    difference.reverse()
    difference = ''.join(difference)
    difference = int (difference)

    numbers = [difference] + numbers[2:]

    difference, sub_difficulty = compute_subtraction_difficulty(*numbers)

    difficulty += sub_difficulty

    return difference, difficulty

Multiplication

multiplication_difficulties = {
    'carry'  : 1,   # carry operation, summation difficulty is seperate
    'offset' : 1,
}

The basic operation of multiplying big numbers is one digit by one digit multiplication. I've tried to capture the difficulty of this operation as follows

def get_single_digit_multiplication_difficulty(d1, d2):
    '''
    Max value of multiplication of two digits is 81 (9*9).
    Difficulty of d1*d2 increases as the resulting value
    of the multiplication increases. thereby 9*9=81 is most difficult
    and 0*0 is least difficult.

    We will represent this difficult with value from 1-4 (inclusive)

    Note that the difficulty will be incremented by 1 for presence
    of odd digit in the operands (except for 1 and 5 because it is arguably
    easier to multiply)

    >>> get_single_digit_multiplication_difficulty(0, 1)
    (0, 1)
    >>> get_single_digit_multiplication_difficulty(1, 1)
    (1, 1)
    >>> get_single_digit_multiplication_difficulty(2, 5)
    (10, 1)
    >>> get_single_digit_multiplication_difficulty(2, 7)
    (14, 2)
    >>> get_single_digit_multiplication_difficulty(2, 6)
    (12, 1)
    >>> get_single_digit_multiplication_difficulty(8, 9)
    (72, 5)
    >>> get_single_digit_multiplication_difficulty(8, 
    (64, 4)
    '''

    if not d1 or not d2: return 0, 1 

    res = d1 * d2
    difficulty = math.ceil((4/81.) * res)

    # odd numbers are harder to multiply except 1 and 5
    if d1 not in [1,5] and d2 not in [1,5] and (is_odd(d1) or is_odd(d2)):
        difficulty += 1

    return res, int(difficulty)

At the next level, the operation would be multiplying a multi-digit number by a single digit, which I call simple multiplication. Over here I take into account the difficulty of carry. I hope the following code is self explanatory.

def compute_simple_multiplication_difficulty(num, digit):
    '''
    >>> compute_simple_multiplication_difficulty(1, 0)
    (0, 1)
    >>> compute_simple_multiplication_difficulty(1, 1)
    (1, 1)
    >>> compute_simple_multiplication_difficulty(2, 1)
    (2, 1)
    >>> compute_simple_multiplication_difficulty(10, 1)
    (10, 2)
    >>> compute_simple_multiplication_difficulty(15, 1)
    (15, 2)
    >>> compute_simple_multiplication_difficulty(15, 5)
    (75, 7)
    >>> compute_simple_multiplication_difficulty(999, 7)
    (6993, 25)
    '''
    num = str(num)

    result = []
    md = multiplication_difficulties
    carry = 0
    difficulty = 0

    for index, d in enumerate(reversed(num)):
        d = int(d)
        res, s_diff = get_single_digit_multiplication_difficulty(d, digit)
        difficulty += s_diff

        if (carry):
            res, carry_sum_difficulty = compute_addition_difficulty(res, carry)
            difficulty += carry_sum_difficulty + md['carry']

        carry = res/10
        result_digit = int(str(res)[-1:])
        result.append( str(result_digit) )

    if carry:
        result.append( str(carry) )

    result.reverse()
    result = ''.join(result)
    result = int(result)

    return result, difficulty

Simple multiplication is a basic operation of complex multiplication (multi-digit multiplied by multi-digit). Let us see an example of "complex multiplication" which the multiplication code follows.

    345 x
    123
  -----
   1035
   690x  # result is "offset" or multiplied by 10
  345xx  # result if "offset" or multiplied by 100
  -----
  42435  # result of summation of above numbers
  -----

The first part of the multiplication is to perform simple multiplications - 345x3, 345x2, 345x1 and to offset the numbers accordingly. The second part of the operation is to sum the numbers. I used the addition algorithm to achieve the second part. Check out the multiplication function.

def compute_multiplication_difficulty(*numbers):
    '''
    Generates a difficulty number and result for given
    list of numbers for the multiplication operation
    *args (tuple) - integers
    returns: (product, difficulty)

    >>> compute_multiplication_difficulty(0,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,0)
    (0, 1)
    >>> compute_multiplication_difficulty(1,1)
    (1, 1)
    >>> compute_multiplication_difficulty(2,1)
    (2, 1)
    >>> compute_multiplication_difficulty(5,1)
    (5, 1)
    >>> compute_multiplication_difficulty(5,2)
    (10, 1)
    >>> compute_multiplication_difficulty(17,2)
    (34, 7)
    >>> compute_multiplication_difficulty(17,29)
    (493, 20)
    >>> compute_multiplication_difficulty(17,29,3)
    (1479, 31)
    >>> compute_multiplication_difficulty(1776,29,3)
    (154512, 77)
    '''

    numbers = list(numbers)
    if len(numbers) == 0: return 1, 0
    elif len(numbers) == 1: return numbers[0], 0

    num1, num2 = numbers[:2]
    if num1 < num2: num1, num2 = num2, num1

    num2 = str(num2)

    difficulty = 0
    borrow = 0
    md = multiplication_difficulties
    m_numbers = []

    for index, d in enumerate(reversed(num2)):

        d = int(d)

        m_number, m_diff = compute_simple_multiplication_difficulty(num1, d)
        difficulty += m_diff

        if index:
            m_number = int(m_number * math.pow(10, index))
            difficulty += md['offset']

        m_numbers.append(m_number)

    m_numbers_sum, m_numbers_diff = compute_addition_difficulty(*m_numbers)
    difficulty += m_numbers_diff

    numbers = [m_numbers_sum] + numbers[2:]
    product, m_diff = compute_multiplication_difficulty(*numbers)

    difficulty += m_diff

    return product, difficulty

Division

division_difficulties = {
    # long division
    'use_digit'       : 1,  # brinding down digit from dividend
    'multiple_lookup' : 1,  # looking up precomputed multiple of divisor
    'quotient_update' : 1,  # updating quotient with digit or period
}

Implementing long division posed a problem because my understanding of the mechanics behind the long division algorithm was minimal if not inexistent. I spent some time trying to "reverse-engineer" it. I came across "Egyptian Division" which made things clearer. With a little help, I managed to implement the following division algorithm. Please let me know, if you come up with a better approach.

def compute_division_difficulty(dividend, divisor, precision):
    '''
    Generates a difficulty number, quotient and remainder
    for dividend / divisor
    @precision (int) -- max required number of digits after decimal point in quotient
    returns: (quotient, remainder, difficulty)

    >>> compute_division_difficulty(54, 5, 0)
    (10.0, 4, 6)
    >>> compute_division_difficulty(50, 5, 0)
    (10.0, 0, 6)
    >>> compute_division_difficulty(575, 6, 0)
    (95.0, 5, 60)
    >>> compute_division_difficulty(575, 6, 1)
    (95.829999999999998, 20, 112)
    >>> compute_division_difficulty(6, 9, 1)
    (0.66000000000000003, 60, 50)
    >>> compute_division_difficulty(410, 2, 1)
    (205.0, 0, 54)
    '''

    if not divisor: raise Exception('Division by Zero')
    if not dividend: return 0, 0, 1

    dividend = str(dividend)

    divisor  = str(divisor)

    difficulty = 0
    previous_multiples_difficulty = 0
    precision_reached = 0
    decimal_point_used = 0
    dd = division_difficulties
    num = []
    quotient = []

    num = dividend[0]
    difficulty += dd['use_digit']
    index = 0

    while 1:
        q_digit = int(num) / int(divisor)

        multiple, multiple_difficulty = compute_multiples_difficulty(int(divisor), q_digit)
        difficulty += int(math.fabs(multiple_difficulty - previous_multiples_difficulty))
        if previous_multiples_difficulty: difficulty += dd['multiple_lookup']
        previous_multiples_difficulty = max(multiple_difficulty, previous_multiples_difficulty)

        quotient.append( str(q_digit) )
        difficulty += dd['quotient_update']

        if decimal_point_used:
            precision_reached += 1

        num, sub_difficulty = compute_subtraction_difficulty(int(num), multiple)
        difficulty += sub_difficulty
        num = str(num)

        index += 1

        if index == len(dividend):
            if precision == 0: break
            quotient.append('.')
            difficulty += dd['quotient_update']
            decimal_point_used = 1

        if not decimal_point_used:
            num += dividend[index]
        else:
            num += '0'

        difficulty += dd['use_digit']

        if (len(num) == 1 and not int(num)) or precision_reached >= precision + 1:
            break

    remainder = int(num)
    quotient = float(''.join(quotient))

    return quotient, remainder, difficulty

You must've noticed the usage of compute_multiples_difficulty(). In long division, at every step, you will try to find the largest multiple of the divisor less than or equal to the number in hand to proceed further. During the process of division, if you've computed the 5th (say) multiple of the divisor with difficulty N. The computation of 6th multiple at a later point in the division is difficulty(lookup of 5th multiple) + difficulty(6-5th multiple).

Results

#Problem 1
>>> compute_addition_difficulty(5, 3)
(8, 2)

#Problem 2
>>> compute_addition_difficulty(99999, 12345)
(112344, 22)

#Problem 3
>>> compute_addition_difficulty(1000000, 1000001)
(2000001, 

Problem 1: 2
Problem 2: 22
Problem 3: 8

The End

I wish I could have written a more detailed explanation instead of sprinkling this article with code. Time however prevents me from doing so . It is some relief that Python is a wonderful language for readability and the code samples above are pretty close to pseudo-code.

I will post back when I complete the program to generate arithmetic problems by order of difficulty. Until then, Adios amigos. Almost forgot! Here is the code.

In between I did some projects using Java, C#, C, C++. None of these impressed me too much. I hated Java’s imposition of stiff rules and it’s dogged adherence to “everything in a class” attitude. C# was better. C++ just turned me off because of the monster it is. I did not like C at all because of its total lack of automated memory handling (like GC). I’ve been doing a lot of coding in C now-a-days as part of my job and I must admit that I like it a lot for its simplicity in primitives and promise of “closeness to hardware” and hence the predictability and performance.

I did a small part of my final year project using Python. However, for some unfathomable reason, Python did not impress me at all then. When I started working at Veveo I used Python for a project and got hooked. It’s simplicity and “readability” got me. The power of wielding this tool got me drunk

Python was designed from the beginning to be a “easy to read” language. Most, if not all, of the syntax is intuitive. The indentation adds to the readability aspect. The policy of “only one way to do a thing” does wonders for readability. Everyone does a certain thing only the “one” way. If you are wondering why the heck I am talking so much about readability, you should consider the fact that an average programmer spends most of his time “reading” code. You have to read your code after you’ve just written it. You’ve to read your code the next day when you resume work. You’ve to read your code the moment a bug is found. You have to read your code when someone asks you how some aspect of it works a couple of months later. You’ve have to read your code when making a teeny-weeny feature addition. I just cannot emphasize enough how much time is spent is just reading. There have been times when I would spend a whole day just reading code and finally making “a single line of code change” at the end of the day!

So there it is. Python makes it possible to write readable code and that does wonders to programmer productivity. Maintaining your code becomes easier. Understanding your collegues code becomes easier and most of all understanding code written by someone across the world becomes easier – so you can start reusing components more quickly and with more confidence than ever before.

I simply love Python.

You must be wondering where I am taking this discussion… because the title says something about a Python being abused. Who is abusing the Python anyway?

I’ve noticed how newbies code in Python and found it particulary intriguing. What is interesting here is that every person comes from a certain programming background and are used to doing things in a certain way. When they are thrown into a situation where they have to learn a new language and write some code in it, they invariably apply the vast experience they have in their language of choice

I’ve had the oppurtunity of observing people from Java, C, Perl, VB (yes, Perl) backgrounds writing code in Python. The Java guys stress test multiple inhertitance in Python and bring the much cherished “everything in a class” practice to the Python. The C guys who are more often than not obsessed with performace and optimization put their brains to work and implement a strcpy using a “for loop” and insist on doing a “shift” instead of “division/multiplication”. The Perl guys just don’t seem to like the alphanumerals. They craft Python code with ingenious application making it look very concise. The more characters in one line the better the code. The more non-alphanumerals the better coder you are. That’s the way of the “Perl’ies”. The VB guys languish for a while complaining constantly about the lack of a proper IDE and after trying out various Python editors, decide to call it quits and go home to comfortable VB. I know, I know ….. I was a VB guy too and I did search for IDE’s too … But then I found VIM and everything was good

I’ve had the good (snigger) fortune of maintaining some of these brilliant artifacts and had my share of nightmares and laugh-outs. I thought I had seen it all, until I saw something today. I told myself — “Never underestimate a brilliant C programmer who has found exec and eval in Python” … Yes, you can quote me on this

    guido = "is speechless"
    larry = "went nuts"
    sergey = "has seen it all now"
    ...
    ...
    for idx in ['guido','larry','sergey']:
        idxv=eval(idx)
        if(not idxv and dd.has_key(idx)):
            idxv='%s="%s"' %(idx,dd[idx])
            exec(idxv)

    ...
    ...

No….. I don’t think I’ve seen it all….

Features like “Places” (Bookmarks on steroids), Cairo for rendering and OS specific widgets have made the best browser better. At the time of writing of this blog post 6 million plus downloads from around the world have already happened.

Everywhere I look at work, I see the “Download Day” certificate from Mozilla corp … I got one myself too

But the question is ….

Do you know who else got the certificate ???

Who else but Billy and Ballmy

I’ve been reading up on TDD and it has struck me as particularly useful methodology to achieve “clean code that works”. TDD encourages writing unit tests to cover all the code (because by definition, you write a test before a line of code is written). Because all your code is covered you are freed from the fear of breakage due to change and can instantly be more confident and productive. Also, the test cases act as a specification in code – very useful.

Python has standard modules, unittest and doctest to help you write test cases. I simply love doctest. It alleviates much of the pain of writing a test case (setup and all) besides acting as “executable documentation”. The unittest module has a Java legacy and is not to my taste. Also, I wanted to find a solution that would help in automated test enumeration (discovery) in my source directories without having to write any “infrastructure” code. One more thing I was looking for was a way to run both unit tests and doc tests together.

After a bit of searching, I found “Nose“. Nose is a clone of “py.test” which I liked better than the original (subjectively). To get a feel of “Nose”, I set up some python test files.

The following is the directory structure and the contents of the files. I’ve put in both unit tests and doc tests in the files to see how “Nose” handles them. Also, the tests are spread across directories. Note that I had to put an “__init__.py” to allow “Nose” to import tests in a subdirectory.

The setup

The directory structure

prashanth@prashanth-desktop:~/tmp$ tree
.
|-- bingo.py
|-- somedir
|   |-- __init__.py
|   `-- test_another.py
`-- test_prashanth.py

1 directory, 4 files

bingo.py

def boing(a, b):
    '''
    >>> boing(10, 20)
    30
    '''
    return a+b

def boing1(a, b):
    '''
    >>> boing1(10, 20)
    40
    '''
    return a+b

test_prashanth.py

def test_a():
    assert 1

def test_b():
    print "hello"
    assert 0

somedir/test_another.py

def test_bingo():
    raise Exception('hgello')

Installing “Nose”

sudo easy_install nose

If you don’t have easy_install, head over here to get information on installation.

Running the tests

Now that “Nose” is installed, let us run the tests,

nosetests --with-doctest

The output is

..E.F
======================================================================
ERROR: somedir.test_another.test_bingo
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/lib/python2.5/site-packages/nose-0.10.2-py2.5.egg/nose/case.py", line 182, in runTest
    self.test(*self.arg)
  File "/home/prashanth/tmp/somedir/test_another.py", line 2, in test_bingo
    raise Exception('hgello')
Exception: hgello

======================================================================
FAIL: test_prashanth.test_b
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/lib/python2.5/site-packages/nose-0.10.2-py2.5.egg/nose/case.py", line 182, in runTest
    self.test(*self.arg)
  File "/home/prashanth/tmp/test_prashanth.py", line 7, in test_b
    assert 0
AssertionError:
-------------------- >> begin captured stdout << ---------------------
hello

--------------------- >> end captured stdout << ----------------------

----------------------------------------------------------------------
Ran 5 tests in 0.057s

FAILED (errors=1, failures=1)

The first line in the output is the "test progress" indication (..E.F) . When a test succeeds, a '.' is written. When a test fails, an 'F' is written. When a test throws an Exception, an 'E' is written. Very useful to get a sense of progress as a huge test suite being executed.

"Nose" captures the stdout and stderr when a test case fails to help you debug the issue. To learn more about using "Nose" go here.

These two files are splits of a compressed file which contains all of the Project Gutenberg English e-books downloaded about a week before the date of this post.

gutenberg_en_files.tar.bz2.0 (2.0GB)

gutenberg_en_files.tar.bz2.1 (1.4GB)

Unigrams along with frequency count from the text data above

gutenberg_en_unigrams.tar.gz (7.4MB)

Bi-grams and Tri-grams along with frequency count from the text data above

gutenberg_en_bi_tri_grams.tar.gz (493MB)

I had to split the files because my webserver has a limitation in serving out files larger than 2GB. After downloading the files, do this

mv gutenberg_en_files.tar.bz2.0 gutenberg_en_files.tar.bz2
cat gutenberg_en_files.tar.bz2.1 >> gutenberg_en_files.tar.bz2
rm gutenberg_en_files.tar.bz2.1

If you find the data useful, I’d be delighted to hear the context in which you made use of it.

Get Project Gutenberg Ngram data

The Ngram data contains bi-grams and tri-grams for now. I plan to generate uni-grams soon. I’ve made the data available here so you can download and use it! This data contains all of the e-books hosted by Project Gutenberg (which means the data contains English, French, German and other languages). If you want an English only dataset, check back in a week or two. I am in the process of generating the same.

The Ngram data containing bi-grams and tri-grams. Each line is prepended with the occurence count.

gutenberg_ngrams.tar.bz2 (624 MB)

This is the compressed tarball of all the txt files in Project Gutenberg (as of a week before this blog post). Note that you don’t need this file unless you want to generate the Ngrams yourself using the scripts provided below.

gutenberg_files.tar.bz2.0,
gutenberg_files.tar.bz2.1,
gutenberg_files.tar.bz2.2 (5.3 GB)

My webserver (Apache) has a problem serving out files bigger than 2GB, so I had to split the file up. After you download the splits, you have to join them like this.

mv gutenberg_files.tar.bz2.0 gutenberg_files.tar.bz2
cat gutenberg_files.tar.bz2.1 >> gutenberg_files.tar.bz2
cat gutenberg_files.tar.bz2.2 >> gutenberg_files.tar.bz2

To decompress the files, you will need bunzip2 on *nix/Cygwin. On Windows, use 7zip.

Generate the data yourself

In case you want to generate the Ngrams yourself by processing the Project Gutenberg data files, follow these instructions. You will have to get the Project gutenberg data files. Use the following command to get all the English language files in txt format.

mkdir gutenberg
cd gutenberg
wget -w 2 -m "http://www.gutenberg.org/robot/harvest?filetypes[]=txt&langs[]=en"

The txt files are compressed and stored in files ending with .zip extension. These zip files are spread across multiple directories. The following command will move the zip files into the “gutenberg” directory you created in the above step.

for i in `find . -name "*.zip"`; do mv $i . ; done;

Now that all the zip files are in the same directory, unzip the zip files.Some zip files may contain files other than .txt’s. The following command extracts only .txt’s in the zip files.

cd ..
mkdir gutenberg_txt
for i in `find gutenberg -name "*.zip"`; do unzip $i \*.txt -d gutenberg_txt/ ; done;
cd gutenberg_txt
for i in `find . -name "*.txt"`; do mv $i . ; done;
cd ..

The gutenberg txt files have gutenberg headers and footers which should be removed lest they skew the frequency of Ngrams. The script “remove_gutenberg_text.py” does exactly this. The “generate_ngrams.py” script creates uni, bi and tri-grams of whatever text is piped into it. The following command pipes all the txt files through both the scripts to create the ngrams file.

for i in `find gutenberg_txt/ -name "*.txt"`; \
do cat $i | python remove_gutenberg_text.py | \
grep -i -v "project gutenberg" |\
 python generate_ngrams.py >> gutenberg_ngrams; done;

Now you have to count the number of times an ngram occurs. The following sequence of commands process the ngrams file generated above and produce a file with the frequency counts of the ngrams. Note that the “512K” option to sort is because I had to run these scripts on my host which kills processes that take too much memory. If you have a machine with a lot of memory, sorting can be significantly faster if you use a higher value, say “1G”.

sort -S 512K -T tmp_sort/ gutenberg_ngrams > gutenberg_ngrams.sorted
uniq -c gutenberg_ngrams.sorted > gutenberg_ngrams.counted
sort -S 512K -T tmp_sort/ gutenberg_ngrams.counted > gutenberg_ngrams.counted.sorted

Gutenberg data processing scripts

• remove_gutenberg_text.py — removes Project Gutenberg header and footer from txt files
• generate_ngrams.py — generate uni, bi and tri-grams for any text

Do get back

If you use this data, I would really appreciate if you get back with details about how you used it in the context of your project

I got inspired to bring my long standing idea to fruition and the outcome is Wordza.

Wordza is a smart word quizzing service designed to help you rapidly learn new words. It adapts to your level and continually challenges you to get better. Preparing for GRE/SAT/CAT? Use Wordza 15 minutes a day.

Questions have difficulty ratings ranging between 1 and 100. The ratings are derived from user activity. A question is easy if a lot of people get it right and difficult when very few do!

You start at difficulty level 50. If you get three questions right in a row, you drive up the difficulty level a notch. On the other hand, answering a question wrong will reduce the difficulty level by one.

If you are interested in the implementation … I used Python, MySQL behind Apache to get this up. When I started making it, I wanted to keep it simple and make it work fast. I hope I’ve met both these requirements. Do give it a try and let me know what you think.

Alexa collects statistics about visits by internet users to websites through the Alexa Toolbar. Based on the collected data, Alexa computes site ranking. By examining the Alexa rank of a site, you can get a rough idea of how popular the site is. Many argue that Alexa rank is misleading but it has its uses.

The Alexa rank script

You can find out the Alexa rank for any site by using this page. However, if you want to programatically get the Alexa rank, you can do it using this script.

Get the Alexa rank script

Using the script

After downloading the script, give it execute permission by doing this. You will need to have Python installed.

chmod +x get_alexa_rank.py

$ ./get_alexa_rank.py google.com
popularity rank = 2
reach_rank = 1

$ ./get_alexa_rank.py wikipedia.com
popularity rank = 7
reach_rank = 6

$ ./get_alexa_rank.py blog.prashanthellina.com
popularity rank = 557287
reach_rank = 482289

$ ./get_alexa_rank.py www.inexistantsite.com
popularity rank = -1
reach_rank = -1

How does the script work?

If you make a http request for the following url,

http://data.alexa.com/data?cli=10&dat=snbamz&url=$URL

after replacing $URL with the url of the site for which you need the Alexa rank, the following XML response is sent out. I tried with “http://blog.prashanthellina.com”.

The script parses the XML response and extracts POPULARITY/@TEXT and REACH/@RANK.

If you are looking for a PHP script for doing the same, check this out.