Boggle Solver in Python

Question

Please excuse my poor styling and/or code. I need this to run faster, but I have little knowledge of how to do that.

Here is a bit of an explanation about boggle, however you can find more online.

It takes the board as a 1 line input (argv[1]) and a list of words (argv[2]) as a dictionary. My solution is to make a dictionary specific to each board, excluding words that cannot be made before checking the board. It works relatively well for small test cases (see example below), however takes a long time when it comes to larger ones.

If anyone could please give me some pointers that would be much appreciated. I am not looking to completely change the code I have already, but I want to make it faster.

Inputs: argv[1]:

ateeapyotinuedse

argv[2]

import sys, copy, time
import numpy as np


#  ===================== Dictionary Class Start =================================

class Dictionary(object):
    def __init__(self, letters, diclist):
        self.idx = 0
        self.letters, self.diclist = letters, diclist
        self.allcouples = set()
        self.size = 0
        self.matrix = self.make_board(letters)
        self.diags = [self.matrix[::-1,:].diagonal(i) for i in range(-3, 4)]
        self.diags.extend(self.matrix.diagonal(i) for i in range(3, -4, -1))
        self.reduce()
        self.size_matters()

    def __str__(self): return str(self.ws)
    def __iter__(self): return self
    def __next__(self):
        self.idx += 1
        try: return list(self.ws)[self.idx-1]
        except IndexError:
            self.idx = 0
            raise StopIteration

    def make_board(self, letters, n=4):
        return np.array([list(letters[i:i+n]) for i in range(0, len(letters), n)])

    def pairs(self, s):
        s1, s2 = s, s[::-1]
        return set([''.join(pair) for pair in zip(s[:-1], s[1:])] + [''.join(pair) for pair in zip(s2[:-1], s2[1:])])

    def reduce(self):
        for row in self.matrix: self.allcouples |= (self.pairs("".join(row)))
        for i in range(4): self.allcouples |= (self.pairs("".join(np.concatenate(self.matrix[:,[i]]))))
        for n in self.diags:
            if len(n) > 1: self.allcouples |= (self.pairs("".join(list(n))))

        board = set(self.letters)

        self.ws = set([w for w in self.diclist if set(w) < board and w[:2] in self.allcouples])
        self.size = len(self.ws)

    def size_matters(self):
        self.ws = [w for w in self.ws if all([w.count(l) <= self.letters.count(l) for l in w])]
        # print(len(self.ws))




# ===================== Checker Class Start =================================

class Checker(object):
    def __init__(self, board):
        self.board, self.letters,self.adj_list = board, {}, {}
        ds = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

        for i in range(4):
            for j in range(4):
                    if board[i][j] not in self.letters: self.letters[board[i][j]] = []
                    self.letters[board[i][j]].append((i, j))
                    self.adj_list[(board[i][j], i, j)] = []

                    for d1, d2 in ds:
                        k,l = i+d1, j+d2
                        if k >= 0 and k < 4 and l >= 0 and l < 4:
                            self.adj_list[(board[i][j], i, j)].append((board[k][l], k, l))

    def dfs(self, word):
        if len(word) < 3 or word[0] not in self.letters: return False
        stack =[(word[0], word, (word[0], i, j), set([(i, j)])) for i, j in self.letters[word[0]]]

        while len(stack) > 0:
            sub, word, let, positions = stack.pop()
            if sub == word: return True
            next_letter = word[len(sub)]

            for l, i, j in self.adj_list[let]:
                if l == next_letter and (i, j) not in positions:
                    p2 = copy.deepcopy(positions)
                    p2.add((i, j))
                    stack.append((sub+next_letter, word, (l, i, j), p2))

        return False

# ======================== Classes End ===================================



def p(word):
    if len(word) < 8: return {'3':1,'4':1,'5':2,'6':3,'7':5}[str(len(word))]
    elif len(word) >= 8: return 11
    else: return 0

def its_boggle_time_baby(b):
    board = list(zip(*[iter(b)]*4))
    # print(board)
    g = Checker(board)
    words = [(word, p(word)) for word in d if g.dfs(word)]
    # for w in words: print(w)
    total_points = 0
    for word, points in words: total_points += points
    print("Possible points: {}".format(total_points))

def main():

    t1 = time.time()

    dic = [w.strip() for w in open(sys.argv[2]) if len(w.strip()) >= 3]

    boardz = [bz.strip() for bz in open(sys.argv[1]).readlines()]
    for bz in boardz:
        global d
        d = Dictionary(bz, dic)
        its_boggle_time_baby(bz)

    t2 = time.time()
    print(t2-t1)

    # print(d)
    # for w in dic: print(w)

