2
\$\begingroup\$

I have implemented an exhaustive depth-first grid search that searches for all possible words in the 8 connected regions. Is there any way I can make this faster or memory efficient than it is now?

I feel like passing a copy of the seen set in dfs(xx, yy, seen.copy(), word + grid[x][y]) is an overhead that can possibly be avoided.

Or is my algorithm completely wrong and I should use something else?

This is not a code site challenge, I am just trying to implement this out of curiosity.

My first question on code review so let me know if there is something that I can add to make this better.

Also can this be made more "pythonic"?

def possible_directions(x, y):
    """
    Returns at most 8 connected co-ordinates for given `x` and `y`
    """
    for xx in range(-1, 2):
        for yy in range(-1, 2):
            if not xx and not yy:
                continue
            if 0 <= x + xx < len(grid) and 0 <= y + yy < len(grid[x]):
                yield x + xx, y + yy

def dfs(x, y, seen, word = ''):
    """
    Recursive Generator that performs a dfs on the word grid
    seen = set of seen co-ordinates, set of tuples
    word = word to yield at each recursive call
    """
    if (x, y) in seen:
        return
    yield word + grid[x][y]
    seen.add((x, y))
    for xx, yy in possible_directions(x, y):
        yield from dfs(xx, yy, seen.copy(), word + grid[x][y])



grid = [['c', 'f', 'u', 'c'], ['e', 'a', 't', 'e'], ['b', 'h', 'p', 'y'], ['o', 'n', 'e', 'p']] # word grid, can be any size, n x n

for x in range(len(grid)):
    for y in range(len(grid[x])):
        for i in dfs(x, y, set()):
            print(i)
\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

It is not necessary to make a copy of seen when making a recursive call. Change seen before the recursive calls and then undo the change afterward.

def dfs(x, y, seen, word = ''):
    """
    Recursive Generator that performs a dfs on the word grid
    seen = set of seen co-ordinates, set of tuples
    word = word to yield at each recursive call
    """
    if (x, y) in seen:
        return
    yield word + grid[x][y]
    seen.add((x, y))
    for xx, yy in possible_directions(x, y):
        yield from dfs(xx, yy, seen, word + grid[x][y])
    seen.remove((x,y))

I wonder if it would be more efficient to take advantage of the symmetry of the square letter grid. If dfs() yielded lists of x,y tuples, you would only need to do dfs searches starting from (0,0), (0,1), and (1,1). Solutions for all the other starting points would be rotations or reflections.

\$\endgroup\$
1
  • \$\begingroup\$ thanks for that, that seems like a simple yet effective change, I am accepting this as an answer but the answer by @ruds explains a bit more and hence I have awarded the bounty to them, apologies :) \$\endgroup\$ Jan 17, 2021 at 17:10
4
+50
\$\begingroup\$

This is fairly tight; I don't think there's much more performance to pull out without dropping into C. That said:

possible_directions

First, I would rename this to neighbors or successors; it's not really about direction but about the nodes in the graph that come next or are adjacent to your current node.

Second, you can reduce the number of branches and arithmetic operations a little:

for xx in range(max(0, x - 1), min(x + 1, len(grid)):
    for yy in range(max(0, y - 1), min(y + 1, len(grid[x])):
        if xx == x and yy = y: continue
        yield xx, yy

Third, you can prevent many no-op calls of dfs by doing your seen check in this function rather than in the dfs base case. That is, pass seen to this function and modify your yield line to something like

if (xx, yy) not in seen: yield xx, yy

dfs

You compute word + grid[x][y] many times (once + once per neighbor). You should memoize this before yielding it (Python may already perform this optimization for you but I doubt it).

I don't think a set of tuples is the best implementation for seen. You can't really avoid the copy of seen that I can see, and the lookups are not as fast as they could be. You already implicitly require that every row is the same length (0 <= y + yy < len(grid[x]), not 0 <= y + yy < len(grid[x + xx])) and that seems like a sensible restriction in any case. I suggest a bit array of some sort (e.g. bitarray, which I've never used but seems to fit the bill), which will allow fast setting, checking, and copying of seen (instead of seen[x][y], check and set seen[y * len(grid) + x]).

Best practice here would probably be to have a wrapper function that does not take a seen or word argument, but initializes them for a call to your recursive helper, something like

def dfs(x, y):
    return dfs_recursive(x, y, set(), '')
\$\endgroup\$
3
  • \$\begingroup\$ thank you for the response, appreciate the suggestion, if I dont get any other answers that are better than yours I will grant the bounty to you (12 hours until it lets me to) \$\endgroup\$ Jan 16, 2021 at 14:19
  • \$\begingroup\$ I am giving you the bounty since you gave a detailed breakdown of my code and also introduced me to bitarray but apologies for accepting a different answer as that explains a detail you missed with the seen set \$\endgroup\$ Jan 17, 2021 at 17:08
  • 1
    \$\begingroup\$ Thanks @python_user - I also upvoted the answer you accepted because they noticed the way to avoid copying seen. \$\endgroup\$
    – ruds
    Jan 17, 2021 at 17:20
3
\$\begingroup\$
  • Pre-compute your offset tuples for possible_directions
  • Use type hints
  • Use strings instead of character lists for immutable data

Those aside, you should really consider avoiding printing every single line of output if possible. The printing alone, at this scale, will have a time impact.

Suggested:

from typing import Set, Tuple, Iterable

Coords = Tuple[int, int]

OFFSETS: Tuple[Coords] = tuple(
    (xx, yy)
    for xx in range(-1, 2)
    for yy in range(-1, 2)
    if xx != 0 or yy != 0
)


def possible_directions(x: int, y: int) -> Iterable[Coords]:
    """
    Returns at most 8 connected co-ordinates for given `x` and `y`
    """
    for xx, yy in OFFSETS:
        if 0 <= x + xx < len(grid) and 0 <= y + yy < len(grid[x]):
            yield x + xx, y + yy


def dfs(x: int, y: int, seen: Set[Coords], word: str = ''):
    """
    Recursive Generator that performs a dfs on the word grid
    seen = set of seen co-ordinates, set of tuples
    word = word to yield at each recursive call
    """
    if (x, y) in seen:
        return
    yield word + grid[x][y]
    seen.add((x, y))
    for xx, yy in possible_directions(x, y):
        yield from dfs(xx, yy, seen.copy(), word + grid[x][y])


grid = (
    'cfuc',
    'eate',
    'bhpy',
    'onep'
)  # word grid, can be any size, n x n
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I really appreciate your suggestions regarding type hints and precomputing offsets :D \$\endgroup\$ Jan 17, 2021 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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