Find a 9 letter string of characters that contains only letters from “acdegilmnoprstuw” such that the hash(the_string) is “910897038977002”.

exercise.md

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

acdegilmnoprstuw

such that the hash(the_string) is

910897038977002

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".

trello.py

# -*- coding: utf-8 -*-

#
# Join the Trello team as a…
# Developer
#
# https://trello.com/jobs/developer
#
# Check strings:
# $ python trello.py
#
# Run unit-tests:
# $ python -m doctest trello.py
# (no output means tests passed)
#


LETTERS = 'acdegilmnoprstuw'
FIRST_LETTER = LETTERS[0]


def compute_hash(string):
    """
    Compute hash for the given string.

    Pseudo-code provided by Trello™:

        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
        }

    Unit-tests:
    >>> compute_hash('leepadg')            # example given by Trello™
    680131659347
    >>> compute_hash('asparagus')          # value to find
    910897038977002
    """

    h = 7
    for char in string:
        h = h * 37 + LETTERS.index(char)
    return h


def compute_string(hash):
    """
    Compute string from hash

    Unit-tests:
    >>> compute_string(680131659347)       # example given by Trello™
    'leepadg'
    >>> compute_string(910897038977002)    # value to find
    'asparagus'
    >>> compute_string('910897038977002')  # hash is cast to int anyway
    'asparagus'
    >>> compute_string(-42)                # unable to compute negative hash
    Traceback (most recent call last):
      ...
    ValueError: Cannot find string for hash -42
    >>> compute_string('')                 # unable to compute empty string as hash
    Traceback (most recent call last):
      ...
    ValueError: invalid literal for int() with base 10: ''
    """

    hash = int(hash)

    # Quick find string length:
    hash_length = len(str(hash))
    string_length = 0
    while True:
        current_string = FIRST_LETTER * (string_length + 1)
        current_hash = compute_hash(current_string)
        if len(str(current_hash)) > hash_length:
            break
        string_length += 1

    chars = []
    for i in range(string_length):
        previous_char = None
        for char in LETTERS:
            current_string = ''.join(chars) + char + FIRST_LETTER * (string_length - i - 1)
            current_hash = compute_hash(current_string)
            if current_hash == hash:
                # String found!
                return current_string
            elif current_hash > hash:
                # Add previous character to chars[]
                chars.append(previous_char or FIRST_LETTER)
                break
            else:
                # Update previous character
                previous_char = char
    # Unable to find the string
    raise ValueError('Cannot find string for hash {hash:d}'.format(hash=hash))

if __name__ == '__main__':
    for hash in (680131659347, 910897038977002):
        print(compute_string(hash))