dsouza.judepk
BAN USERdef unscramble(scrambled, words):
result = [letter for letter in scrambled]
# Scan through the words in dict
# For each word, find it's anagram and replace it with the actual word.
for word in words:
# Scan through the scrambled sentence with a
# window of length of the word.
start = 0
end = len(word)
while end < len(result)+len(words): # We'll be adding spaces for each word we find.
# Capture potential corresponding scrambled word in the window
scrambled_word = result[start:end]
# Anagram check
if sorted(scrambled_word) == sorted(word):
# Insert space for the sentence
result.insert(start, " ")
# Replace scrambled word with actual word
result[start+1:end+1] = word
break
# Didn't find it, move the window
start += 1
end += 1
return "".join(result).strip()
def test():
scrambled = "elhloothtedrowl"
words = ["the", "hello", "to", "world"]
result = unscramble(scrambled, words)
assert result == "hello to the world", result
test()
Basically turning the char array into an int array to make easier decisions
which direction to move next. The decision is based on the following conditions:
RIGHT If current_char < target_char and target_char is within upper_bound
example, current_char=c, target_char=d
DOWN If current_char < target_char and upper_bound < target_char
example, current_char=c, target_char=x
UP If current_char > target_char and lower_bound > target_char
example, current_char=w, target_char=b
LEFT If current_char > target_char and target_char is within the lower_bound
example, current_char=e, target_char=b
current_char is the char you are currently traversing on in the array
target_char is the destination char you want to reach
lower_bound is determined based on the currently traversed row, these would be (a, f, k, p, u, z)
upper_bound is determined the same way, except these are on the opposite border (e, j, o, t, y).
- dsouza.judepk May 30, 2018