Недавно на собеседовании мне поставили следующую задачу:
Напишите скрипт, способный работать в командной строке как python.
Он должен состоять из двух слов в командной строке (или, если вы предпочитаете, он может запросить у пользователя два слова через консоль).
Учитывая эти два слова: а. Убедитесь, что они имеют одинаковую длину b. Убедитесь, что оба слова присутствуют в словаре допустимых слов английского языка, который вы скачали.
Если да, вычислите, можете ли вы добраться до второго слова из первого, выполнив ряд следующих шагов: а. Вы можете изменить одну букву за раз b. Каждый раз, когда вы меняете букву, полученное слово также должно существовать в словаре c. Вы не можете добавлять или удалять буквы
Если два слова достижимы, сценарий должен распечатать путь, который ведет как единственный кратчайший путь от одного слова к другому.
Вы можете использовать /usr/share/dict/words для своего словаря слов.
Мое решение состояло в использовании поиска в ширину для поиска кратчайшего пути между двумя словами. Но, видимо, этого было недостаточно, чтобы получить работу :(
Ребята, вы знаете, что я мог сделать не так? Большое спасибо.
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
Спасибо за все отличные ответы. Я думаю, что меня действительно поразил тот факт, что я каждый раз перебираю ВСЕ слова в словаре, чтобы рассмотреть возможные соседние слова. Вместо этого я мог бы использовать перевернутый индекс, как указали Дункана и Мэтта Андерсона. Подход A* определенно помог бы. Большое спасибо, теперь я знаю, что я сделал не так.
Вот тот же код с перевернутым индексом:
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 = {}
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, self.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 self.in_dictionnary(start), 'Start word not in dictionnary.'
assert self.in_dictionnary(end), '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 in_dictionnary(self, word):
for s in self.get_steps(word):
if s in self.words:
return True
return False
def get_neighbours(self, word):
'''Gets every word one letter away from the a given word.
'''
for step in self.get_steps(word):
for neighbour in self.words[step]:
yield neighbour
def get_steps(self, word):
return (word[0:i] + '*' + word[i+1:]
for i, w in enumerate(word))
def read_dict(self, size):
'''Loads every word of a specific size from the dictionnary into an inverted index.
'''
for w in open(self.dict_path):
w = w.decode('latin-1').strip().lower()
if len(w) != size:
continue
for step in self.get_steps(w):
if step not in self.words:
self.words[step] = []
self.words[step].append(w)
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
И сравнение времени:
% python one_letter_game_old.py happy hello Кратчайший путь (найдено за 91,57 сек.):
=> happy -- гарпия -- арфы -- олени -- привалы -- залы -- ады -- привет% python one_letter_game.py happy hello Кратчайший путь (найдено за 1,71 сек.):
=> happy -- harpy -- harps -- harts -- halts -- Halls -- hells -- hello
