12
\$\begingroup\$

I have written a Boggle board solver in Python 3. I would like comments on readability and structure. Thank you!

Boggle

Boggle is a board game with a 4x4 board of squares, each of which has a letter, in which you score points by finding words on the board. This is an example Boggle board:

c a t c
a t c a
t c a t
c a t c

This board contains the words 'cat', 'act', 'tact', etc. The words must be made up of neighboring squares, and you can't use the same square twice in a word. Words don't need to be in a straight line.

Program overview

Create an empty Boggle board, with a given word list:

b = Boggle('twl06.txt')

The program depends on an external dictionary file. You can obtain one here for example.

Fill the board, row by row:

b.set_board('catcatcatcatcatc')

List the words in the board:

b.find_words()

Score the board:

b.score()

Code

class Boggle:
    def __init__(self, file, size=4, points=None):
        """
        Boggle board class constructor

        :param file: Path to the dictionary file
        :param size: Size of the board
        :param points: The points corresponding to word lengths
        :return: None
        """
        self.size = size
        self.board = [[' '] * self.size for _ in range(self.size)]
        self.adjacency = self.build_adjacency()
        self.words, self.prefixes = self.load_dictionary(file)

        # Points per word of given length
        points = points if points is not None else {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}
        self.points = [0 for _ in range(self.size**2)]
        for i in range(len(self.points)):
            if i in points:
                self.points[i] = points[i]
            elif i > 0:
                self.points[i] = self.points[i-1]

    def __repr__(self):
        """
        Prints the Boggle board

        :return: A string representation of the board
        """
        return '\n'.join([' '.join(row) for row in self.board])

    def adjacent(self, pos):
        """
        Finds all adjacent positions for a given position on the board

        :param pos: A 2-tuple giving row and column of a position
        :return: A list of positions adjacent to the given position
        """
        row, col = pos
        adj = []
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                new_row = row + i
                new_col = col + j
                if 0 <= new_row < self.size and 0 <= new_col < self.size and not (i == j == 0):
                    adj.append((new_row, new_col))
        return adj

    def build_adjacency(self):
        """
        Builds the adjacency lookup for each position on the board

        :return: A dictionary of adjacent positions for each position on the board
        """
        adjacency = dict()
        for row in range(0, self.size):
            for col in range(0, self.size):
                adjacency[(row, col)] = self.adjacent((row, col))
        return adjacency

    def load_dictionary(self, file):
        """
        Loads a dictionary file into Boggle object's word list

        :param name: Path to the dictionary file
        :return: None
        """
        words = set()
        prefixes = set()
        with open(file, 'r') as f:
            next(f)
            for line in f:
                word = line.rstrip()
                if len(word) >= 3:
                    words.add(word)
                    for i in range(len(word)):
                        prefixes.add(word[:i])
        return words, prefixes

    def get_letter(self, pos):
        """
        Gets the letter at a given position

        :param pos: A 2-tuple giving row and column location of a position
        :return: A letter at the given position
        """
        return self.board[pos[0]][pos[1]]

    def set_board(self, letters):
        """
        Sets the letters on the board

        :param letters: A string giving the letters, row by row
        :return: None
        """
        for row in range(self.size):
            index = row * self.size
            row_letters = letters[index:index+self.size]
            for col, letter in enumerate(row_letters):
                self.board[row][col] = letter

    def find_words(self):
        """
        Finds all words on the board

        :return: A set of words found on the board
        """
        words = set()
        for row in range(self.size):
            for col in range(self.size):
                words |= self.find_words_pos((row, col))
        return words

    def find_words_pos(self, pos):
        """
        Finds words starting at a given position on the board

        :param pos: A 2-tuple giving row and column on the board
        :return: A set of words starting at the given position
        """
        stack = [(n, [pos], self.get_letter(pos)) for n in self.adjacency[pos]]
        words = set()
        while stack:
            curr, path, chars = stack.pop()
            curr_char = self.get_letter(curr)
            curr_chars = chars + curr_char

            # Check if path forms a word
            if curr_chars in self.words:
                words.add(curr_chars)

            # Check if path forms the prefix of a word
            if curr_chars in self.prefixes:
                # Get adjacent positions
                curr_adj = self.adjacency[curr]

                # Check if adjacent positions have already been visited
                stack.extend([(n, path + [curr], curr_chars) for n in curr_adj if n not in path])
        return words

    def score(self):
        """
        Scores the Boggle board

        :return: The Boggle board score
        """
        score = 0
        words = self.find_words()
        for word in words:
            score += self.points[len(word)]
        return score


