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!!!