Last active
October 22, 2016 03:25
-
-
Save wcharczuk/b9c6ee72ed79ffc1920d to your computer and use it in GitHub Desktop.
Generate "Word Path" Between Two Words
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #goal is to compute the 'path' from one valid word to another by only changing one letter at a time (forming valid words inbetween) | |
| #example: | |
| # cat -> dog | |
| # cat -> cot -> cog -> dog | |
| import sys | |
| import string | |
| alphabet = string.ascii_lowercase | |
| word_dict = dict() | |
| def load_dictionary(): | |
| dict_file = open('/usr/share/dict/words', 'r') | |
| for line in dict_file: | |
| trimmed = line[:len(line)-1] | |
| word_dict[trimmed] = True | |
| def is_valid_word(word): | |
| return word in word_dict | |
| def sub_at_index(word, index, letter): | |
| return word[:index] + letter + word[index+1:] | |
| def permute_possible_words(word): | |
| #for each letter, change to any letter that is not the current letter, test if that makes a valid word | |
| new_words = [] | |
| for index in range(0, len(word)): | |
| c = word[index] | |
| for new_c in alphabet: | |
| if c != new_c: | |
| new_word = sub_at_index(word, index, new_c) | |
| if is_valid_word(new_word): | |
| new_words.append(new_word) | |
| return new_words | |
| def compute_path(word1, word2): | |
| if len(word1) == 0: | |
| print "Error: Invalid word length" | |
| sys.exit(1) | |
| if len(word1) != len(word2): | |
| print "Error: Words are not the same length" | |
| sys.exit(1) | |
| if word1 == word2: | |
| return [word1, word2] | |
| state_queue = [(word1, [word1])] | |
| while len(state_queue) != 0: | |
| word, path = state_queue.pop(0) | |
| for new_word in permute_possible_words(word): | |
| if not( new_word in path ): | |
| new_path = path[:] | |
| new_path.append(new_word) | |
| if new_word == word2: | |
| return new_path | |
| else: | |
| state_queue.append( (new_word, new_path ) ) | |
| return path | |
| if __name__ == "__main__": | |
| load_dictionary() | |
| word1 = sys.argv[1] | |
| word2 = sys.argv[2] | |
| path = compute_path(word1, word2) | |
| for word in path: | |
| print word |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment