Solution to Fog Creek's developer puzzle

fog-creek.py

'''
http://www.fogcreek.com/jobs/dev

Find a 9 letter string of characters that contains only letters from: acdegilmnoprstuw

such that the hash(the_string) is: 945924806726376

if hash is defined by the following pseudo-code:

Int64 hash (String s) {
    Int64 h = 7
    String letters = "acdegilmnoprstuw"
    for(Int32 i = 0; i < s.length; i++) {
        h = (h * 37 + letters.indexOf(s[i]))
    }
    return h
}

For example, if we were trying to find the 7 letter string where hash(the_string) was 680131659347, the answer would be "leepadg".
'''

LETTERS = "acdegilmnoprstuw"

def hash(s):
    h = 7
    for i in range(len(s)):
        h = h * 37 + LETTERS.index(s[i])
    return h

def unhash(h, length):
    h -= 7 * 37 ** length
    return _unhash(h, "", length)

def _unhash(h, s, length):
    if h == 0 and len(s) == length:
        return s
    elif h < 0 or len(s) == length:
        return False

    for i in reversed(range(len(LETTERS))):
        new_h = h - (i * (37 ** (length - len(s) - 1)))
        result = _unhash(new_h, s+LETTERS[i], length)
        if result: return result

hash = 680131659347
print(str(hash) + " >> " + unhash(hash, 7))

hash = 945924806726376
print(str(hash) + " >> " + unhash(hash, 9))