promenade.py

#!/usr/bin/python


def hash(s, key="acdegilmnoprstuw", seed=7, multiplier=37):
    '''hashes string and return int

    pseudocode:

        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
        }

    '''
    hash = seed
    for c in s:
        try:
            hash = hash * multiplier + key.index(c)
        except ValueError:
            print(("Character '{}'' is invalid. "
                   "Only '{}' characters allowed!").format(c, key))
            raise
    return hash


def unhash(h, l, key="acdegilmnoprstuw", seed=7, multiplier=37):
    '''
        h: int hash
        l: int length of original string
        key: string based on which the character index is calculated
        seed: int defaults 7
        multiplier: int

        The hash calculate is the form of:

            H = (((... ((7 * m + c1)*m + c2)*m + c3)*m ...)))*m + c9)

            -> c1...c9 is index of first character,
               nineth character of string s, in string key
            -> m is the multiplier
            -> 7 is the seed

        Therefore,

            H = 7*m^9 + c1*m^8 + c2*m^7 + .... c8*m^1 + c9*m^0
        or,

            H - (7 * m^9) = c1*m^8 + c2*m^7 + .... c8*m^1 + c9
                            ^---------------------------^   ^
                                    `part 1                  `part 2

            -> part 1 is multiple of m
            -> part 2 is not multiple, as c9 < m

        So,
            c9 = (H - (7 * m^9)) % m
            should give us c9 (the last character)...
        and
            c8 = ((H - (7 * m^9) - c9) / m ) % m
        and
            c7 = (((H - (7 * m^9) - c9 - c8*m / m*m) % m
        so on ....
    '''

    hash_constant = h - (seed * (multiplier**l))
    last_char_index = 0
    answer = ''
    for i in range(l):
        hash_constant -= (last_char_index * (multiplier**i))
        char_index = (hash_constant / multiplier**i) % multiplier
        answer += key[char_index]

    return ''.join(reversed(answer))


def test_hash():
    # 680131659347, the answer would be "leepadg".
    assert hash('leepadg') == 680131659347


def test_unhash():
    # 680131659347, the answer would be "leepadg".
    assert unhash(680131659347, len('leepadg')) == 'leepadg'

if __name__ == '__main__':
    print(unhash(945924806726376, 9))