Skip to content

Instantly share code, notes, and snippets.

@wo0dyn
Created July 26, 2014 16:42
Show Gist options
  • Save wo0dyn/15e5006be77bf00bcf01 to your computer and use it in GitHub Desktop.
Save wo0dyn/15e5006be77bf00bcf01 to your computer and use it in GitHub Desktop.
Find a 9 letter string of characters that contains only letters from “acdegilmnoprstuw” such that the hash(the_string) is “910897038977002”.

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

# -*- 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment