2
\$\begingroup\$

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.

Definition

Class:    SmartWordToy
Method:   minPresses
Parameters:   String, String, String[]
Returns:  int
Method 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 deque
from itertools import product


def 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 -1

It works on multiple sample inputs, like:

print(SmartWordToy().minPresses("aaaa", "gzzb", {}))  # prints 9
print(SmartWordToy().minPresses("aaaa", "zaaz", {"z z a a"}))  # prints 2
print(SmartWordToy().minPresses("aaaa", "zzzz", {"z z z z"}))  # prints -1
print(SmartWordToy().minPresses("aaaa", "aaaa", {}))  # prints 0

But, 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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This definitely helped! Reduced the memory usage dramatically, made it work faster. It still fails to fit into topcoder's memory constraints for some of the tests, but the memory usage is just a bit over the limit - I'll think of a way to optimize the memory usage. Thanks! \$\endgroup\$ – alecxe Feb 11 '17 at 23:08
  • 1
    \$\begingroup\$ Don't generate forbidden words in the beginning, just check whether each word is forbidden when required. \$\endgroup\$ – Raziman T V Feb 12 '17 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.