python - 一个字母游戏问题？

Question

最近在一次工作面试中，我遇到了以下问题:

1. 编写一个能像python一样在命令行运行的脚本

2. 它应该在命令行上输入两个词(或者如果您愿意，它可以选择通过控制台询问用户以提供这两个词​​)。

3. 鉴于这两个词:一个。确保它们的长度相等b.确保它们都是英语有效单词词典中的单词你下载的。

4. 如果是这样，请计算您是否可以通过以下一系列步骤从第一个单词到达第二个单词一个。您一次可以更改一个字母b.每次你改变一个字母，得到的单词也必须存在于字典中C。您不能添加或删除字母

5. 如果这两个词是可达的，脚本应该打印出从一个词到另一个词的一条最短路径。

6. 你可以/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

---

感谢您提供所有出色的答案。我认为真正让我着迷的是我每次都会遍历字典中的所有单词以考虑可能的单词邻居。相反，我可以使用 Duncan 和 Matt Anderson 指出的倒排索引。 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 The shortest path (found in 91.57 sec.) is:
=> happy -- harpy -- harps -- harts -- halts -- halls -- hells -- hello

% python one_letter_game.py happy hello The shortest path (found in 1.71 sec.) is:
=> happy -- harpy -- harps -- harts -- halts -- halls -- hells -- hello

Answer 1

我不会说您的解决方案错误，但它有点慢。有两个原因。

1. 广度优先搜索将访问所有长度比所需长度短一个的路径，加上所需长度的部分到所有路径，然后才能给您答案。最佳优先搜索 (A*) 理想情况下会跳过大多数不相关的路径。

2. 每次寻找邻居时，您都在检查字典中的每个单词是否可以成为邻居。正如 Duncan 所建议的，您可以构建一个数据结构来查找邻居而不是搜索它们。

这是您问题的另一种解决方案:

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