8
\$\begingroup\$

I wrote a word-search solver in Python3. It takes input from a file named input.txt and takes the word as a command-line argument. It is intended to be run as a script, so I didn't really bother with code reusability / extendability.

It assumes that input.txt contains the word search file looking something like this:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y

It ignores all non-letter characters and assumes each line contains the same amount of letters (which might not be good).

Here is the code:

#### A word search solver.

class OkayImDoneNowBreakEverything(Exception):
    ## Python doesn't support tagged breaks, so I raise an exception instead
    pass

from string import ascii_letters as letters
import sys
word = sys.argv[1]

### Read the letters.
with open("input.txt") as f:
    grid = []
    for line in f:
        row = []
        for c in line.rstrip("\n"):
            if c in letters:
                row.append(c.upper())
        grid.append(row)

first = word[0]
directions = [
    (1, 0),
    (1, 1),
    (0, 1),
    (-1, 1),
    (-1, 0),
    (-1, -1),
    (0, -1),
    (1, -1)
]
names = [
    ["up and to the left", "up", "up and to the right"],
    ["left", "IF YOU SEE THIS SOMETHING BROKE", "right"],
    ["down and to the left", "down", "down and to the right"]
]

### Go through the grid and scan for the correct words.
try:
    for i, line in enumerate(grid):
        for j, _ in enumerate(line):
            ## try every direction, checking if any of them work
            for yd, xd in directions:
                y = i
                x = j
                try:
                    for c in word:
                        if c != grid[y][x]:
                            break
                        y += yd
                        x += xd
                        if x < 0 or y < 0:
                            ## if either of these numbers are negative,
                            ## they would loop back around to the end of
                            ## the list, which we don't want
                            raise IndexError()
                    else: # the for loop didn't break, which means we found a match
                        raise OkayImDoneNowBreakEverything()
                except IndexError:
                    ## if this happened, we didn't find the word, so we
                    ## can just try another direction
                    pass
    else: # the loop didn't break, which means we didn't find a match
        print("Didn't find a match.")
except OkayImDoneNowBreakEverything:
    print("Found a match at line {0}, column {1} going {2}".format(i+1,
                                                                   j+1,
                                                                   names[yd+1][xd+1]))

Are there any ways I could make this faster or more idiomatic?

\$\endgroup\$
  • \$\begingroup\$ Your word-search solver is looking only for one occurrence of the given word. I'd name it one-word-search.. \$\endgroup\$ – Grajdeanu Alex. Feb 24 '17 at 11:04
10
\$\begingroup\$

Program structure

At first glance, I would say that your main problem is excessively deep indentation, due to nested for loops and try blocks.

One consequence is the humorously awkward OkayImDoneNowBreakEverything exception. Why doesn't Python support tagged breaks? Because the language is designed to encourage you to write good code, and usually you would be better off returning from a function. In fact, your code would be much improved with functions:

  • Your program would be more readable it were divided into self-contained chunks, each having parameters, only local effects, and obvious outputs. As an illustration of readability, just look at the main() function I wrote below: you can see what the program does at a glance.
  • Your comments could be docstrings.
  • You could reuse the code. For example, what if you want to read the file once and search for multiple words within it?

In addition, you can avoid nesting the loops for i, j, and directions by using itertools.product().

Furthermore, you can eliminate the use of exceptions altogether. You could avoid encountering IndexError by doing a bounds check. That would also be more efficient, since you can arithmetically predict whether walking in some direction will end up out of bounds before you even encounter the edge.

Additional remarks

Reading the grid could be done more simply. Whenever you start with an empty list, then append to it in a loop, consider using a list comprehension instead to define the result "all at once". In your code, there is no need to .rstrip("\n"), since you are will ignore any non-letters anyway. Personally, I'd use re.findall('[A-Z]', …) to extract the letters.

Avoid having parallel data structures for directions and names. I'd create one unified list, using namedtuple to help.

Suggested solution

"""A word search solver"""

from collections import namedtuple
from itertools import product
import re
import sys

Direction = namedtuple('Direction', 'di dj name')

DIRECTIONS = [
    Direction(-1, -1, "up and to the left"),
    Direction(-1,  0, "up"),
    Direction(-1, +1, "up and to the right"),
    Direction( 0, -1, "left"),
    Direction( 0, +1, "right"),
    Direction(+1, -1, "down and to the left"),
    Direction(+1,  0, "down"),
    Direction(+1, +1, "down and to the right"),
]

def read_grid(filename):
    """
    Read a word search puzzle from a file into a 2D matrix of uppercase letters.
    """
    with open(filename) as f:
        return [re.findall('[A-Z]', line.upper()) for line in f]

def extract(grid, i, j, dir, length):
    """
    Extract letters from the grid, starting at row i column j, as a string.
    If the extraction will walk out of bounds, return None.
    """
    if ( 0 <= i + (length - 1) * dir.di < len(grid) and
         0 <= j + (length - 1) * dir.dj < len(grid[i]) ):
        return ''.join(
            grid[i + n * dir.di][j + n * dir.dj] for n in range(length)
        )
    return None

def search(grid, word):
    """
    Search for a word in a grid, returning a tuple of the starting row,
    starting column, and direction.  If the word is not found, return None.
    """
    word_len = len(word)
    for i, j, dir in product(range(len(grid)), range(len(grid[0])), DIRECTIONS):
        if word == extract(grid, i, j, dir, word_len):
            return i, j, dir
    return None

def main(filename, word):
    grid = read_grid(filename)
    match = search(grid, word.upper())
    if match is None:
        print("Didn't find a match.")
    else:
        i, j, dir = match
        print("Found a match at line {0}, column {1} going {2}".format(
                i + 1, j + 1, dir.name))

if __name__ == '__main__':
    main('input.txt', sys.argv[1])
\$\endgroup\$

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.