Gray Code Generator

I suppose I could finally talk about it!  I had my Google interview last July.  Was an embarassement (and to myself too).  This was the final question in my interview (with none other than Lars Rassmussen).  The question was the typical one – “there is a room from which at any time only one person can either enter or exit the room – and not at the same time.  So how would you model all the states the room can be in without repetitions”.

“Simple, isnt that just Graycode?” I blurt out.  At which point I was asked to write an algorithm to actually generate all graycodes for a n-bit string.   And this was where I floundered.  Mind you I had just been through 3 and a half hours and writing an algorithm was the last thing on my mind.  It wasnt that I hadnt known how to do it, I just blanked out then then and there – half an hour close to the finish of the interview and I had lost focus.  Stupid stupid me.

Anyway I just got back from a swim and for some reason the demon of the failed interview reared its ugly head and so I figured Id attempt it here (atleast to get some closure, sob sob).  Here goes.

Here are possible gray codes for N = 1, 2, 3 and 4:

N = 1	N = 2	N = 3	N = 4
0	00	000	0000
1	01	001	0001
	11	011	0011
	10	010	0010
		110	0110
		111	0111
		101	0101
		100	0100
			1100
			1101
			1111
			1110
			1010
			1011
			1001
			1000

Anyway this is only one combination. Any bit could be changed in generating the sequence. The pattern here is that the first half and the second half of the code are “kind of” the same but with the first bit being 0 and 1 respectively and the rest of the bits being reverse of each other.

ie with N = 2,
first half = 00 and 01
second half = 11 and 10

So a simple algorithm would be (in pseudo-haskell):

gc 1, reverse = ["1", "0"] if reverse, else ["0", "1"]
gc N, True =
      ["1" + x for x in gc(N - 1, True) ] ++ ["0" + x for x in gc(N - 1, False) ]
gc N, False =
      ["0" + x for x in gc(N - 1, False) ] ++ ["1" + x for x in gc(N - 1, True) ]

Problem with the above is the storage required in the recursion to store the graycodes for N – 1 (and that too twice). So in python we could avoid this with generators like:

def graycode(numbits, reverse = False):
    if numbits = 1:
        if reverse:
            yield "1"
            yield "0"
        else:
            yield "0"
            yield "1"
    else:
        if reverse:
            # all the "1"s start first
            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code
        else:
            # all the "0" start first
            gcprev = graycode(numbits - 1, False)
            for code in gcprev:
                yield "0" + code

            gcprev = graycode(numbits - 1, True)
            for code in gcprev:
                yield "1" + code

and finally an auxilliary function to print out the codes:

def gcgen(numbits, reverse = False):
    for codes in graycode(numbits, reverse):
        print "Code: ", codes

And that was 15 minutes of thinking. Damn it why didnt it come to me last year? Could have been the difference between a googler and foogler!!! Unless ofcourse it didnt really matter and they simply thought I was just a dick@#$D!!!

API Centric Design with Django and GAE

I wasnt really sure what to call this post.  My current situation is I write django apps (well so many words within that sentence can be loosely defined).  I guess after playing with django for last two and a half years (and Google AppEngine, GAE, ever since it came out) I am at a very interesting (or frustrating) crossroad.  What platform to choose and stick with – appengine or django.  Actually I had this conundrum about a year ago and I have essentially postponed this choice by what I call API centric design (ACD).  I am pretty sure ACD is just another fancy acronymn for existing techniques out there but still bear with me.

Django can be quiet easily used with GAE.  And infact that is what I have done.  I use django entirely within GAE.  The real impedence mismatch pops its ugly head thanks to the completely different backend schemes used by GAE and Django (key-value store vs relational DB).  As much as I am not a fan of the GAE, it is a pretty good platform for prototyping.  Well its free and hence, given the state of the competition, the best choice (for now) in the price range.   So how does one use GAE for prototyping an application, leaving it out there to collect feedback (and failing early and failing often) and move the application a platform of choice when the limits are reached and the constraints in GAE are just too much?  A redesign of an app to leverage non-GAE environments is certainly not the way to go.

What I have done is only expose an API from the app point of view.  Hide the back-end specific details behinds its own models.py (django uses models.py to hold the data models for an applications).  Its actually a lot easier than it sounds (if it already sounds easy, then it is even easier).  What is trickier is that one would have to exercise considerable discipline in following this.  Every call in the application should call only the exposed api instead of using the data-backend related calls provided by the platforms (GAE or Django or anything else).  Even leave the implementation and the optimisation to the specific backends.

