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.
