Однобуквенный выпуск игры?
Недавно на собеседовании мне дали следующую проблему:
Напишите скрипт, способный работать в командной строке как python
Он должен состоять из двух слов в командной строке (или, при желании, он может запросить пользователя ввести два слова через консоль).
Учитывая эти два слова: Убедитесь, что они имеют одинаковую длину b. Убедитесь, что оба слова присутствуют в словаре допустимых слов на английском языке, который вы загрузили.
Если это так, вычислите, можете ли вы найти второе слово из первого, выполнив ряд шагов следующим образом: a. Вы можете изменить одну букву за раз б. Каждый раз, когда вы меняете букву, результирующее слово также должно существовать в словаре c. Вы не можете добавлять или удалять письма
Если два слова достижимы, сценарий должен распечатать путь, который ведет как один кратчайший путь от одного слова к другому.
Вы можете / usr / поделиться / 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
Спасибо за все отличные ответы. Я думаю, что действительно меня поразило, так это то, что я перебираю ВСЕ слова в словаре каждый раз, чтобы рассмотреть возможных соседей по словам. Вместо этого я мог бы использовать перевернутый индекс, на что указывали Дункан и Мэтт Андерсон. * Подход тоже определенно помог бы. Большое спасибо, теперь я знаю, что я сделал не так.
Вот тот же код с инвертированным индексом:
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 сек.):
=> Счастливое - Гарпия - Арфы - Харты - Остановки - Холлы - Ады - Привет% python one_letter_game.py happy hello Кратчайший путь (найден за 1,71 сек.):
=> Счастливое - Гарпия - Арфы - Харты - Остановки - Холлы - Ады - Привет
5 ответов
Я бы не сказал, что ваше решение неверно, но оно немного медленное. По двум причинам.
При поиске в ширину собираются все пути длиной на один короче, чем необходимо, плюс некоторые пути всех необходимых длин, прежде чем он сможет дать вам ответ. Поиск по принципу "лучший первый поиск" (A*) в идеале пропускает большинство нерелевантных путей.
Вы проверяете каждое слово в словаре на кандидатуру в качестве соседа каждый раз, когда ищете соседей. Как предполагает Дункан, вы можете построить структуру данных, чтобы по существу искать соседей, а не искать их.
Вот еще одно решение вашей проблемы:
import collections
import heapq
import time
def distance(start, end):
steps = 0
for pos in range(len(start)):
if start[pos] != end[pos]:
steps += 1
return steps
class SearchHeap(object):
def __init__(self):
self.on_heap = set()
self.heap = []
def push(self, distance, word, path):
if word in self.on_heap:
return
self.on_heap.add(word)
heapq.heappush(self.heap, ((distance, len(path)), word, path))
def __len__(self):
return len(self.heap)
def pop(self):
return heapq.heappop(self.heap)
class OneLetterGame(object):
_word_data = None
def __init__(self, dict_path):
self.dict_path = dict_path
def run(self, start_word, end_word):
start_time = time.time()
self._word_data = collections.defaultdict(list)
if len(start_word) != len(end_word):
print 'words of different length; no path'
return
found_start, found_end = self._load_words(start_word, end_word)
if not found_start:
print 'start word %r not found in dictionary' % start_word
return
if not found_end:
print 'end word %r not found in dictionary' % end_word
return
search_start_time = time.time()
path = self._shortest_path(start_word, end_word)
search_time = time.time() - search_start_time
print 'search time was %.4f seconds' % search_time
if path:
print path
else:
print 'no path found from %r to %r' % (start_word, end_word)
run_time = time.time() - start_time
print 'total run time was %.4f seconds' % run_time
def _load_words(self, start_word, end_word):
found_start, found_end = False, False
length = len(start_word)
with open(self.dict_path) as words:
for word in words:
word = word.strip()
if len(word) == length:
if start_word == word: found_start = True
if end_word == word: found_end = True
for bucket in self._buckets_for(word):
self._word_data[bucket].append(word)
return found_start, found_end
def _shortest_path(self, start_word, end_word):
heap = SearchHeap()
heap.push(distance(start_word, end_word), start_word, (start_word,))
while len(heap):
dist, word, path = heap.pop()
if word == end_word:
return path
for neighbor in self._neighbors_of(word):
heap.push(
distance(neighbor, end_word),
neighbor,
path + (neighbor,))
return ()
def _buckets_for(self, word):
buckets = []
for pos in range(len(word)):
front, back = word[:pos], word[pos+1:]
buckets.append(front+'*'+back)
return buckets
def _neighbors_of(self, word):
for bucket in self._buckets_for(word):
for word in self._word_data[bucket]:
yield word
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:
matt = OneLetterGame(dict_path = '/usr/share/dict/words')
matt.run(*sys.argv[1:])
И, сравнение времени:
% python /tmp/one_letter_alex.py canoe happy
The shortest path (found in 51.98 sec.) is:
=> canoe -- canon -- caxon -- taxon -- taxor -- taxer -- taper -- paper -- papey -- pappy -- happy
% python /tmp/one_letter_matt.py canoe happy
search time was 0.0020 seconds
('canoe', 'canon', 'caxon', 'taxon', 'taxor', 'taxer', 'taper', 'paper', 'papey', 'pappy', 'happy')
total run time was 0.2416 seconds
Я согласен, что было бы странно ожидать, что ваш ответ на этот программный тест будет единственной причиной, по которой они выбрали кого-то другого, но на самом деле есть проблемы с вашим кодом. Вы делаете линейный поиск по словарю для каждого шага пути или каждого потенциального пути. Это может занять много времени для большого словаря и множества потенциальных путей. Также вполне очевидно, что вы не проверили его полностью, так как он не работает, когда нет пути.
Если бы я кодировал это, я бы при загрузке слов создал бы словарь, который бы убрал линейный поиск, позволяя вам довольно четко выбрать следующие слова. Этот код не является полным решением, но должен указать, что я имею в виду:
words = {}
def get_keys(word):
"""Generate keys from a word by replacing each letter in turn by an asterisk"""
for i in range(len(word)):
yield word[:i]+'*'+word[i+1:]
def get_steps(word):
"""Find the set of all words that can link to the given word."""
steps = []
for key in get_keys(word):
steps.extend(words[key])
steps = set(steps) - set([word])
return steps
# Load the dictionary
for word in ('start', 'stare', 'spare', 'spore'):
for key in get_keys(word):
if key not in words:
words[key] = []
words[key].append(word)
print(words)
print(get_steps('stare'))
Может быть, вы не хотели работать в такой компании с самого начала. Я лично не верю в рецензии кода. Я думаю, что если вы проделали достаточно хорошую работу с проверкой портфолио и прошлых ссылок, то в тестах спотового кода это не нужно. Компании с жесткой политикой, подобной этой, никогда не добиваются успеха, поскольку все, что они используют, - это один из треков кода, который думает о коде 24/7. Просто мои 2 цента.
Может быть, они ожидали, что поиск A* с расстоянием редактирования в качестве оценки?
Может быть, вы забыли добавить шебанг? >-|
Или, может быть, им просто не понравился ваш стиль кодирования... Например, я бы не создал класс для такой простой проблемы, это слишком сложное решение (хотя я не настолько разборчив, чтобы принимать решение о найме). только на это, конечно).