Interesting puzzles - 5

Here's one I heard from a junior:

You have a chessboard of side length 2^n. An arbitrary unit square is removed from this board. Is it possible to tile the remaining chessboard with L shaped tiles having 3 unit squares each (as shown in the figure below).

 _
| |_
|___| 

Back ...

So I am back to blogging after a great break to Tiruppur and some busy work with some internal deadlines.

On a work related note, I will be moving to the RFID group here.

If you like python and puzzles you must have a look at python challenge. Naturally they are python centric (python module names in hints and the like..). Download the python imaging library before you start :). I am at level 16 now and can give additional hints if necessary ;)

Search history...

Started using Search History. Wonder how I got along without it till now!

Speaking of google they does use their adsense well. Try searching for Udi Manber and see the ads :)

Interesting...
"Just as the U.S. wants to see a strong and democratic Russia, we want to see a strong and democratic U.S. that acts in the international arena jointly with other states and with respect for international law,"

Random stuff

Too many are moving out of msft these days. minimsft documents a few of them ...

Noticed something very interesting - most of the Microsoft DEs worked at DEC sometime in their careers!

ACV has written a lot of cool humour stuff on his site

Anagrams ....

You have dictionary words in a file. You are solving crosswords. You want to quickly find anagrams of a given word.
Perf requirements:
1. Load up time of a couple of seconds is acceptable (wordlist of ~50k which you can get from web)
2. Each anagram query should be fast say < 0.5 or 1 sec.

Here's how building the strucure would look in python. Reads like psuedo code but it works.. Pretty neat?

def sort(word):
    l = list(word)
    l.sort()
    return "".join(l)

def anagrams(words):
    ags = {}
    for word in words:
        sw = sort(word)
        ags.setdefault(sw, []).append(word)

    return dict([(x,y) for (x,y) in ags.iteritems() if len(y) > 1])

if __name__ == "__main__":
    words = open("wordlist.txt").readlines()
    words = [word.strip() for word in words]
    rs = anagrams(words)
    print len(rs)

If you think about it your first reaction would be - but it would be **so** slow :)). But you know what? It satisfies the requirements and takes a fraction of time to write than in C.