One letter game problem?
- by Alex K
Recently at a job interview I was given the following problem:
Write a script capable of running on the command line as python
It should take in two words on the command line (or optionally if you'd prefer it can query the user to supply the two words via the console).
Given those two words:
a. Ensure they are of equal length
b. Ensure they are both words present in the dictionary of valid words in the English language
that you downloaded.
If so compute whether you can reach the second word from the first by a series of steps as follows
a. You can change one letter at a time
b. Each time you change a letter the resulting word must also exist in the dictionary
c. You cannot add or remove letters
If the two words are reachable, the script should print out the path which leads as a single, shortest path from one word to the other.
You can /usr/share/dict/words for your dictionary of words.
My solution consisted of using breadth first search to find a shortest path between two words. But apparently that wasn't good enough to get the job :(
Would you guys know what I could have done wrong? Thank you so much.
import collections
import functools
import re
def time_func(func):
import time
def wrapper(*args, **kwargs):
start = time.time()
res = func(*args, **kwargs)
timed = time.time() - start
setattr(wrapper, 'time_taken', timed)
return res
functools.update_wrapper(wrapper, func)
return wrapper
class OneLetterGame:
def __init__(self, dict_path):
self.dict_path = dict_path
self.words = set()
def run(self, start_word, end_word):
'''Runs the one letter game with the given start and end words.
'''
assert len(start_word) == len(end_word), \
'Start word and end word must of the same length.'
self.read_dict(len(start_word))
path = self.shortest_path(start_word, end_word)
if not path:
print 'There is no path between %s and %s (took %.2f sec.)' % (
start_word, end_word, find_shortest_path.time_taken)
else:
print 'The shortest path (found in %.2f sec.) is:\n=> %s' % (
self.shortest_path.time_taken, ' -- '.join(path))
def _bfs(self, start):
'''Implementation of breadth first search as a generator.
The portion of the graph to explore is given on demand using get_neighboors.
Care was taken so that a vertex / node is explored only once.
'''
queue = collections.deque([(None, start)])
inqueue = set([start])
while queue:
parent, node = queue.popleft()
yield parent, node
new = set(self.get_neighbours(node)) - inqueue
inqueue = inqueue | new
queue.extend([(node, child) for child in new])
@time_func
def shortest_path(self, start, end):
'''Returns the shortest path from start to end using bfs.
'''
assert start in self.words, 'Start word not in dictionnary.'
assert end in self.words, 'End word not in dictionnary.'
paths = {None: []}
for parent, child in self._bfs(start):
paths[child] = paths[parent] + [child]
if child == end:
return paths[child]
return None
def get_neighbours(self, word):
'''Gets every word one letter away from the a given word.
We do not keep these words in memory because bfs accesses
a given vertex only once.
'''
neighbours = []
p_word = ['^' + word[0:i] + '\w' + word[i+1:] + '$'
for i, w in enumerate(word)]
p_word = '|'.join(p_word)
for w in self.words:
if w != word and re.match(p_word, w, re.I|re.U):
neighbours += [w]
return neighbours
def read_dict(self, size):
'''Loads every word of a specific size from the dictionnary into memory.
'''
for l in open(self.dict_path):
l = l.decode('latin-1').strip().lower()
if len(l) == size:
self.words.add(l)
if __name__ == '__main__':
import sys
if len(sys.argv) not in [3, 4]:
print 'Usage: python one_letter_game.py start_word end_word'
else:
g = OneLetterGame(dict_path = '/usr/share/dict/words')
try:
g.run(*sys.argv[1:])
except AssertionError, e:
print e
