5
\$\begingroup\$

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
    for i,j in itertools.product(range(size[1]),range(size[0])):
        if grid[i][j] == ' ':
            grid[i][j] = letters[randint(0,len(letters)-1)]

    return grid, answers

def insertWord(word, grid, invalid=None):
    '''Insert a word into the letter grid

    'word' will be inserted into the 2D list grid.
    invalid is either None or a list of coordinates
    These coordinates are denote starting points that don't work.
    Returns an updated grid as well as a list of the added word's indices.'''

    height, width = len(grid), len(grid[0])
    length = len(word)

    #Detect whether the word can fit horizontally or vertically.
    hori = width >= length + 1  
    vert = height >= length + 1  
    if hori and vert:
        #If both can be true, flip a coin to decide which it will be
        hori = bool(randint(0,1))
        vert = not hori

    line = [] #For storing the letters' locations
    if invalid is None:
        invalid = [[None,None,True],[None,None,False]]

    #Height * width is an approximation of how many attempts we need
    for _ in range(height*width):
        if hori:
            x = randint(0,width-1-length)
            y = randint(0,height-1)
        else:
            x = randint(0,width-1)
            y = randint(0,height-1-length)
        if [y,x,hori] not in invalid:
            break
    else:
        # Probably painted into a corner, raise an error to retry.
        raise(RuntimeError)

    start = [y, x, hori] #Saved in case of invalid placement
    #Now attempt to insert each letter
    for letter in word:
        if grid[y][x] in (' ', letter):
            line.append([y,x])
            if hori:
                x += 1
            else:
                y += 1
        else:
            #We found a place the word can't fit
            #Mark the starting point as invalid
            invalid.append(start)
            return insertWord(word, grid, invalid)

    #Since it's a valid place, write to the grid and return
    for i,cell in enumerate(line):
        grid[cell[0]][cell[1]] = word[i]
    return grid, line

def printGrid(grid):
    '''Print the grid in a friendly format.'''

    width = len(grid[0])
    print ("+" + ('---+' * width))

    for i,line in enumerate(grid):
        print ("| " + " | ".join(line) + " |")
        print ("+" + ('---+' * width))

words = ["python", "itertools", "wordsearch","code","review","functions",
         "dimensional", "dictionary", "lacklustre"]
grid, answers = makeGrid(words, [14,8])
printGrid(grid)

I'm looking for general feedback. In particular about how to handle more awkward cases. As it stands I just brute force through generation. If you change the size to [14,7], you'll likely need to up the attempts parameter instead of relying on the default. This happens because it's a smaller board with a lot of long words that aren't necessarily chosen to intersect well.

\$\endgroup\$
1

2 Answers 2

4
\$\begingroup\$

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 with:

@classmethod
def attempt_grid(cls, words, size, n_attempts):
    '''
    Try `n_attempts` times to make a grid of the 
    given size with the given words. 

    Words are placed randomly one at a time, so
    it is possible that later words might not fit
    because of where earlier words were placed.
    This tries several times to place all the words,
    and returns the first grid that 'works'. 
    '''

You'll have to change your call to attemptGrid()tocls()` instead.

Unlike Dannno, I see no problem with you using the for-else construct. It seems perfectly appropriate here.

In the case that you couldn't get a good grid in the given number of attempts, you might want to just return None instead of re-raising the exception. An exception should signal that the function can't do what it claims to do - so something whose name says "I will try to do such-and-such" shouldn't use an exception (or print 'error') to say "well, I tried and failed, but maybe I could try harder if you want".


Lastly, there's a couple of minor improvements you can make to how the constructor (your attemptGrid) is implemented. When you're testing whether the words can at least theoretically all fit:

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

This is somewhere you should use an exception. You definitely shouldn't signal an error condition in non-UI code by just printing 'error' to stdout and then proceeding mostly as normal.

Also, you can use Python's max function to find which size is bigger, and you also only need to test against the longest word. So this can all become:

if max(len(word) for word in words) > max(size[0], size[1]):
    raise ArgumentError("Grid size is too small for the given words")

If you do choose to use a numpy array for the grid, you would initialise it in here like this:

self.grid = np.full(size, ' ', dtype='<U1')

And you can use argwhere again to detect the unfilled letters so that:

#Add other characters to fill the empty space
for i,j in itertools.product(range(size[1]),range(size[0])):
    if grid[i][j] == ' ':
        grid[i][j] = letters[randint(0,len(letters)-1)]

becomes:

for location in np.argwhere(self.grid == ' '):
    self.grid[location] = random.choice(letters)
\$\endgroup\$
0
3
\$\begingroup\$

PEP 8

A good* Python application will usually* conform to PEP 8, the most commonly usedcitation needed coding standards in the Python ecosystem.

Naming