As an example, let us take the famous “counter” example.  A typical way to have counters in traditional RDBMs based platforms is to have a table that stores the rows of name/counter pairs.  For DBMSes that are strong with write’s this is great.  GAE however recommends a different approach using shards.  Check Brett Slatkin’s video on this.  So how do you choose between these two?

Firstly settings.py needs to have a variable called USING_APPENGINE (or something similar) that will be set to True if the app is running in GAE and False otherwise (ie a native django app running on the test server or on other webservers).

Suppose our counters api is as follows:

def get_counter(counter_name)

def incr_counter(counter_name, byhowmuch = 1)

Now il need 3 files for the api – counters.py, djcounters.py and gaecounters.py.  Only counters.py will be imported in any other part of the application requireing counters.  djcounters.py will have the get and incr counter implementations for traditional RDBMBs and gaecounters.py will have the same for a GAE specific implementation.

counters.py will be:

from django.conf import settings

if settings.USING_APPENGINE:

from gaecounters.py import *

else:

from djcounters.py import *

Thats it.  In your calling app simply do:

import counters

counters.get_counter(“xxx”)

counters.incr_counter(“xxx”, 10)

This is only the beginning.  Clearly this extends to other types of backends as well (ie support TokyoCabinet in the future etc).  When writing an application you shouldnt have to worry about the optimisations.  Nothing stipulates that gaecounters.py will have to implement Brett Slatkin’s stragey when using counters in GAE, but having separate files allows for this optimisation in the future.  Let the api abstract it all away.

Ofcourse it may appear that this will explode the number of functions required in the API.  Not necessarily (ie functions having to bepeated to do filters or object creations or deletions).  Some of the common patterns are object creation, fetching an object by ID or by certain attrib/column values, deleting records.  There are others, but these are the most common ones.

So I have a base djhelpers and gaehelpers file which define object creations, deletions, searches for ANY kind of object class and each one is optimised (sort of) to that specific implementation.

For instance, in django objects can be created with the method:

def create_object(obj_class, **kwds):

    return obj_class.objects.create(**kwds)

while the GAE implementation would be:

def create_object(obj_class, **kwds):

    obj = obj_class(**kwds)

    db.put(obj)

    return obj

Note these are only basic ones.  Other implementations could go through the kwds list and get the parent and id parameters to set these on the object as required.  Alternatively, you could only save optionally and so on.

So an object creation in another part of the app is simply a matter of doing:

create_object(MyObjectClass, a = 1, b = 2, c = 3)

and the object is created without having to worry about the backend type.

This is again a simple way of hiding the implementation details.  The same could be implemented using metaclasses and properties to define a DBObject class whose metaclass would be the implementation specific class for the above and other object specific methods.

Sydney Django Users Group

Well we already do have a Sydney Python group.  So I was a bit apprehensive when I created the Sydney Django Users Group.  But my goal was not to compete with SyPy (actually most of our members are FROM SyPy and we regularly visit SyPy discussions – including one last night by Alex Dong on scaling web applications).

The main goal was to have a small group focusing purely on django activity in sydney.  So far so good.  Had our first meetup last tuesday.  Modest turn out and interesting talk by Sam Cavenagh and Shaon Diwakar.  Oh and thanks heaps for Shaon and Sam for actually pushing me to organise the meetup by getting me out of my lazy zone.

And here’s for lots more activity in the sydney django community.

StartupCampSydney II

Wow that was a doozer!

Last weekend was the StartupCampSydney.  A weekend where about 6-10 teams (each with 6-8 members) build, launch and pitch a Startup in one weekend.  Yep one weekend. To be honest I never thought it would work and when asked to be part of this one, I was trying to come up with an excuse to back out of it (before my wife who I hoped would have asked me not to go, urged me to participate…) …  the urging turned out to be a blessing.. that was one of the most intense, enriching, immersed and enlightening product development excercises Ive been in.

The sheer amount of talent from all backgrounds says it all.. and ofcourse meeting and working with so much talent just makes you do things that you never realised were possible.  Our startup is ThreeFeeds.com – a topic/news aggregator. Check it out, we would love your feedback (please forgive us in advance for the bugs).

