I'm currently working on solving the SmartWordToy TopCoder problem:The toy company I Can't Believe It Works! has hired you to help  develop educational toys. The current project is a word toy that  displays four letters at all times. Below each letter are two buttons  that cause the letter above to change to the previous or next letter  in alphabetical order. So, with one click of a button the letter 'c'  can be changed to a 'b' or a 'd'. The alphabet is circular, so for  example an 'a' can become a 'z' or a 'b' with one click. In order to test the toy, you would like to know if a word can be  reached from some starting word, given one or more constraints. A  constraint defines a set of forbidden words that can never be  displayed by the toy. Each constraint is formatted like X X X X,  where each X is a string of lowercase letters. A word is defined by a  constraint if the ith letter of the word is contained in the ith X of  the contraint. For example, the constraint lf a tc e defines the  words late, fate, lace and face. You will be given a String start, a String finish, and a String[]  forbid. Calculate and return the minimum number of button presses  required for the toy to show the word finish if the toy was originally  showing the word start. Remember, the toy must never show a forbidden  word. If it is impossible for the toy to ever show the desired word,  return -1.DefinitionClass:    SmartWordToyMethod:   minPressesParameters:   String, String, String[]Returns:  intMethod signature: int minPresses(String start, String finish, String[] forbid)(be sure your method is public)and trying to implement the BFS approach maintaining the queue of words to analyze while keeping track of visited and forbidden words.Here is my current implementation:from collections import dequefrom itertools import productdef get_combinations(word):    Get a next and previous word variation for every character.    for index, char in enumerate(word):        next_char = chr(ord(char) + 1)        prev_char = chr(ord(char) - 1)        # make it a cycle        if char == 'a':            prev_char = 'z'        if char == 'z':            next_char = 'a'        yield word[:index] + next_char + word[index + 1:]        yield word[:index] + prev_char + word[index + 1:]class SmartWordToy:    def minPresses(self, start, finish, forbid):        # if we've got the solution with no presses        if start == finish:            return 0        forbidden = set([.join(variation)                         for item in forbid                         for variation in product(*item.split())])        # if finish is forbidden, it is never reachable        if finish in forbidden:            return -1        visited = set()        # double-ended queue for the BFS approach        queue = deque([(start, 0)])        while queue:            # take the next element from queue            word, presses = queue.popleft()            # mark word as visited            visited.add(word)            # make two changes for every character and check if we reached finish            for item in get_combinations(word):                if item == finish:                    return presses + 1                # put a word variation to queue if not already visited and not forbidden                if item not in forbidden and item not in visited:                    queue.append((item, presses + 1))        # we've got no match        return -1It works on multiple sample inputs, like:print(SmartWordToy().minPresses(aaaa, gzzb, {}))  # prints 9print(SmartWordToy().minPresses(aaaa, zaaz, {z z a a}))  # prints 2print(SmartWordToy().minPresses(aaaa, zzzz, {z z z z}))  # prints -1print(SmartWordToy().minPresses(aaaa, aaaa, {}))  # prints 0But, if the edit distance (the presses counter) is becoming larger, like for example on the following input:SmartWordToy().minPresses(aaaa, aagg, {})The program quickly starts to eat a lot of memory (1GB in just a few seconds on my machine) and exceeds the allowed time limit as well. And, this is not even a worst case. How would you recommend to improve my current approach and keep track of visited words in a more efficient manner? Will appreciate any other feedback.
The BFS approach to the SmartWordToy challenge
python;performance;breadth first search;memory optimization
You are marking a vertex as visited while taking it out of the queue and not while pushing it. Hence there can be a large number of copies of the same vertex in the queue, worsening the space and time complexity.The solution is to mark a vertex as visited while pushing it in the queue.