if __name__ == '__main__':
    main()

Here is the cProfile. I can see it spends a lot of time on the listcomps but don't know how to shorten them.

Answer 1

As mentioned in my comment, I was unable to download your word list. For testing I have used a file with the most common four thousand English words that I happened to have to hand. I ran 1000 iterations against this file, using the board letters you provided.

I paid most attention to this listcomp line.

self.ws = set([w for w in self.diclist if set(w) < board and w[:2] in self.allcouples])

To better understand where the time was being spent and where the benefit came from, I ran the following:

    T1 = set([w for w in self.diclist if True])
    T2 = set([w for w in self.diclist if w[:2] in self.allcouples])
    T3 = set([w for w in self.diclist if set(w) < board])
    T4 = set([w for w in self.diclist if set(w) < board and w[:2] in self.allcouples])
    T5 = set([w for w in self.diclist if w[:2] in self.allcouples and w[1:3] in self.allcouples])
    T6 = set([w for w in self.diclist if w[:2] in self.allcouples and set(w) < board])
    T7 = set([w for w in self.diclist if w[:2] in self.allcouples and w[1:3] in self.allcouples and set(w) < board])

These are not identical filters, and the number of words they allow to pass is as follows.

T1 4035
T2 898
T3 232
T4 139
T5 319
T6 139
T7 89

Unsurprisingly my T1 line that didn't bother to filter anything was the fastest by an order of magnitude, (t=0.096) but this no-op has costs further down the line. Similarly unsurprisingly T2 was the next fastest (t=0.807). T3 was almost as slow as T4 (your original version) even though it is a weaker filter. (2.196 and 2.268 respectively). T5 clocked in at 0.988, T6 at 1.330 and T7 at 1.172. One important consideration here is the short circuiting behaviour of and: T6 and your T4 are identical filters but T6 can run much faster by doing the quick test first.

Switching in my test from T4 to T7 moved the total runtime of my test (1000 iterations of the dictionary creation and dfs) from 7.737 to 5.345 seconds, roughly saving one second in doing the filter faster and another in filtering out more wrong words.

In your profiling, you found similarly high total time in the listcomp on line 111 :

dic = [w.strip() for w in open(sys.argv[2]) if len(w.strip()) >= 3]

I have not checked this myself, first because I don't have access to the original file, and second because this is run once at program load rather than once per board and is asymptotically cheap. I do note that about a third of the cumtime on that line comes from the strip() function calls. If you do judge it worth shaving the time off, I would suggest you look first to avoiding calling strip twice, and second to whether the input file is regular enough in where whitespace appears to handle more cheaply. (Incidentally, my T7 test above will reject any words shorter than 3 characters anyway, so if you use it you could actually just remove the second strip and length test altogether.)

The list comprehensions are not necessarily the lowest hanging fruit for further optimisation. In my 5.367 second run, 3.367 seconds were spent within the dfs call. Of those, 2.740 were spent running deepcopy. This suggests that if some alternative data structure could be used to record the visited tiles (I would be looking for some sort of immutable deque) which avoids the need for the clone, significant savings may be available.

Such improvements notwithstanding, it is always worth working from the rule that the fastest work is the work you don't do, perhaps look at ways to share work between words. Intuitively if you search for "cats" and then want to search for "catch", it makes sense to start from the end of "cat" rather than redoing that initial chunk of work. There are various possible approaches to benefiting from this.

1. One approach is to use a trie (spelling correct) data structure, exploiting the same benefits as make it good for use in predictive text software. Essentially you'd convert your whole data structure to a tree of shared prefixes, and then your dfs would explore the tree, yielding a word every time it passed through one.

2. Simply to build a cache of shared prefixes and the stack states at which those prefixes are reached. This requires care in deciding what to cache and when to remove things from the cache. If the dictionary is sorted alphabetically ahead of time, you are guaranteed to only need to cache the common prefix between two adjacent words. For example as you go from "advance" to "advanced", stack states for reaching everything should be stored. Going on to "advantage" and all states plotting routes to the first 5 letters should be kept, but those to "advanc" and longer can be discarded.

There may be similar opportunities to benefit from shared suffixes or arbitrary shared substrings, but they are much harder to exploit. (In particular, the need to consider which cells have already been used would require more effort than the benefit would be likely to justify.)

Lest I come across as overly critical, the number of times in writing this today that I have thought of a potential optimisation only to re-read the code more carefully and see you have already done it is frustratingly and commendably high. The fact that the question came with profiling information speaks wonders on its own. The whole review experience has been educational, and fun, for me. So thank you for that.