if __name__ == '__main__':
    b = Boggle('twl06.txt')
    b.set_board('catcatcatcatcatc')
    print(b)
    print(b.find_words())
    print(b.score())
\$\endgroup\$
8
\$\begingroup\$

1. Separation of concerns

A Boggle object is a combination of three things: a dictionary of words, a Boggle position, and rules for scoring a collection of words. The principle of separation of concerns suggests that these should be three different pieces of code. This would make the code easier to understand, test, and reuse.

For example, imagine that you want to apply one dictionary to several different Boggle positions. If dictionaries and Boggle positions were separate objects, this would be easy. But with the code in the post, then you are faced with an unsatisfactory choice between loading the dictionary multiple times (wasting memory), or overwriting the Boggle position (destroying the previous positions).

Similarly, imagine that you wanted to find the score of the list of words found by an interactive user. If scoring were a separate operation, this would be easy. But the code in the post can only find the score of all the words in the position, so couldn't be reused for this use case.

2. Loading a dictionary

  1. When a function loads data from a file, it is convenient if the interface allows the caller to pass either a filename or a file-like object. That's because you don't always have a real file — sometimes you have data that you generated in memory, or fetched over a network connection, or whatever. In the Python standard library, see wave.open or zipfile.ZipFile or many other functions.

  2. The load_dictionary method discards the first line of the file. Is this right? If so, it needs to be explained somewhere in the documentation. But I think it would be better not to do this and let the caller discard the first line if they need to.

  3. The number 3 in load_dictionary is arbitrary and so ought to be a named parameter.

  4. The prefixes set needlessly includes the empty string. This can be avoided by writing range(1, len(word)).

Revised code:

def load_dictionary(file, min_length=3):
    """Load a file of words.

    :param file: Name of the file, or a file-like object.
    :param min_length: Minimum word length.
    :return: Pair (words, prefixes) where words is the set of words
       in the dictionary, and prefixes is the set of valid non-empty
       prefixes.

    """
    def load(f):
        for line in f:
            word = line.rstrip()
            if len(word) >= min_length:
                yield word
    if isinstance(file, str):
        with open(file) as f:
            words = set(load(f))
    else:
        words = set(load(file))
    prefixes = {w[:i] for w in words for i in range(1, len(w))}
    return words, prefixes

