HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Boggle board game solver in Python

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewstackoverflowgamepythonpython-3.x
bogglegamepythonsolverboard

Problem

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,

Solution


  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.

  1. Loading a dictionary



-
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.

-
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.

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

-
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


  1. Boggle position



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

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

-
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 ` should be returned.

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

-
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.)

-
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.

-
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.

-
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 0:
a.append(i - 1)
if col < size - 1:
a.append(i + 1)

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

Code Snippets

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
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
points = points if points is not None else {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}
_POINTS = {3: 1, 5: 2, 6: 3, 7: 5, 8: 11}
_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

Context

StackExchange Code Review Q#146261, answer score: 8

Revisions (0)

No revisions yet.