3
\$\begingroup\$

I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles.

class Tile:
    empty = None

    def __init__(self, letter):
        self.letter = letter
        #the dictionary tracks the Tiles that border a given Tile
        self.directionals = {'n':Tile.empty, 's':Tile.empty, 'w':Tile.empty, 'e':Tile.empty, 'nw':Tile.empty, 'ne':Tile.empty, 'sw':Tile.empty, 'se':Tile.empty}

class Board:    
    def __init__(self, length, chars=''):
        self.length = length
        self.grid = [[] for _ in range(length)]

        for i in range(length):
            for _ in range(length):
                new_tile = Tile(randomchar()) #assume randomchar() returns a random character each time
                self.grid[i].append(new_tile)

        for i in range(length):
            for j in range(length):
                tile = self.grid[i][j]

                if i - 1 >= 0:
                    tile.directionals['n'] = self.grid[i - 1][j]
                if i + 1 < length:
                    tile.directionals['s'] = self.grid[i + 1][j]
                if j - 1 >= 0:
                    tile.directionals['w'] = self.grid[i][j - 1]
                if j + 1 < length:
                    tile.directionals['e'] = self.grid[i][j + 1]
                if i - 1 >= 0 and j - 1 >= 0:
                    tile.directionals['nw'] = self.grid[i - 1][j - 1]
                if i - 1 >= 0 and j + 1 < length:
                    tile.directionals['ne'] = self.grid[i - 1][j + 1]
                if i + 1 < length and j - 1 >= 0:
                    tile.directionals['sw'] = self.grid[i + 1][j - 1]
                if i + 1 < length and j + 1 < length:
                    tile.directionals['se'] = self.grid[i + 1][j + 1]

Starting from any Tile, the player will be able to create a word by traversing through unvisited Tiles. After successfully creating a word, the Tiles used to compose that word are reset. For example on a 4-by-4 Board:

   start         player makes 'some'   new Tiles represented by '*'
[[L A P S],         [[L A P S],          [[L A P S],
 [R O S E], ------>  [R O S  ],  ------>  [R O S *],
 [T I M E],          [T I   E],           [T I * E],
 [S O F T]]          [    F T]]           [* * F T]]

Throughout the game, I want to ensure the Board has a minimum number of words able to be made. I want to have the functionality to choose the reset Tiles such that they form words with neighboring Tiles, or else the number of available words on the Board may fall below the threshold.

To accomplish this, I implemented the below function.

def dfs(tile, word, min_word_length=2, max_word_length=5):
    visited = []

    def helper(tile, word):
        if len(word) > max_word_length:
            return
        if tile in visited: 
            return
        #allwords is a list with all the words in the English dictionary
        if word in allwords and len(word) >= min_word_length: 
            print(word)

        visited.append(tile)
        for direction in tile.directionals.values():
            if direction is not Tile.empty and direction not in visited:
                helper(direction, word + direction.letter)
        visited.remove(tile)

    helper(tile, word)

I would create Tiles with random letters for the Tiles needing to be reset, applying the dfs function after each Tile is plugged in to see if a valid word is formed. However, the current implementation is too inefficient: it struggles when max_word_length exceeds 5, exponentially more so on larger boards.

How can I change my implementation so that it'd be more efficient? Ideally, I would like the resetting to happen almost immediately (< 1 second). I was thinking of incorporating memoization, but am not sure how to in this case.

\$\endgroup\$
3
\$\begingroup\$

Obfuscation

Tile.empty is a long, verbose way of saying None. Each time you use it, the Python interpreter must look up Tile in locals(), and then globals(), to find the Tile class object. Then, it needs to look up empty in the Tile dictionary to find the value None. If you simply used None, your code would be faster, because None is a keyword; no heroic efforts are needed by the Python interpreter to determine what this value is.

Dictionary of None values

From the minimal code which has been presented, there is no compelling reason to store each direction in self.directionals. Instead of a direction key returning None (or Tile.empty), that direction could simply not exist in the dictionary. The top-left corner would only contain directions "e", "se", and "s". This would simply this code:

        for direction in tile.directionals.values():
            if direction is not Tile.empty and direction not in visited:
                ...

to this:

        for direction in tile.directionals.values():
            if direction not in visited:
                ...

One less check means less work, and faster performance.

Finally, since you keep asking for tile.directional.values(), you might consider storing these values in their own collection:

        tile.valid_directionals = set(tile.directionals.values())

or, if you must store all 8 directions:

        tile.valid_directionals = set(value for value in tile.directionals.values()
                                      if value is not Tile.empty)

and then using:

        for direction in tile.valid_directionals:
            if direction not in visited:
                ...

Using a set instead of a dict_values iterator may not be any faster, but I'll be taking advantage of it later.

List Comprehension

    self.grid = [[] for _ in range(length)]

    for i in range(length):
        for _ in range(length):
            new_tile = Tile(randomchar()) #assume randomchar() returns a random character each time
            self.grid[i].append(new_tile)