Function names and variables should be named using snake_casing, classes with PascalCasing, and constants with UPPER_SNAKE_CASING. Thus, letters should be named LETTERS and makeGrid should be named make_grid

Parenthesis

Don't use parens where they aren't needed. For example,

sizeCap = (size[0] if size[0] >= size[1] else size[1])

can lose the parenthesis.

Spaces

You should be separating operators such as ,, *, +, etc from their arguments with spaces - thus

for i,j in itertools.product(range(size[1]),range(size[0]))

becomes

for i, j in itertools.product(range(size[1]), range(size[0]))

and so on.

Python 3 compatibility (print() function)

It's generally a good idea to try and make your code as easily portable to Python 3 as possible - in your case this will primarily mean adding the line

from __future__ import print_function

at the top of your file, and then changing all of your print statements to print() functions.

Additionally, you should be using xrange instead of range to avoid creating intermediate lists. This does change from Python 2 to 3 (range acts like xrange in Python 3 and xrange disappears). I'd recommend either making another file called compatibility.py with everything you need to make it compatible, otherwise doing something like this at the top of your file

try:
    range = xrange
except NameError:
    range = range

Minor code improvements

Couple places where your code can be improved.

letters = "qwertyuiopasdfghjklzxcvbnm"

can be

import string
letters = string.ascii_lowercase

or just omit the letters variable entirely and substitute string.ascii_lowercase as needed.

sizeCap = (size[0] if size[0] >= size[1] else size[1])
sizeCap -= 1

can just be

sizeCap = (size[0] if size[0] >= size[1] else size[1]) - 1

in which case you do need the parenthesis.

The line

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

could be rewritten as

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

There is no need to use itertools to look at each element in the grid. Just do

for row, col in enumerate(grid):
    for index, element in enumerate(col):
        if element == ' ':
            grid[row][index] = random.choice(string.ascii_lowercase)

Whether or not that is better is debatable, but I would say it is easier to read.

You don't need to pick a random integer

grid[i][j] = letters[randint(0,len(letters)-1)]

is easier to do

grid[i][j] = random.choice(letters)

The last of my small changes would be to not return a grid from insertWord - because lists are a mutable type any changes you make to it inside of the function will be there outside of the function as well.

More substantial code changes

Don't use exceptions to structure code flow

This smells bad to me

try:
    return attemptGrid(words, size)
except RuntimeError as e:
    pass

I'd much rather do something like

# Assume some enum-like class has been defined that has the appropriate return codes
grid = attemptGrid(words, size)
if grid != ReturnCodes.INVALID_BOARD:
    return grid

Try to avoid the for-else construct

This is one of the more confusing language constructs in Python. I would much rather see some sort of "success" variable that is set if everything works, manually break from the loop, and then return if the "success" variable has been set to True.

success = False

for _ in range(attempts):
    grid = attemptGrid(words, size)
    if grid != ReturnCodes.INVALID_BOARD:
       success = True
       break
    else:
       success = False

if success:
   return grid
raise SomeExceptionType("A valid board couldn't be created") 

Algorithm improvements

I don't have any fantastic ideas off the top of my head for how to improve your algorithm. I'd say you probably want to figure out potential intersections first, and then try to space things by that.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ grid = [[' '] * size[0]] * size[1] is generally a bad idea, because lists are mutable. You don't get size[1] distinct lists, you get size[1] copies of the same list. I would do grid = [[' ']*size[0] for _ in xrange(size[1])] \$\endgroup\$ Jul 28, 2015 at 2:40
  • \$\begingroup\$ @NightShadeQueen ooh, that's a really good point that I completely overlooked. Edited. \$\endgroup\$ Jul 28, 2015 at 3:07
  • \$\begingroup\$ Thanks for the detailed answer. Is the issue with controlling flow by exceptions mostly that the exceptions might occur for other reasons than I expect (even if they're of the same type) or are there other problematic aspects I'm not thinking of? \$\endgroup\$ Jul 31, 2015 at 9:58
  • 1
    \$\begingroup\$ @SuperBiasedMan it's not so much an issue of other reasons (although that is a possibility) - it's more that we already have ways to control program flow. Exceptions should be used for truly exceptional circumstances - something happened that can't be easily recovered from. In this case, you don't need an exception to signal that making a grid failed - you can return a value that indicates that, and then act based on the return value. \$\endgroup\$ Jul 31, 2015 at 13:32
  • 1
    \$\begingroup\$ @SuperBiasedMan sorry I was just looking at this again, and thought I should make one more point. There are occasionally times where you do want to control program flow based on whether or not something raises an exception - when that is the case I strongly prefer writing some function raises so I can do if raises(my_function, exception_type, arguments): do_something(). If anything you'd want to do in the exceptional circumstance can't be handled by that function, you probably need to restructure your code or handle the error more explicitly. \$\endgroup\$ Aug 4, 2015 at 16:43

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.