3. Boggle position

  1. It's simpler to specify the letters in the position as a parameter to the constructor, avoiding the need for a set_board method.

  2. The board size can be deduced from the number of letters in the position, avoiding the need for the caller to specify it separately.

  3. The __repr__ method is documented as follows:

    If at all possible, this should look like a valid Python expression that could be used to recreate an object with the same value (given an appropriate environment). If this is not possible, a string of the form <...some useful description...> should be returned.

    The implementation here does not meet this specification; it's more suitable for the __str__ method.

  4. I don't think it's worth writing your own docstring for standard methods like __repr__. This ends up just repeating information that is already in the Python documentation. (But there's nothing wrong with doing it if you prefer it that way.)

  5. It would simplify the code if, instead of representing the board as a list of lists, and a position as a tuple (row, col), you represented the board as a flat list, and a position as an index into that list.

  6. The adjacency, build_adjacency and find_words_pos methods are only called from one place (and are not expected to be useful to users of the class) so I would inline these methods at the point of use.

  7. In find_words_pos, the path is represented by a list. But checking whether an element is in a list takes time proportional to the length of the list. It would be more efficient to represent the path as a set.

Revised code:

class Boggle:
    """A position in the game of Boggle."""

    def __init__(self, letters):
        """Construct a Boggle position.

        :param letters: String of letters in the position.

        """
        size = int(len(letters) ** 0.5)
        if size * size != len(letters):
            raise ValueError('Boggle board is not square')
        self.size = size
        self.letters = letters
        self.adjacency = {}
        for i in range(size * size):
            row, col = divmod(i, size)
            self.adjacency[i] = a = []
            if row > 0:
                a.append(i - size)
            if row < size - 1:
                a.append(i + size)
            if col > 0:
                a.append(i - 1)
            if col < size - 1:
                a.append(i + 1)

    def __repr__(self):
        return '{}({!r})'.format(type(self).__name__, self.letters)

    def __str__(self):
        return '\n'.join(map(''.join, zip(*[iter(self.letters)] * self.size)))

    def words(self, dictionary):
        """Find words in the Boggle position using a dictionary.

        :param dictionary: The dictionary to use, in the form of a
            pair of a set of words, and the derived set of valid prefixes.
        :return: The set of words found.

        """
        words, prefixes = dictionary
        found = set()
        for i in range(self.size ** 2):
            stack = [(i, {i}, self.letters[i])]
            while stack:
                curr, used, prefix = stack.pop()
                if prefix in words:
                    found.add(prefix)
                if prefix in prefixes:
                    stack.extend((j, used | {j}, prefix + self.letters[j])
                                 for j in self.adjacency[curr]
                                 if j not in used)
        return found

4. Scoring

  1. Instead of having a keyword argument points=None and then extra code to assign the default value:

    points = points if points is not None else {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}
    

    I would suggest having a global variable:

    _POINTS = {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}
    

    and then having a keyword argument points=_POINTS, avoiding the extra assignment code.

  2. If scoring is separated from the position representation (as suggested in §1 above), it can't depend on the size of the board, and so the lookup logic has to be changed. I suggest using the bisect module, as shown below.

Revised code:

_POINTS = {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}

from bisect import bisect

def score(words, points=_POINTS):
    """Score a collection of words in Boggle.

    :param words: Iterable of words.
    :param points: Map from word length to points.
    :return: The Boggle score for the words.

    """
    p = sorted(points)
    score = 0
    for word in words:
        i = bisect(p, len(word)) - 1
        if i >= 0:
            score += points[p[i]]
    return score

5. Efficiency

The way the search works, it has to constuct a new list path + [curr] (or a new set used | {j} in my revised implementaton) for each node visited in the search, and that requires copying out the old path. It would be more efficient to rearrange the code so that we can call path.append(curr) as we move forward in the search, and then path.pop() as we move back.

Here's an implementation using the stack of iterators pattern:

def words(self, dictionary):
    """Find words in the Boggle position using a dictionary.

    :param dictionary: The dictionary to use, in the form of a
        pair of a set of words, and the derived set of valid prefixes.
    :return: The set of words found.

    """
    words, prefixes = dictionary
    found = set()
    path = [object()]
    path_set = set(path)
    path_prefix = ['']
    stack = [iter(range(self.size ** 2))]
    while stack:
        for i in stack[-1]:
            if i not in path_set:
                prefix = path_prefix[-1] + self.letters[i]
                if prefix in words:
                    found.add(prefix)
                if prefix in prefixes:
                    path.append(i)
                    path_set.add(i)
                    path_prefix.append(prefix)
                    stack.append(iter(self.adjacency[i]))
                    break
        else:
            path_prefix.pop()
            path_set.remove(path.pop())
            stack.pop()
    return found

It's more complex than the naïve version of the search, but I find that it's about twice as fast.

There's a similar efficiency problem with the construction of the prefix strings — again, the old string has to be copied out each time a new string is built. To fix this requires changing the dictionary data structure: what you need is a prefix tree (also known as a "trie"), instead of a set of prefixes.

\$\endgroup\$
4
\$\begingroup\$

Representation

Strings are iterable, meaning that, when reading such data, having a list of n individual characters is no different than having a single string of said n characters. And since you only read self.board except in set_board(), then you could store your first representation as:

    self.board = [' ' * self.size] * self.size

and define your setter as:

def set_board(self, letters):
    self.board = [letters[i*self.size:(i+1)*self.size] for i in range(self.size)]

and, since I just used the word "setter", let's use the more pythonic property instead:

@property
def board(self):
    return '\n'.join(self._board)

@board.setter
def board(self, letters):
    self._board = [letters[i*self.size:(i+1)*self.size] for i in range(self.size)]

Note the use of self._board instead of self.board to avoid a name conflict. Usage being:

b = Boggle('twl06.txt')
b.board = 'catcatcatcatcatc'
print(b.board)

__str__ and __repr__

I didn't use your __repr__ method in the previous example to print the board because:

  1. it can now be just return self.board; and
  2. it is actually the __str__ method that should provide such representation; __repr__ being meant to return the "official" representation of the class. Ideally eval(repr(x)) should return something equivalent to x.

Let's see how we can build that:

def __str__(self):
    return self.board

def __repr__(self):
    points = {self.points.index[pt]: pt for pt in set(self.points)}
    return 'Boggle(file={}, size={}, points={}, board={})'.format(
        self._filename,  # Uh-Oh, we don't have this one, we’ll need to store it
        self.size,
        points,
        ''.join(self._board))

I didn't exactly returned something that uses the actual constructor signature because, even if it's best to match it, it is not a requirement. And also because it could be an improvement to add that board parameter:

def __init__(self, file, size=4, points=None, board=None):
    ...
    if board is None:
        board = ' ' * size * size
    self.board = board  # let's use the property
    ...

Adjacency

First of, since you only call adjacent from build_adjacency and since you already have row and col in this method, why build a tuple to unpack it right after? Why not just pass both values as parameters:

def adjacent(self, row, col):

Second, you uses 2 for loops and a 3-cases condition only to retrieve between 2 and 4 items in a list. This seems a bit too much to me. Instead, I’d retrieve the 4 positions manually and filter them:

def adjacent(self, row, col):
    neighbours = [
        (row, col - 1),  # left
        (row, col + 1),  # right
        (row - 1, col),  # down
        (row + 1, col),  # up
    ]
    return list(filter(lambda pos: all(0 <= p < self.size for p in pos), neighbours))

You can also turn build_adjacency into a dict-comprehension:

def build_adjacency(self):
    size = self.size
    return {
        (row, col): self.adjacent(row, col)
        for row in range(size) for col in range(size)
    }

I could also suggest to merge the two methods, but it will likely become unreadable, let's see:

def build_adjacency(self):
    size = self.size
    return {
        (row, col): list(filter(
            lambda pos: all(0 <= p < size for p in pos),
            [
                (row, col - 1),  # left
                (row, col + 1),  # right
                (row - 1, col),  # down
                (row + 1, col),  # up
            ]
        ))
        for row in range(size) for col in range(size)
    }

Well, it could have been worse but still, it's not that ideal to get at a glance.

Comprehensions and generator expressions

I just mentionned that for the adjacency building, but there are some other places where you could benefit from using these kind of iteration instead of painfully accumulating stuff in a variable of your own:

  1. Use sum in score:

    def score(self):
        return sum(self.points[len(word)] for word in self.find_words())
    
  2. Use itertools.chain.from_iterable in find_words:

    import itertools
    flatten = itertools.chain.from_iterable
    
    
    def find_words(self):
        _range = range(self.size)
        return set(flatten(
            self.find_words_pos((row, col))
            for row in _range for col in _range))
    

Also, as a personal taste, I would turn these two methods into properties:

@property
def words(self):
    _range = range(self.size)
    return set(flatten(
        self.find_words_pos((row, col))
        for row in _range for col in _range))

@property
def score(self):
    return sum(self.points[len(word)] for word in self.words)

And, lastly, I would simplify the building of self.points by using the last number of points seen:

board_size = size * size  # May be done a bit earlier to define `board = ' ' * board_size`
last_seen = 0
self.points = [last_seen] * board_size
for i in range(board_size):
    last_seen = points.get(i, last_seen)
    self.points[i] = last_seen
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.