is a long, round about way of writing:

    self.grid = [[Tile(randomchar()) for _ in range(length)] for _ in range(length)]

Whenever you create a list, and then append to it in a loop, consider using list comprehension instead. It is a powerful tool for your tool chest.

Simplify Tests

Consider i - 1 >= 0. The Python Interpreter must lookup the value i, subtract 1 from it, which involves constructing a new int object, or since all the values are going to be small, looking up an interned version. Then, the value is compared to zero, and discarded. Consider the equivalent expression i >= 1, or even i > 0. Look up the value and compare to a constant. No subtraction operation required, no new integer object required for the result, and no discarding of the result of the subtraction after being used. This is still in your executed once initialization code, so performance doesn't matter much, but why be sloppy?

Searching too deep

Your helper function looks approximately like:

    def helper(tile, word):
        if len(word) > max_word_length:
            return

        ...

        for direction in tile.directionals.values():
            if ...:
                helper(direction, word + direction.letter)

Imagine if we've called the helper a few times, and we've just recursed in with word="TRAPS". We start looping around the tiles around the S, skipping the visited tiles, and call helper(direction, "TRAPS" + direction.letter) with direction.letter taking on the values 'O', 'I', 'M', 'E', 'E' and 'S'. In each call, the first thing we do is check len(word) > max_word_length, and return if True. With max_word_length = 5, every one of those calls will immediately return! There is no point iterating to the len(word) == 6 depth! If we checked for this earlier, we could eliminate many useless calls, and save time.

    def helper(tile, word):

        ...

        if len(word) < max_word_length:
            for direction in tile.directionals.values():
                if ...:
                    helper(direction, word + direction.letter)

Redundancy

Furthermore:

def helper(tile, word):
    ...
    if tile in visited: 
        return
    ...
    for direction in tile.directionals.values():
        if direction not in visited:
            helper(direction, word + direction.letter)

You test direction not in visited, and only if that is true will you call helper(direction, ...). In that recursive call, the tile in visited test will therefore never be true. You can remove that redundant check for better performance.

Containment Testing

    #allwords is a list with all the words in the English dictionary
    if word in allwords and len(word) >= min_word_length: 
        ...

First of all, English can contain some really long words, like "tetraiodophenolphthalein". We should shorten this dictionary to words which are max_word_length and less.

possible_words = [word for word in allwords
                  if min_word_length <= len(word) <= max_word_length]

With this, my dictionary size is reduced from 235,886 words down to 17,082. And a smaller dictionary will speed things up.

But what will speed things up more is getting rid of that list. Testing if a word is in a list is an \$O(n)\$ operation. If the words were stored in a set, this reduces search complexity to an \$O(1)\$ operation.

possible_words = set(word for word in allwords
                     if min_word_length <= len(word) <= max_word_length)

Then, containment testing is easy:

    if word in possible_words: 
        ...

word in possible_words doesn't look much different from word in allwords, but the speed-up going from x in list to x in set is quite dramatic.

What about the and len(word) >= min_word_length condition? Where did it go? possible_words only contains words which are at least min_word_length, so we get that for free!

Pruning the Search Tree

Alright, I'm finally where I actually wanted to be to answer this question. The fun part.

How many words in the English dictionary start with "RL"? What about "MS" or "FM" or "TF"? Plenty of words start with "SM" but no words start with `"SMF".

As you are collecting the tile letters into a candidate word, you test whether you have discovered a word, but not whether you've reached a combination which will not start any word. Doing so will prune you search tree, and avoid checking around \$6^3\$ candidate words starting with "RL". Less searching, yields faster performance!

So, how do we prune?

Consider the word "SOME". If we start with "S", we have a possible word. If we start with "SO", we have a possible word. If we start with "SOM", we have a possible word. And if we start with "SOME" we have a possible word. So for each word in our possible_words, we just need to collect all the possible prefixes for the word into a set.

valid_prefixes = set(word[:size]
                     for word in possible_words for size in range(1, length(word))

With this set of valid prefixes, if our candidate word fragment is not a valid prefix, we can skip deeper searching of that branch:

    for direction in tile.directionals.values():
        if direction not in visited:
            candidate = word + direction.letter
            if candidate in valid_prefixes:
                helper(direction, candidate)

The tile.valid_directionals set

Almost forgot. visited is a list. If we switch this into a set, then we can use set arithmetic to get a set of valid_directionals that haven't been visited with valid_directionals - visited

def dfs(tile, word, min_word_length=2, max_word_length=5):
    visited = set()

    def helper(tile, word):
        if word in possible_words: 
            print(word)

        if len(word) < max_word_length:
            visited.add(tile)
            for direction in tile.valid_directionals - visited:
                candidate = word + direction.letter
                if candidate in valid_prefixes:
                    helper(direction, candidate)
            visited.remove(tile)

    helper(tile, word)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You’ve accepted the answer. Does this mean you’re not getting “exponentially longer times for larger boards”? Is your reset below 1 second? How have performance changed? \$\endgroup\$ – AJNeufeld Jan 17 at 5:18

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.