Wordsearch Generator

For fun I decided to make an algorithm in Python that would create a 2D list of a specified size that it can populate with a list of words and fill the gaps with random characters. It's basically a wordsearch.

You supply it with the words, optionally a size and then a count of how many times to retry when invalid boards are generated. It returns both the 2D list of letters, but also a dictionary with the word list as keys and the values are lists containing co-ordinates for each character in the word, such as:

{'python': [[1,4],[2,4],[3,4],[4,4],[5,4],[6,4]]}

Here's the full script:

```
import itertools

from copy import deepcopy
from random import randint

letters = "qwertyuiopasdfghjklzxcvbnm"

def makeGrid(words, size=[10,10], attempts=10):
'''Run attemptGrid trying attempts number of times.

Size contains the height and width of the board.
Word is a list of words it should contain.'''

for _ in range(attempts):
try:
return attemptGrid(words, size)
except RuntimeError as e:
pass
else:
print "ERROR - Couldn't create valid board"
raise e

def attemptGrid(words, size):
'''Attempt a grid of letters to be a wordsearch

Size contains the height and width of the board.
Word is a list of words it should contain.
Returns the 2D list grid and a dictionary of the words as keys and
lists of their co-ordinates as values.'''

#Make sure that the board is bigger than even the biggest word
sizeCap = (size[0] if size[0] >= size[1] else size[1])
sizeCap -= 1
if any(len(word) > sizeCap for word in words):
print "ERROR: Too small a grid for supplied words."
return

grid = [[' ' for _ in range(size[0])] for __ in range(size[1])]

#Insert answers and store their locations
answers = {}
for word in words:
grid, answer = insertWord(word,grid)
answers[word] = answer

#Add other characters to fill the empty space

Big picture: Won't somebody please think of the childrenclients!

The data structure you're creating here isn't ideal for how client code will likely want to use it. When a user makes a guess, the application will want to check whether the string they've highlighted (identified probably by either a start and end position, or a start position, direction and length) matches any of the words. The best way to do that with a grid is to extract that guess (as a string), check if it's a key in the answers dictionary, and then make sure that the starting point from that dict matches.

This is the number one most common thing that anyone will want to do. And it's a little awkward - especially the 'extracting the string' part, given a list of lists of length 1 strings. But it will work the same every time, for every client. So let's give them a prebuilt function to do it. While we're at it, we now have a moderately complex data structure (a tuple and some nested lists), a routine to create them and a few routines to do something with them (although insertWord is probably uninteresting to clients) - that's a good indication that what you want is a class.

class WordGrid:
    def __init__(self, words, size):
        # Does what your attemptGrid does
        # but put grid and answers as attributes on
        # self instead of returning them
        # More detailed comments on the current
        # attemptGrid code are toward the bottom of the post

    def word_at(x, y, length, orient):
        '''
        Return the word hidden at the given position, or
        `None` if there is no word hidden there.
        '''

    def _insert_word(self, word):
        # Your insertWord function

    def __str__(self):
        # Like your `printGrid`, but build and return
        # a string instead of printing it.
        # Reserve printing for UI code. Problem domain code
        # should avoid doing IO.

etc.

This means a client's "user has made a guess" routine looks like this:

word = grid.word_at(...)
if word is not None:
    # cross the word off the list

Inserting a word

The way you are inserting a word can be a little better. Instead of storing a list of invalid positions, store a matrix of flags representing the validity of each position. That way, instead of estimating how many attempts you would need to find a valid position, you can tell when all possible valid positions have been exhausted.

Numpy is quite good for this (and you may want to use it for the grid of characters as well). The easiest way to decide the next candidate location is to do a random.choice of all the valid locations, which you can enumerate quite easily with np.argwhere.

Use a 3D boolean array - the first two dimensions match the grid, the last one is for orientation. You could also use two separate arrays, of course, but this is more flexible if you later decide to allow diagonal or backwards words.

It will look like this:

def _insert_word(self, word, allow_vertical, allow_horizontal):
    valid = np.dstack((np.ones_like(self.grid, dtype=bool)*directions)
    if not allow_horizontal or valid.shape[0] < len(word):
        valid[..., 0] = False
    if not allow_vertical or valid.shape[1] < len(word):
        valid[..., 1] = False

    while True:
        try:
            x0, y0, orient = random.choice(np.argwhere(valid))
        except IndexError as e:
            # No more valid positions
            raise RuntimeError("Failed to create valid grid") from e

        if orient:
            coords = zip([x0]*len(word), range(y0,y+len(word))
        else:
            coords = zip(range(x0, x+len(word)), [y0]*len(word))

        for (x,y),c in zip(coords, word):
            if self.grid[x, y] not in (' ', c):
                valid[x0, y0, orient] = False
                continue
            self.grid[x, y] = c

        return (x0, y0, orient)

Note that I pre-calculate the coordinates that we attempt to put letters at; this lets you use lock-step iteration with zip instead of updating the position inside the loop body. I also just return the location of the word (matching the details of how to locate it with what word_at expects), since any code calling this has access to the grid anyway.

If you don't a numpy array for the grid, you will need to change the indexing to [x][y].

attemptGrid / __init__ and makeGrid

The names attemptGrid and makeGrid are almost exactly backwards for what those functions do. attemptGrid does the actual work of creating the grid and inserting the words, and raises an exception if it can't; makeGrid makes a certain number of attempts at doing that successfully. But with my prior suggesting of making this a class, attemptGrid is now __init__, which means makeGrid should be an alternate constructor (usually a classmethod), and the name attemptGrid is free to use. Except I'll PEP8ify it to attempt_grid and explicitly document why it's even a thing to start

StackExchange Code Review Q#98247, answer score: 4