Write code (In Ruby or Python or JavaScript) to find a 9 letter string of charac
ID: 3781475 • Letter: W
Question
Write code (In Ruby or Python or JavaScript) to find a 9 letter string of characters that contains only letters from
acdegilmnoprstuw
such that the hash(the_string) is
930846109532517
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".
Explanation / Answer
The method compute_string written in python solves the above problem:
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))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.