Check out a full coverage of SCS by Ross Dawson.

Cant wait for the next one.

LunarProbe

At work I do games.   Again not the usual kind but the slot ones.  A good thing about where I work unlike others in the industry is that we actually have a bit of belief in technology and try to “catchup” with latest technology (usually mainstream – 5 years).  Now while this may be astonishing to some outside the industry, it is quite advanced within!  Anyhoo I am digressing.

Point was that with all this catching up we do, we recently (about 6months-1year ago) started using Lua to script a big chunk of the games so that only the core is handled by C++ and everything UI related is palmed off to Lua.  Obvious advantage is that extra builds are not required as compileable source code is not changed and configuration is a lot easier and lot less time consuming.  Again nothing new here.

The problem is that the lua scripts we invoke from C++ have no easy way of debugging them.  So our engineers had been toiling with this by using the first-class technique of peppering the code with print statements.  You would thing some methodologies would die eventually but nope.

So I figured why not simply have a debugger that takes advantage of Lua’s debug api and allow debugging of scripts remotely.  So was born LunarProbe.  My attemt at debugging lua scripts once embedded in a host language.  Even at the beginning I figured that this was a very generic thing and has no specific code for our games.  So I decided to release it on the Apache License.  You can find the code on google code.

So far it only supports C/C++ but hope to have more languages supported with the appropriate bindings in place.  The idea is simple:

1. The lua_State object (ie the lua stack or the lua context) is god in Lua.  Essentially it is what the interpreter uses to execute scripts and lua statements “on”.
2. A new lua stack can be opened with the lua_open command.
3. Usually following this command, you open all the standard libraries with the luaL_openlibs.

That is it.  You do usual things like loading lua files on a particular stack.  See the lua manual for more info on this.

So where does the debugging come in?  Well each lua stack can be given a debug hook function that is called by the interpreter after certain points at runtime. eg after a line has been executed, after a function is invoked, after a function has returned etc.

What LunarProbe does is registers itself as a hook function and deals with each of the above debug events and presents it via tcp (port 9999 by default) to a remote client.  The debug server is in fact api driven.  It accepts commands from the client and returns responses (but not HTTP – to keep it simple).  This means any UI could be written easily by simply following the debug server protocol.  A reference client is provided (written in python).  The python client is supposed to be like gdb (but no where near it!! GDB – please accept my apologies for even trying a comparison!!  I know I dont deserve it.)

I wanted to write a GUI or an Eclipse plugin, but we dont use eclipse plugin at work and wx widget toolkits werent installed by default here at work.  So doing either meant having all developers install extra packages which was a huge adminstrative overhead.  At a later stage, I would like to see more coming up.  Any helpers?

Again I digress.  So how would one enable LunarProbe in stacks they are opening?  Simple.

Instead of lua_open and luaL_openlibs, simply do this:

1. Include the lunarprobe header (ensure that lunarprobe/src is in the include path):

• #include “lpmain.h”

2. Instead of lua_open and luaL_openlibs simply do:

LUNARPROBE_NS::LuaUtils::NewLuaStack(true, true, “hello”)

This does a few things:

1. Creates a lua stack using lua_open
2. If the first parameter is true, then Opens standard libraries using luaL_openlibs.
3. and if the second parameter is true, registers LunarProbe by calling LUNARPROBE_NS::LunarProbe::Attach(stack, name), where “stack” was opened in step 1.
4. The fourth parameter (defaulting to “”) only gives a name to each of your stacks for debugging purposes.  This is very useful in the debug client to identify which stack your dealing with when the address of a stack may not be very useful or very clear.

Alternatively, you can simply call the step 3 instead of NewLuaStack if you do not want to pull out your own versions of lua_open and luaL_openlibs.

That it. This is the embedding/attaching part of the debugger.  Now the client.

The Client

lunarprobe/client includes a simple client – client.py.

I wont go into too much detail here as the “help” command is mostly self-explanatory.  Just the brief stuff.

Invoke this with:

• python client run

or if you would like to run it from within an interpreter then:

• import client
• client.run()

This brings up the LDB prompt: type in “help” to show all commands and their usage.

One distinction (actually an inconvinience) is that since multiple stacks can be debugged at the same time, any context (LP calls stacks as contexts) specific commands must pass in the address of the context.  This is not hard, just inconvinient.

To get a list of all the contexts simply type in the contexts at the prompt and press enter.  This will show all context names and their addresses.  Use these addresses with any context related commands (like step, next, continue etc).

Breakpoints at the moment can be set by filename (and linenumber) or by a function name.  However at this stage member functions are not differentiated from global functions.  So a function name breakpoint will affect ALL functions of the same name.

As mentioned this is very brief.  Apologies for that.  Il add more and more in as I improve this.

Well hopefully this project is useful for all Lua embedders out there.  Please let me know how I can improve this.  Also this project is on google code, so please let me know if you would like to contribute or extend LP.

Best of luck!!!

The Greatest Entrepreneurs

The 80s and 90s, saw a huge influx of Indian migrants to Australia (the trend still continues).  Now there is something different about these migrants.  Now what is odd about this class of migrants is most of them were in their mid 30s to mid 40s, with very comfortable lifestyles back home (by which I mean respectable jobs/positions resulting from years of hard work).  Why I think this is odd is that you would not expect people/couples with such low risk lifestyles to risk it all and jump ship to sail to the uncertain shores of a foreign land.

It is pretty easy (or comforting atleast) sitting in your parents’ basement coding or being sponsored to spend summers on startup ideas sponsored by THE man PG himself (an opportunity Id kill for), but leaving all you have with very little promise of great rewards, purely for the sake of your family, is what I consider true entrepreneurship (well children are the ultimate startups anyway).  Costs of failures are very high (hardship for entire family, loosing face, etc).  Rewards are not staggering except that life for one’s family is slightly better.

I would like to thank two such migrants who risked very comfortable jobs for the sake of their two sons.  Myself and my brother.  Mum was a very respected high-school teacher (she was my math teacher – which could explain my interest in maths).  Dad was a successful accountant.  Like others they had left it all for us.  The main reason was reverse-discrimination in the society gripped by the plague of the caste system, existing only to empower already corrupt politicians (redundant adjective). Times were hard for the first two years – time they had spent unemployed, living on government assistance.  But I am glad for those times.  It had instilled in us a passion and respect for hardwork.  Cant complain at all.  No room for becoming spoilt brats.  In fact I wonder if I can ever replicate their own dedication and values on my own kids (one day).  Atleast I know that I dont have to look far in search of role-models!

So thanks mum and dad (hope this combined post suffices for mothers’ and fathers’ days).

Google Captcha got my tongue!!

AAAAAAAAAAAAAAAAAAAAAARRRRRRRRGGHHHHH

Hate captcha in the google maps.  I can understand how it needs to protect itself against spam, but this is ludicrous.  I was playing with the google maps api writing a simple google maps mashup.  This meant editing my js file and reloading the pages a few times.  Somehow google flagged this as a sequence of spam requests.  So it shows me the dreaded captcha page.  I enter the damn captcha.  You would think a company like google would be smart enough to let you get on with your work.  Oh no, it brings up the captcha page again.  May be I got the captcha wrong originally so I tried again, no luck.  Now onto my 100th try in a row and still no luck.  Google still thinks my requests (from a FF3 browser) are all spam requests.

Is this the sign that gOoGle is finally going the MS way?

Happy 3rd of January

Happy new year and a happy 3rd of January to all.  No, nothing significant about that date except that it happens to be the date of my first blog (hopefully of hundreds, cough cough) this  year.

Been a great vacation.  Drove down to Melbourne to visit the parents.  Boy that was relaxing and tiring at the same time.  Cant believe time just dissapeared before I knew it!

Any hoo a happy 2008 to all.  Hope 2007 was a great year for all of you and hope 2008 is much better!

/* No Comment */

I think the new title certainly reflects what I usually have to say about things and how often I say it.  So figured why not.  On a “deeper” level (not much more though),  this was our team name back in uni when we had participated in the ACM programming competitions.  Jees, I think I did everything to avoid actually going to classes.  Good times, those were.  The intense atmosphere in the comps..  ah dont think Id be doing justice describing it.  Those were the days.  And plus, did I mention the free food?

Any body interested in discussing some of the ACM problems?

Back On

Well after a long long gap. Here I am back on. Had a few things going on. Had my exams going, bought a house, tried out OmniDrive and made a mountable drive for OmniDrive. Will post more about it soon.