5
\$\begingroup\$

`Boggle is a word game in which letters are randomly placed in a 4x4 grid e.g:

A D Q P
N L E M
O S R T
V K J H

Words can be started from any letter and are formed by finding a sequence of connecting letters. Letters may connect diagonally, vertically or horizontally.

Example words on the above board are "son", lad" and "land". Letters may not be re-used.

Below is a recursive solution to the boggle board. The problem with my solution is it is very slow. I had to limit word length to 8 otherwise it takes far too long.

Please can you comment on general style improvements and if you can think of another method to solve this game, a hint as to what I should do for my next attempt.

The dictionary is from here

"""Boggle game solver"""
import copy


def words_from(board, row, column, running_string="", list_words=[]):
    """Calculate all possible words from a given starting position [row, column]"""
    if row in (4, -1) or column in (4, -1):
        return
    if len(running_string) > 4:
        return
    if board[row][column] != "-":
        new_string = running_string + board[row][column]
        new_board = copy.deepcopy(board)
        new_board[row][column] = "-"
        # Add new word
        if len(new_string) >= 3:
            list_words.append(new_string.lower())

        # Find next word
        next_move = [
            (1, 1),
            (-1, -1),
            (1, -1),
            (-1, 1),
            (1, 0),
            (0, 1),
            (-1, 0),
            (0, -1),
        ]
        for dx, dy in next_move:
            words_from(new_board, row + dx, column + dy, new_string, list_words)
        return list_words


def get_permutations(board):
    """Get all permutations """
    set_permutations = set()
    counter = 0
    print("Working..", end = "")
    for row in range(4):
        for column in range(4):
            print(".", end="")
            counter += 1
            words = words_from(board, row, column, list_words=[])
            if words:
                for word in words:
                    set_permutations.add(word)
            words = None
    return sorted(list(set_permutations))

def dictionary_check(set_permuations):
    """Check set_permutations for valid English words"""
    dictionary = {}
    with open("en-dict.txt", "r", encoding="utf8") as file:
        for line in file:
            dictionary[line.strip()] = 0

    counter = 0
    for word in set_permuations:
        if word.lower() in dictionary:
            counter += 1
            print(word)
    print(f"======\n{counter} words")


def find_words(board):
    """Find words on the boggle board"""
    set_permutations = get_permutations(board)
    print("Performing dictionary check....")
    dictionary_check(set_permutations)


def build_board(string):
    """Build board from string"""
    if len(string) != 16:
        print("Error. Must enter 4*4 grid (16 characters)")
        return
    board = [[*string[0:4]], [*string[4:8]], [*string[8:12]], [*string[12:16]]]
    find_words(board)


if __name__ == "__main__":
    string_board = "playthiswordgame"
    build_board(string_board)

\$\endgroup\$
  • \$\begingroup\$ Please tell us which python version this is. \$\endgroup\$ – t3chb0t Jun 18 at 19:06
  • 2
    \$\begingroup\$ Python 3.7. Sorry \$\endgroup\$ – EML Jun 18 at 19:06
  • \$\begingroup\$ When I ran it no words were printed. Perhaps you preprocessed your downloaded word list to make it lowercase? If that's not in the instructions, you should ensure you use the same case (upper or lower) in your dictionary as you're querying. \$\endgroup\$ – Josiah Jun 18 at 21:13
  • \$\begingroup\$ @Josiah I am so sorry. I linked the wrong dictionary. I have updated the link. Sorry \$\endgroup\$ – EML Jun 18 at 21:16
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 14 → 12 \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jun 18 at 22:40
3
\$\begingroup\$

The problem that you observe with this program is speed, so let's look at that.

Running the program, I immediately noticed that the get_permutations section was slow, and the dictionary_check section was many times faster. That immediately tells me that it's not worth looking for faster ways to do the dictionary_check until get_permutations is much faster. After all, even if we could make dictionary_check take no time at all, the program would take almost as long to run!

Of course, I've been a bit naughty there. I went with my internal clock, when what I should do is use a tool. This is the result of running cprofile.

python -m cProfile -s cumtime boggle.py

             116983186 function calls (93930898 primitive calls) in 32.455 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   32.455   32.455 {built-in method builtins.exec}
        1    0.052    0.052   32.455   32.455 boggle.py:1(<module>)
        1    0.009    0.009   32.403   32.403 boggle.py:62(find_words)
        1    0.085    0.085   31.945   31.945 boggle.py:34(get_permutations)
5763088/16    4.231    0.000   31.726    1.983 boggle.py:15(words_from)
15128064/720384   12.915    0.000   27.119    0.000 copy.py:132(deepcopy)
3601920/720384    5.565    0.000   25.605    0.000 copy.py:210(_deepcopy_list)
 30256128    3.207    0.000    3.207    0.000 {method 'get' of 'dict' objects}
  3601920    1.764    0.000    2.288    0.000 copy.py:252(_keep_alive)
 23052288    1.619    0.000    1.619    0.000 {built-in method builtins.id}
 18009500    1.261    0.000    1.261    0.000 {method 'append' of 'list' objects}
 11526144    0.840    0.000    0.840    0.000 copy.py:190(_deepcopy_atomic)
        1    0.289    0.289    0.448    0.448 boggle.py:50(dictionary_check)
  4431757    0.324    0.000    0.324    0.000 {built-in method builtins.len}
   720284    0.131    0.000    0.131    0.000 {method 'add' of 'set' objects}
      173    0.076    0.000    0.076    0.000 {built-in method builtins.print}
   712738    0.067    0.000    0.067    0.000 {method 'lower' of 'str' objects}
   178691    0.017    0.000    0.017    0.000 {method 'strip' of 'str' objects}
      240    0.000    0.000    0.003    0.000 cp1252.py:22(decode)
      240    0.003    0.000    0.003    0.000 {built-in method _codecs.charmap_decode}
        1    0.000    0.000    0.000    0.000 {built-in method io.open}
        1    0.000    0.000    0.000    0.000 _bootlocale.py:11(getpreferredencoding)
        1    0.000    0.000    0.000    0.000 {built-in method _locale._getdefaultlocale}
        1    0.000    0.000    0.000    0.000 boggle.py:5(check_board)
        1    0.000    0.000    0.000    0.000 codecs.py:259(__init__)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

The first few lines are just the call sequence in: for example there's a lot of time (cumtime) spent in find_words but almost all of it is in functions that it's calling and very little in the function directly (tottime). That's not where you want to cut down.

Instead, a huge amount of time is spent within deepcopy: 27 of 32 seconds. That is genuine time expenditure, and a good place to start hitting. Two options occur to me: either look for a simpler board representation that is cheaper and easier to copy, or try to avoid the copies.

For option 1, the obvious simpler thing is a flat list or tuple with sixteen elements, which you then index into as [row * 4 + column]. The data would be the same, but you'd avoid the overhead of copying all the extra lists.

For option 2, you'd want to use one board and keep track of what you're changing (and, depending on your implementation, perhaps exactly one copy of the board you never change). When you use a letter you'd stub it out; when you come back up the tree you'd replace the stub symbol with the original letter.

I haven't done it myself and it's always dangerous guessing at performance, but I would be optimistic about getting four to five times faster with that second change.


The above is trying for efficiency gains with minimal changes to the underlying algorithm. If you want to get much faster, however, you'll need to change your approach to the problem. The first rule of getting a job done faster is "The fastest work is the work you don't do."

Although I said earlier and stand by that you don't need to start optimising dictionary_check, there may be some opportunities to benefit from knowing your word list while you explore the grid. For example, there are no words that start with "plt". If, then, your running_string is "plt" then all future strings you find are guaranteed to get filtered out at the end. One option would be to read your word list at the start, and prepare a dictionary of all the prefixes that appear. As you recursively call words_from, if the running_string is not in the prefix dictionary, return immediately. That would probably offer enough gains that you could remove your limit to length 8 words.


I notice that the question and code have been editted several times since I started this answer. I'm just going to post it as is, and hope that except in the most fiddly details it is still helpful.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Its nice to know where the program was slow. As for the changes I made they were just brushing up the code rather than changing the implementation. I will see if I can change the deepcopy method to get a faster result \$\endgroup\$ – EML Jun 18 at 22:25
  • \$\begingroup\$ as you can see from the update now, the code is much faster! Thanks \$\endgroup\$ – EML Jun 18 at 22:31
  • \$\begingroup\$ I will now work on trying to block recursive builds for word prefixes that will never form a word such as "plt" \$\endgroup\$ – EML Jun 18 at 22:35

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.