by Pravin Paratey

Lesson 5 - Adding standard GUI elements

In this lesson, we’ll learn how to add standard GUI elements like the statusbar and the toolbar. We’ll learn about the Common Controls library - which let us add GUI elements like the RichEdit box, the Treeview control, the Listbox/Listview controls and more! Click here to view the full list.

Introducing Common Controls

Windows includes a library called the Common Controls library which lets you add many Windows GUI elements. These elements aren’t part of the core Windows API but are available through a dll - Comctl32.dll.

Before using any UI element from Comctl32.dll, we must load the dll. This can be conveniently done by calling the InitCommonControlsEx() function in MainWindow.cpp:

#include <windows.h>
#include <windowsx.h>
#define _WIN32_IE 0x0500 // To support INITCOMMONCONTROLSEX
#include <commctrl.h>
#include "MainWindow.h"
#include "AboutDialog.h"

First, we include the Commctrl.h, and then add the following code to MainWindow.cpp

bool MainWindow::Run(int nCmdShow)
        return false;

    // Initialize Common controls
    // Ensure common control DLL is loaded
    icx.dwSize = sizeof(INITCOMMONCONTROLSEX);
    icx.dwICC = ICC_BAR_CLASSES; // Specify BAR classes
    InitCommonControlsEx(&icx); // Load the common control DLL

    m_hwnd = CreateWindowEx(

Before you hit build, you must add comctl32.lib to your linker path. This is needed to resolve function references as Comctl32.dll is an external library. To do this, go to Project > Build options, select the Linker settings tab, click the Add button and enter libcomctl32.a as illustrated in the figure below.

Adding comctl32.lib

Adding a statusbar

Adding a statusbar is extremely easy. Commctrl.h contains the function CreateStatusWindow() to create a statusbar. So where do we call this function? In lesson 3, we learnt about the Windows Message Queue and how Windows uses it to notify our application of events.


We are going to look at two messages that Windows passes to our application. The first is the WM_CREATE. This message is posted to the Message Queue of a window after it has been successfully created. This is where you would want to add any UI elements that you want to create.

// MainWindow.h
    HWND m_hwnd;
    static HWND m_hStatusbar;
// MainWindow.cpp
HINSTANCE MainWindow::m_hInstance = NULL;
HWND MainWindow::m_hStatusbar;

Lets create a separate function to draw the statusbar,

// Creates the toolbars and statusbar
// Parameters:
//  cs - Contains initialization parameters
// Returns:
//  void
bool MainWindow::OnCreate(HWND hwnd, LPCREATESTRUCT lpcs)
    // Create Statusbar
    MainWindow::m_hStatusbar = CreateStatusWindow(WS_CHILD|WS_VISIBLE, "Ready", hwnd, IDC_STATUSBAR);
    return true;

Define IDC_STATUSBAR as 102 in resource.h


Try resizing the window now. Did you notice that the statusbar does not resize but retains its original size and position?

Breaks on resize

This can be fixed by handing the WM_SIZE message. WM_SIZE is passed to your application whenever the user resizes a window, minimizes or maximizes it.

    switch (msg)
    case WM_SIZE:
        // Resize the statusbar;
    case WM_DESTROY:

The statusbar is also a Window which can send and receive messages. We could’ve overridden its message handling proc had we wanted to add custom functionality. For now, we just pass the WM_SIZE message and its parameters to the Statusbar. The statusbar is smart enough to know how to resize itself within its parent container.

LRESULT CALLBACK MainWindow::MainWndProc (HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
    switch (msg)
    case WM_SIZE:
        // Resize the statusbar

Adding toolbars

We are going to add two toolbars to our application. A standard toolbar containing buttons like [New, Open, Save] and a paint toolbar which will contain buttons like [Draw Line, Draw Square, etc]. The first thing to do is add the HWND variables (remember a toolbar is just a specialised Window!) to MainWindow.cpp and MainWindow.h,

HINSTANCE MainWindow::m_hInstance = NULL;
HWND MainWindow::m_hStatusbar = NULL;
HWND MainWindow::m_hMainToolbar = NULL;
HWND MainWindow::m_hPaintToolbar = NULL;
    static HWND m_hStatusbar;
    static HWND m_hMainToolbar;
    static HWND m_hPaintToolbar;
    static char m_szClassName[];

Lets head to our OnCreate method and add code to create a toolbar. This involves,

  1. Creating a toolbar window and specifying it’s style.
  2. Creating an Imagelist to hold the images visible on the toolbar buttons.
  3. Creating a TBBUTTON structure which specify the buttons and their properties.
bool MainWindow::OnCreate(HWND hwnd, LPCREATESTRUCT lpcs)
    const int numbuttons1 = 4;
    // Create Main Toolbar
    MainWindow::m_hMainToolbar = CreateWindowEx(
                                    0, TOOLBARCLASSNAME, NULL,
                                    WS_CHILD | TBSTYLE_FLAT,
                                    0, 0, 0, 0,
                                    hwnd, NULL, MainWindow::m_hInstance, NULL);

    HIMAGELIST hImageList1 = ImageList_Create(
            16, 16,                 // 16x16 button size
            ILC_COLOR16 | ILC_MASK, // ILC_MASK ensures transparent background
            numbuttons1, 0); 
    // Set the image list.
    SendMessage(MainWindow::m_hMainToolbar, TB_SETIMAGELIST, (WPARAM)0,

    // Load the button images.
    SendMessage(MainWindow::m_hMainToolbar, TB_LOADIMAGES, 

    TBBUTTON tbButtons1[numbuttons1] = {
            BTNS_AUTOSIZE, {0}, 0, 0},
            BTNS_AUTOSIZE, {0}, 0, 0},
            BTNS_AUTOSIZE, {0}, 0, 0},
            TBSTYLE_SEP, {0}, 0, 0}

    // Add buttons
    SendMessage(MainWindow::m_hMainToolbar, TB_BUTTONSTRUCTSIZE, (WPARAM)sizeof(TBBUTTON), 0);
    SendMessage(MainWindow::m_hMainToolbar, TB_ADDBUTTONS, (WPARAM)numbuttons1, (LPARAM)&tbButtons1);

    // Show toolbar
    SendMessage(MainWindow::m_hMainToolbar, TB_AUTOSIZE, 0, 0);
    ShowWindow(MainWindow::m_hMainToolbar, TRUE);


Next, we’ll take a look at internationalization and how you can write applications that can be easily ported to other languages.

by Pravin Paratey

Facebook puzzle - Find Sophie

Today, we’ll take a look at solving the Facebook engineering puzzle - Find Sophie.

Problem statement

Sophie the Cat

After a long day of coding, you love to head home and relax with a loved one. Since that whole relationship thing hasn’t been working out for you recently, that loved one will have to be your cat, Sophie. Unfortunately you find yourself spending considerable time after you arrive home just trying to find her. Being a perfectionist and unable to let anything suboptimal be a part of your daily life, you decide to devise the most efficient possible method for finding Sophie.

Luckily for you, Sophie is a creature of habit. You know where all of her hiding places are, as well as the probability of her hiding in each one. You also know how long it takes you to walk from hiding place to hiding place. Write a program to determine the minimum expected time it will take to find Sophie in your apartment. It is sufficient to simply visit a location to check if Sophie is hiding there; no time must be spent looking for her at a location. Sophie is hiding when you enter your apartment, and then will not leave that hiding place until you find her. Your program must take the name of an input file as an argument on the command line.

Understanding the problem

This problem can be re-stated as - Given an undirected, weighted and possibly disconnected graph, find the “shortest” tour connecting all vertices which have a probability > 0.

In short, we have to,

  • Enumerate all paths starting from the first position.
  • Compute the Expectation value of each path.
  • Output the minimum. Or -1.00 if we couldn’t cover all vertices.

Lets work this out for the test input,

front_door    .2
in_cabinet    .3
under_bed     .4
behind_blinds .1
front_door under_bed     5
under_bed  behind_blinds 9
front_door behind_blinds 5
front_door in_cabinet    2
in_cabinet behind_blinds 6

We can draw the graph as:

Graph of the example

Our possible paths are:

  • FD -> UB -> BB -> IC
  • FD -> UB -> IC (via FD) -> BB
  • FD -> IC -> UB (via FD) -> BB
  • FD -> IC -> BB -> UC
  • And so on

Expectation value

You may recall from probability theory that for a discrete random variable X with a probability mass function p(x), the expectation value is,

E(X) = Σ xi ⋅ p(xi)

In our problem, we have to find the expectation value (EV) of time taken. For the path, FD -> UB -> BB -> IC, the EV will be (note how the time is additive):

E(P1) = 0.2(0) + 0.4(5) + 0.1(5 + 9) + 0.3(5 + 9 + 6) = 9.40

If you compute the EV for every path enumerated, you’ll find that the path with the least expectation value is FD -> IC -> UB (via FD) -> BB [ 0.2(0) + 0.3(2) + 0.4(9) + 0.1(18) ]

Finding tours

Now that you know how to compute the EV of a path, the next challenge is figuring out how to find a path. We call this path a “tour” to indicate our intention to visit every node.

If you’ve studied Computer Science, you might think - _”Travelling Salesman!“_. Umm … we don’t have the constraint of visiting each location exactly once. Which is a good thing or it’d be NP-complete.

We’re going to do this in two stages. In the first stage, we will solve the shortest path problem for all pairs of vertices. We can use either Dijkstra’s algorithm, Floyd-Warshall algorithm or Johnson’s algorithm (which is faster than Floyd-Warshall in certain cases).

The shortest path algorithms described above tell you the shortest-path between two nodes. The next stage is enumerating all possible tours. This has a possible time complexity between O(nn) and O(n!) depending on your implementation.

At this point, you’re ready to compute the EV of every tour and output the minimum.


Of course, that’s slow. And it wouldn’t pass the Facebook PuzzleBot. So what do you do? How do you make it faster? I’m not sure about faster, but we can definitely make it our algorithm smarter.

The O(n!) is the culprit. Do you really need to enumerate all possibilities? Or can you discard the unviable paths? How do you know a branch is unviable?

The first thing you can do is store the minimum EV (until now) and discard all paths that exceed this value. Consider the following figure. Assume the EV of the first path [FD -> UB -> BB -> IC] was 100. If the EV of [FD -> IC] is > 100, we can drop the entire branch (colored Red).

Dropping branches based on score

If you add this to your code and run it, you’ll realize that you don’t end up dropping as many branches as you’d like. Can we do better?

Well, Yes. What if you used a heuristic like that in A* algorithm to compute the EV of the remaining path? Since we are looking for an exact solution and not an approximate one, our heuristic h(x) should be chosen carefully. h(x) should always be <= the min(E(Pathi)). One possible h(x) can be:

h(x) = min(Path_length) * (Remaining Probability)


This is enough to get past the PuzzleBot. I leave you with a final question: Can you do better? Perhaps at the cost of memory? I look forward to your comments


February 05, 2011
Since many of you have asked me how much time my code took to run the examples, I’ve updated results.txt with the time. Oh, and my machine has a 2.4GHz dual core processor.


Test cases
Introduction to Algorithms
Computational Problems in Graph Theory: Travelling Salesman Problem, Shortest Path Problem, Hamiltonian Path Problem, Hamiltonian Path
Algorithmic Graph Theory
On a routing problem (Richard Bellman)
by Pravin Paratey
by Pravin Paratey

Palindromic sub-sequences in python

This bit of code returns all palindromic subsequences in the input string. If the line marked #In-efficient is better implemented (I am lazy), the running time is O(n<sup>2</sup>). Can you find a better solution?

<?prettify linenums=true?>

#!/usr/bin/env python

def get_palindromes(str):
    """ Return all palindromes in str of minimum size 3 """
    length = len(str) + 1
    found = []
    for i in xrange(0, length):
        for j in xrange(i+3, length):
            mid = i + ((j - i) / 2)
            if str[i:mid] == str[mid+1:j][::-1]: # In-efficient
    return found    

if __name__ == '__main__':
    print get_palindromes('efeababaf')
by Pravin Paratey

Writing a spider in 10 mins using Scrapy

I came across Scrapy a few days back and have grown to really love it. This tutorial will illustrate how you can write a simple spider using Scrapy to scrape data off Paul Smith. All this in 10 minutes.

This tutorial is available on [github]( Please refer to it for code updates to accomodate periodic changes to the Paul Smith website.

Lets begin

  1. Download and install scrapy and its dependencies.
  2. This done, open up your terminal and type python startproject paul_smith. A scrapy project will be created.
  3. Navigate to ~/paul_smith/paul_smith/spiders and create the file with the following contents:

    from scrapy.spider import BaseSpider

    class PaulSmithSpider(BaseSpider): domain_name = “” start_urls = [“"]

    def parse(self, response): open(‘paulsmith.html’, ‘wb’).write(response.body)

    SPIDER = PaulSmithSpider()

  4. To run the spider, go to ~/paul_smith type python crawl on the command line. This will fetch the page and save it to paulsmith.html.
  5. The next step is to parse the contents of the page. Open the page in your favourite editor and try to understand the pattern of the items we want to capture. You can see that &lt;div class="product-group-1"&gt; contains the required information. We are going to modify out code like so:

    from scrapy.spider import BaseSpider
    from scrapy.selector import HtmlXPathSelector

    class PaulSmithSpider(BaseSpider): domain_name = “” start_urls = [“"]

    def parse(self, response): hxs = HtmlXPathSelector(response) sites =‘//div[@class=“product-group-1”]‘) for site in sites: print site.extract()

    SPIDER = PaulSmithSpider()

    You can read more on XPath Selectors here.

  6. Finally, looking at the HTML again, we can extract title, link, img-src & sale-price like so:

    from scrapy.spider import BaseSpider
    from scrapy.selector import HtmlXPathSelector
    import random

    class PaulSmithSpider(BaseSpider): domain_name = “” start_urls = [“"]

    def parse(self, response): hxs = HtmlXPathSelector(response) sites =‘//div[@class=“product-group-1”]‘) random.shuffle(sites) for site in sites: title =‘h3[@class=“desc”]/text()‘).extract() hlink =‘a/@href’).extract() price =‘p[@class=“price price-GBP”]/text()‘).extract() image =‘a/img/@src’).extract()

      print title, hlink, image, price

    SPIDER = PaulSmithSpider()

    You can save this data to your datastore in whatever way you wish.

  7. The output of 3 random items scraped using the above code can be seen below.


Source code

- View on Github

by Pravin Paratey

Script to generate URS from Wikipedia

A persons’ URS is a phrase that could be used instead of his/her usual name in all circumstances, which makes it absolutely clear who he/she is. A good URS for a person should meet the following criteria:

  • Everyone familiar with the person will confidently recognise him/her from the URS.
  • There is no possibility that the URS could also describe anyone other than the person.
  • Even someone who isn’t familiar with the person will have some understanding of who he/she is from the URS.
Script to generate URS from the starting paragraph of Wikipedia 
articles about persons.

by Pravin Paratey (pravinp -at-

Current Implementation:
1. Extract first sentence
2. Clean wiki markup
3. Observing given data, and the data on wikipedia, shows that there 
   is a pattern that is followed while writing wikipedia entries for
   persons. Replacing (was/is)(an/a/the/) with (/the) does the trick
4. Output sentence formed

Ideally, the piece of code should identify the following concepts:
1. Name of person
2. Time period
3. Son/Daughter/Father/Mother of (in case of famous personality)
4. Renowned for

How do we go about it?
1 and 2 - straight forward. Wikipedia gives cues through its markup
3 - straight forward. String matching using "son of", "daughter of", etc
4 - will need to match against a database.

For 3, we only keep the "son of", "daughter of", "X of Y" if Y is a prominent
person. An easy way of doing this is using incoming links on wikipedia OR
to search for X and Y individually on google and noting the number of results.

import re, sys, codecs

def cleanUri(m):
    """ Cleans Uri wiki markup """
    word =
    if '|' in word: word = word.split('|')[1]
    return word.strip()

def dotRemove(m):
    """ Replaces . by # inside tags """
    return'.', '#')

def cleanMarkup(text):
    """ Removes
    1. wiki markup
    2. sanitize html entities 
    #text = re.sub(r"\[\[[\w\s\-,]+\|(\w+)\]\]", r"\1", text)
    text = re.sub(r"\[\[(.*?)\]\]", cleanUri, text)
    text = re.sub(r"\{\{.*?\}\}", r"", text)
    text = re.sub(r".*?<\/ref>", r"", text)
    text = re.sub(r"---.*?---", r"", text)
    text = re.sub(r"\[.*?\]", r"", text)
    text = text.replace("'''", "").replace("''", "'")
    text = text.replace("[[", "").replace("]]", "")
    text = text.replace("–", "-").replace("&", "&")
    return text

def getFirstSentence(text):
    """ Returns the text until first instance of '.'
    It also makes sure that the '.' isn't part of a wiki link
    or name"""
    tmp = re.sub(r"\[\[.*?\]\]", dotRemove, text)
    tmp = re.sub(r"\[.*?\]", dotRemove, tmp)
    tmp = re.sub(r".*?<\/ref>", dotRemove, tmp)
    tmp = re.sub(r"---.*?---", dotRemove, tmp)
    tmp = re.sub(r"'''.*?'''", dotRemove, tmp)
    tmp = re.sub(r"''.*?''", dotRemove, tmp)
    index = tmp.find('.')
    if index == -1: 
        return text
        return text[:index]

def makeArticle(m):
    """ Changes a, an to the when appropriate """
    retval = ', the'
    if len( == 0:
        retval = ' '
    return retval
def extractURS(text):
    """ The function to call. Returns the URS """
    text = getFirstSentence(text)
    text = cleanMarkup(text)
    text = re.sub(r",?\s+(was|is)\s+(an|the|a|)", makeArticle, text)
    return text

if __name__ == '__main__':
    #fp = open(sys.argv[1])
    fp ="input.txt", "r", "utf-8")
    fp2 ="output.txt", "w", "utf-8")
    fp2.write(codecs.BOM_UTF8.decode("utf-8")), # Add BOM for UTF-8
    for line in fp:
        line = line.rstrip()
        if len(line) == 0 or line.startswith("#"): # For debugging
        urs = extractURS(line)
        fp2.write(urs + '\r\n')

Example Inputs and Outputs

These are inputs from Wikipedia (Click on the article and then Edit). Ex Lala Lajpat Rai. The above script outputs the URS.

Example Input: ”‘B. S. Johnson “’ (Bryan Stanley Johnson) ([[5 February]],[[1933]] - [[13 November]],[[1973]]) was an English experimental novelist, poet, literary critic and film-maker. Script Output: B. S. Johnson (Bryan Stanley Johnson) (5 February,1933 - 13 November,1973), the English experimental novelist, poet, literary critic and film-maker

How are URS used?

URS can be directly substituted in a sentence containing that persons’ name. (Hover over Bhagat Singh to see this URS. ex. Bhagat Singh was executed by the British in 1931. This way, a person who had no idea who Bhagat Singh was, now has more context about the person.

by Pravin Paratey
by Pravin Paratey

XML DOM in Java

Of late, I have been working with Java. And one of the issues that I faced was XML parsing. With so many libraries available, I decided to stick to jaxp. What follows is sample code to Tree walk over the nodes:


import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

public class Tester {
    public static void main(String args[]) 
        DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();

        try {
            DocumentBuilder builder = factory.newDocumentBuilder();
            org.w3c.dom.Document doc = builder.parse(new File(args[0]));
            NodeList nodes1 = doc.getChildNodes();
            for(int i=0; i<nodes1.getLength(); i++) {
                TreeWalk(nodes1.item(i), 0);
        catch(Exception e) {
    private static void TreeWalk(Node n, int level) 
        if(n.getNodeType() != Node.TEXT_NODE) {
            for(int i=0; i<level; i++)
                System.out.print("  ");
            System.out.print(n.getNodeName() + ":");
        else {
        NodeList list = n.getChildNodes();
        for(int i=0; i<list.getLength(); i++) {
            TreeWalk(list.item(i), level+1);

{: class=“prettyprint linenums:1”}

by Pravin Paratey

Hacking wp-syntax plugin to show header

I was recently asked how I got the wp-syntax plugin to show a header like so:

int main() {
    return 0;

To show the test.cpp file name, I modified the wp-syntax.php file (present in /wp-content/plugins/wp-syntax/) like so:

Changed the regular expression in the wp_syntax_before_filter function from:

function wp_syntax_before_filter($content)
    return preg_replace_callback(


function wp_syntax_before_filter($content)
    return preg_replace_callback(
        "/\s*<pre(?:lang=[\"']([\w-]*)[\"']|line=[\"'](\d*)[\"']|escaped=[\"'](true|false)?[\"']|header=[\"']([\w-\. ]*)[\"']|\s)+>(.*)<\/pre>\s*/siU",

{: class=“prettyprint linenums:1”}

And the wp_syntax_highlight function to:

function wp_syntax_highlight($match)
    global $wp_syntax_matches;

    $i = intval($match[1]);
    $match = $wp_syntax_matches[$i];

    $language = strtolower(trim($match[1]));
    $line = trim($match[2]);
    $escaped = trim($match[3]);
    $header = trim($match[4]);
    $code = wp_syntax_code_trim($match[5]);
    if ($escaped == "true") $code = htmlspecialchars_decode($code);

    $geshi = new GeSHi($code, $language);
    do_action_ref_array('wp_syntax_init_geshi', array(&$geshi));

    $output = "\n<div class=\"wp_syntax\">";

    if($header) {
        $output .= "<div class=\"wp_syn_hdr\">" . $header . "</div>";

{: class=“prettyprint linenums:94”}

Note the addition of lines 104 and 114-116.

All you have to do is add another attribute header="header-text" in your pre tag. ex. &lt;pre lang="php" line="1" header="wp-syntax.php"&gt;

by Pravin Paratey

Exporting Opera email to mbox format

The following snippet combines the various opera mbs into one mbox format which can be used by other email clients like Evolution to import mail.

# Quick hack to merge all opera mbs files into mbox format which can
# then be used by other email clients to import Opera email.
# by Pravin Paratey (January 19, 2009)

import os

# Change this value
folder = '/home/pravin/.opera/mail/store/account1/'

fp = open('combined.mbox', 'a')

for d0 in os.listdir(folder):
    p0 = os.path.join(folder,d0)
    if os.path.isfile(p0): continue
    for d1 in os.listdir(p0):
        p1 = os.path.join(p0, d1)
        for d2 in os.listdir(p1):
            p2 = os.path.join(p1, d2)
            for f in os.listdir(p2):
                fp2 = open(os.path.join(p2, f), 'r')