Super Word Search Solution

super_word_search.py

from collections import defaultdict

class SuperWordSearch:
    """
    Solves the Super Word Search variation of the word search problem.
    """

    # All 8 directions (left to right, top to bottom, etc.)
    DIRECTIONS = ((0,1),(1,0),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1))

    def __init__(self, grid, wrap):
        # Grid being search
        self.grid = grid

        # If wrapping the grid while searching is enabled
        self.wrap = wrap

        # Number of rows in the grid
        self.n = len(grid)

        # Number of columns in the grid
        self.m = self.n > 0 and len(grid[0]) or 0

        # Dictionary of chars and their positions in the grid for
        # efficient lookup
        self.char_lookup = defaultdict(list)

        self._preprocess_grid()

    def _preprocess_grid(self):
        """
        Preprocesses the grid for efficient lookup of start positions by
        character for testing against a pattern.
        """
        for r in range(self.n):
            for c in range(self.m):
                self.char_lookup[self.grid[r][c]].append((r,c))

    def _in_bounds(self):
        """
        Checks if the current search position is in the bounds
        of the grid.
        """
        return 0 <= self.r < self.n and 0 <= self.c < self.m

    def _match(self, char):
        """
        Checks if the charater in the pattern matches the character in the
        current search position.
        """
        return char == grid[self.r][self.c]

    def _all_matched(self, offset):
        """
        Checks if all characters of the pattern have been compared.
        """
        return self.pattern_length - 1 == offset

    def _move(self, start, direction, offset):
        """
        Moves the current search position from the start position by the
        offset in a direction. Wrap the search position if it's enabled.
        """
        self.r, self.c = [start[i] + direction[i] * offset for i in range(2)]
        if self.wrap: self.r, self.c = self.r % self.n, self.c % self.m

    def _char_already_compared(self, start, offset):
        """
        Checks if the character in the search position has already been
        compared. Characters can only be used once in Super Word Search.
        """
        # The search position is back at start and we have already moved
        return start == (self.r, self.c) and offset != 0

    def find_pattern(self, pattern):
        """
        Checks if a pattern exists in the grid. If it does, it returns
        the start and end position. If not, it returns None.
        """
        # Empty pattern, no match
        if not pattern: return None

        self.pattern_length = len(pattern)

        for start in self.char_lookup.get(pattern[0], []):
            for direction in self.DIRECTIONS:
                for offset, char in enumerate(pattern):
                    self._move(start, direction, offset)

                    if not self._in_bounds() or not self._match(char) \
                            or self._char_already_compared(start, offset):
                        break

                    if self._all_matched(offset):
                        # Match found
                        return (start,(self.r,self.c))

        # No match found
        return None

if __name__ == '__main__':
    # Read console input
    n, m = map(int, raw_input().split())
    grid = tuple([tuple(raw_input()) for _ in range(n)])
    wrap = raw_input() == 'WRAP'
    patterns = [raw_input() for _ in range(int(raw_input()))]

    # Find patterns in grid and print to console
    word_search = SuperWordSearch(grid, wrap)
    results = map(word_search.find_pattern, patterns)
    format_result = lambda result: result \
            and '(%s,%s) (%s,%s)' % sum(result, ()) \
            or 'NOT FOUND'
    print "\n".join(map(format_result, results))