# Word Search Generator

Last night I thought a word search would be fairly interesting to try. I'm not sure how proper ones run, but my one kind of works through the brute force method, where it'll place a letter in one spot (the first letter of a random word), and branch out in all directions while narrowing down the list of matching words until it finds a match (although if there's remaining words, there's a chance it'll continue as to not end up with all the shortest words).
Each attempt is an iteration, so obviously the more iterations, the more chance the grid will be filled with words.

It'll also generate similar words based on the words added to the search, to throw the user off a little (eg. testing could also generate tesing, temtin, test, stin etc).

Instead of storing the values in a 2d grid, I stored them in a list, and used a separate function to calculate the next index when given an index and direction, and it checks that it's still on the grid and not gone off the side.

Examples (with using a list with all the english words):

14x14 output with 10 iterations:
w x w r r m j b v y x c k c
b h y d y s e e a i i z o s
o a n a l n t x s e j y c a
o r a t i o n a l s a a l f
b g u u n c o m b i n e d y
r z w e f e n n t e i x c z
t q r c r f s l n l k a m g
x u u f q s f w a c e i l o
v a z s o z w h r n o c w v
p l e l k t z v i r o e w j
i l c n f q r w a a v o k u
h s e i b l y u h r r c l u
a h k i t p b x o o w r r u
w x n t g f n g m j h s w e
Words: celt, mohair, rationals, ruers, uncombined

Solutions:
rationals: (1, 3) right
celt: (11, 8) left-up
mohair: (8, 13) up
ruers: (1, 3) down-right
uncombined: (3, 4) right

14x14 output with 20 iterations (in debug mode to remove extra letters):
n
w   e s               s
a     p n       y m y t s
l     m     r         i
u         o     c
c l o v e s     b k       h
e y     l e       c
n   l   e           a
i     i s             e
p       k               t
l     d u s t   e
u               r
b
Words: bulkily, cloves, dust, enrobe, lawn, lumps, pines, reteach, stickles, stymy

Same as above but with difficulty 1 instead of 5:

b
e   m
r   e
g   d
a
a w f u l             l   g
p             i     y
s   d i a g   n     v
y   f         s     e
c   i         u i   o
h   n         l n   z
e   k         t k   o
e y   n
r     e
Words: awful, berg, diag, fink, gyve, inky, insulter, medal, ozone, psyche

14x14 output with 200 iterations (also in debug mode):
m i x t   e f i w         n
l i p s   s y o t s m   r g
y i d       m   a   b o   g
m   l y     e   o   b a n e
a   o t l e w   m e   i c y
s   s m i u r e u h   a
n n d b n n g r i     l
e   u   e o g a   n a   h e
r     n k d m s k u n g s
u   e w s i   k l     t a
s   s a t e d e   a   e r s
n l y   r k d     p m t p
e a d o s i a i p o y m
t o o f     r e k a m c   a
Words: ados, amps, amyl, cabs, chink, comet, dens, else, embodier, fens, foot, idyl, image, kike, kung, lilts, lips, maker, mewing, mixt, moat, mony, myopia, pals, raga, reborn, ruin, sated, sure, toys, trash, tsked, unasked, unsold, wife, yale, yawn, yegg


Feedback on the style of writing and documentation would be useful since I'm still trying to improve, plus if you notice anything I've done really badly let me know. The last thing I did apparently had too many comments so I tried to keep them to only the basic ones this time round.

import random
class WordSearch(object):
"""Generate a word search using any input strings.

#Set up class
grid_x = 10
grid_y = 10
ws = WordSearch(grid_x, grid_y)

#Set difficulty
ws.difficulty(5)

#Get the input
f = 'C:/words.txt'
if f:
input_words = ws.format_input_list(filename=f)
else:
input_words = ws.format_input_list(['example', 'word'])

#Generate the grid
iterations = 20
ws.generate(iterations, words=input_words)

#Display the grid
ws.display()

#Display the solutions
ws.solutions()
"""

def __init__(self, x=0, y=0, **kwargs):
"""Set up the WordSearch class.

Parameters:
x:
The width of the grid.

y:
The height of the grid.

kwargs:
'difficulty':
Default: 5
Set the difficulty level.
See WordSearch().get_difficulty() for what each level contains.
"""

self.x = x
self.y = y
self.grid_ids = range(self.x*self.y)
self.grid = ['' for i in self.grid_ids]
self.difficulty_level = kwargs.get('difficulty', 5)

def difficulty(self, level):
"""Update the difficulty level."""
self.difficulty_level = level

def get_difficulty(self):
"""Generate rules for the difficulty level.

Levels:
0: Right
1: Right, down
2: Right, down, with right-down dragonal
3: Right, down, up, with right diagonals
4: All directions, with right diagonals
5: All directions, with all diagonals
"""
grid_directions = 
if self.difficulty_level > 0:
grid_directions.append(2)
if self.difficulty_level > 1:
grid_directions.append(1)
if self.difficulty_level > 2:
grid_directions += [6, 7]
if self.difficulty_level > 3:
grid_directions.append(4)
if self.difficulty_level > 4:
grid_directions += [3, 5]
return grid_directions

def direction_coordinate(self, inital_location, direction):
"""Calculate the new coordinate ID based on a direction.
For visual feedback of this in action, use WordSearch().debug_grid().

Returns None if out of range, otherwise return the new coordinate ID.

Parameters:
initial_location:
The coordinate ID to work from.

direction:
Which direction to look.

0 = right
1 = diagonal right-down
2 = down
3 = diagonal left-down
4 = left
5 = diagonal left-up
6 = up
7 = diagonal right-up

>>> WordSearch(10, 10).direction_coordinate(57, 6)
47
>>> WordSearch(5, 10).direction_coordinate(57, 6)
>>> WordSearch(5, 10).direction_coordinate(47, 6)
42
"""
directions = {}
directions['right'] = 1
directions['down'] = self.x
directions['left'] = -directions['right']
directions['up'] = -directions['down']

direction_move = (directions['right'],
directions['right']+directions['down'],
directions['down'],
directions['left']+directions['down'],
directions['left'],
directions['left']+directions['up'],
directions['up'],
directions['right']+directions['up'])

old_coordinate = self.get_coordinate(inital_location)
new_location = inital_location+direction_move[direction]
new_coordinate = self.get_coordinate(new_location)

if old_coordinate and new_coordinate:
if all(new_coordinate[i] in (old_coordinate[i]+j for j in xrange(-1, 2)) for i in xrange(2)) and 0 < new_location < self.x*self.y:
return new_location

def format_input_list(self, word_list=None, word_length_min=3, word_length_max=None, **kwargs):
"""Take a list of words and remove any words too long or short."""
if word_length_max is None:
word_length_max = (min(self.x, self.y) + (self.x+self.y)/2)/2

if kwargs.get('filename', None):
with open('C:/Code/wordsEn.txt') as f:

return [i for i in word_list if word_length_min < len(i) <= word_length_max]

def word_variations(self, words, min_length=1):
"""Take the list of used words and cut them up a little, so the user will find similar combinations
of letters in the word search that don't amount to the full word.

It could ideally do with improvement, the idea currently is quite basic.

Parameters:
min_length:
Minimum amount of results to generate.
It will iterate through all words multiple times until the resulting output is longer than this.

>>> random.seed(1234)

>>> ws.word_variations(['testing', 'word'], 10)
['etint', 'er', 'estd', 'tstd', 'rsti', 'isti', 'oi', 'teoin', 'teown', 'tesn', 'test', 'wod']
>>> ws.word_variations(['testing', 'word'], 5)
['twsig', 'wwrd', 'wwod', 'en', 'ein']
"""
all_letters = ''.join(words)
word_list = []
while len(word_list) < min_length:

for word in words:
original_word = word
word_len = len(word)
word_range = xrange(word_len)

for repeat in xrange(random.randint(0, 4)):

#Remove random letters from the word - word = wrd, wod, etc
remove_letters = random.sample(word_range, random.randint(0, word_len/3))
num_removed_letters = 0
for index in remove_letters:
word = word[:index-num_removed_letters]+word[index+1-num_removed_letters:]
num_removed_letters += 1

#Replace random letters in word - word = ward, wore, wond, etc
word_section = sorted(random.sample(word_range, 2))
if word_section or word_section != word_len:

new_word = word[random.randint(0, word_section):random.randint(word_section, word_len)]
new_word_len = len(new_word)

for replacement in xrange(random.randint(0, new_word_len/2)):
replacement_index = random.randint(0, new_word_len-1)
new_letter = random.choice(all_letters)

new_word = new_word[:replacement_index]+new_letter+new_word[replacement_index+1:]

#Only add to list if
if new_word != original_word:
word_list.append(new_word)
return word_list

def debug_grid(self):
"""Output a grid showing the related ID of each cell.

>>> WordSearch(4, 4).debug_grid()
00 01 02 03
04 05 06 07
08 09 10 11
12 13 14 15

>>> WordSearch(12, 3).debug_grid()
00 01 02 03 04 05 06 07 08 09 10 11
12 13 14 15 16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31 32 33 34 35
"""
count = 0
max_len = len(str(self.x*self.y-1))
for i in range(self.y):
print ' '.join(str(i+count).zfill(max_len) for i in range(self.x))
count += self.x

def get_coordinate(self, id=0, **kwargs):
"""Convert an ID into its coordinate.
Only needs the X grid value to calculate, the Y value checks it is within range.

Parameters:
id:
Coordinate ID of the cell.

kwargs:
ignore:
Default: False
If the maximum Y value should be ignored when checking if the number is in range.
Set to True and it can return a coordinate that doesn't exist in the grid.

>>> WordSearch(10, 10).get_coordinate(57)
(7, 5)
>>> WordSearch(5, 10).get_coordinate(57)
>>> WordSearch(5, 10).get_coordinate(57, ignore=True)
(2, 11)
>>> WordSearch(23, 10).get_coordinate(57)
(11, 2)
>>> WordSearch(23, 64).get_coordinate(57)
(11, 2)
"""
ignore_limit = kwargs.get('ignore', False)

location_x = id%self.x
location_y = id/self.x
if location_y <= self.y or ignore_limit:
return (id%self.x, id/self.x)

@staticmethod
def direction_to_text(direction):
"""Convert a direction number to text."""
return ('right', 'down-right', 'down', 'down-left', 'left', 'left-up', 'up', 'right-up')[direction]

def generate(self, num_iterations, second_pass=True, fill_empty_values=True, **kwargs):
"""Generate data for the word search. The second pass simply means a second loop that will fill the
grid with similar segments of words similar to the words already there.

This function works by selecting a starting point, assigning a random first letter from the word list,
and then branching out in all directions to find a matching word. Since the first matching word is
always the smallest, there is a chance to skip this depending on how many existing words there are, to
give larger words a chance to appear. The results get narrowed down for each further step in the direction,
where if there is an existing character, it will remove all non matching results.
After a successful attempt, the word is written into the grid and stored in the used_words dictionary with
some extra information on locating it.

For debug purposes, set second_pass and fill_empty_values to False.

Parameters:
num_iterations:
Maximum iterations to run on generating words.
Each iteration relates to an attempt, so does not guarentee the same amount of output words.
Larger grids will make use of more iterations, but they will also take a lot longer to generate.

second_pass:
If the code should run an additional pass using similar words that have been generated.
fill_empty_values:
If the code should fill all remaining values with random characters.

"""
capitalise_non_matches = False
input_words = kwargs.get('words')
grid_directions = self.get_difficulty()
self.used_words = {}

for stage in xrange(1+second_pass):

#Detect which word list to use depending on the pass
if stage and self.used_words:
word_list = self.word_variations(self.used_words.keys(), num_iterations)
else:
word_list = input_words

for i in range(num_iterations):

#Cancel loop when out of words
if not word_list and not stage:
break

random.shuffle(grid_directions)

initial_word_list = []

#Build list of matching words
if word_list:
while not initial_word_list:

#Pick a coordinate, and fill with letter if empty
current_coordinate = random.choice(self.grid_ids)
using_new_letter = False
if not self.grid[current_coordinate]:
self.grid[current_coordinate] = random.choice(word_list)
using_new_letter = True
if capitalise_non_matches and stage:
self.grid[current_coordinate] = self.grid[current_coordinate].upper()

#Create a selection of words
initial_word_list = [word for word in word_list if self.grid[current_coordinate] in word]
initial_word_list = random.sample(initial_word_list, min(len(initial_word_list), num_iterations))

else:
initial_word_list = []

valid_word = None

if initial_word_list:
for direction_index in xrange(len(grid_directions)):

direction = grid_directions[direction_index]

next_direction = current_coordinate
matching_word_list = initial_word_list
random.shuffle(matching_word_list)

#Loop while there are matching words
count = 0
while matching_word_list:

#Cancel if invalid direction
if next_direction is None:
matching_word_list = []
break

#Loop for each word
invalid_word_index = []
delete_count = 0
for i in xrange(len(matching_word_list)):

i -= delete_count

#Add to invalid words if the letter doesn't match
if self.grid[next_direction] and self.grid[next_direction] != matching_word_list[i][count]:
del matching_word_list[i]
delete_count += 1

if not matching_word_list:
break

#If reached the length of a word, it's succeeded
elif count >= len(matching_word_list[i])-1:

#Choose whether to stop here or continue for a longer word
if random.uniform(0, 1) < max(0.25, 1.0/(max(1, len(matching_word_list)/2))) or count > (self.x+self.y)/random.choice(xrange(2,5)):
valid_word = matching_word_list[i]
matching_word_list = []
break
else:
del matching_word_list[i]
delete_count += 1

next_direction = self.direction_coordinate(next_direction, direction)
count += 1

#Update the grid data
if valid_word is not None:

used_word = word_list.pop(word_list.index(valid_word))
if not stage:
self.used_words[used_word] = (current_coordinate, direction)

next_direction = current_coordinate
for i in range(1, len(valid_word)):

letter = valid_word[i]
next_direction = self.direction_coordinate(next_direction, direction)
if not self.grid[next_direction]:
if stage and capitalise_non_matches:
letter = letter.upper()
self.grid[next_direction] = letter

#If the data doesn't match the word, this shouldn't happen
elif self.grid[next_direction] != letter:
self.grid[next_direction] = '-'

break

#Remove single remaining letters if the word was not completed
elif len(grid_directions)-1 == direction_index:
if using_new_letter:
self.grid[current_coordinate] = ''

#Fill with random letters
alphabet = 'abcdefghijklmnopqrstuvwxyz'
if capitalise_non_matches:
alphabet = alphabet.upper()
if fill_empty_values:
for i in xrange(len(self.grid)):
if not self.grid[i]:
self.grid[i] = random.choice(alphabet)

def display(self):
"""Print the word search with its current values."

Example Output:
h y i j u n g h w g m c f c
n a a b v t z r r u n q u r
e g n i n i g n e o t k l t
r q a d e k c q a s w c i e
m g t w k w w s l t d f t s
s k g z k y a w t y w s t o
d f m p q l n d o w e r y m
e c e w e x t d r s g e d r
i m u s f u m r s n t h t a
d i l h p w r a d c b w y m
p i m f n b v f e d a m n u
n y k y c n o h v e k j z o
d v c z a w j w f j n d t s
c l h c c w f r i z z e r y
Words: canvasses, engining, frizzer, gawk, marmoset, nils, realtor, unmade
"""
count = 0
for i in xrange(self.y):
current_row = []
for j in xrange(self.x):
letter = self.grid[count]
if not letter:
letter = ' '
current_row.append(letter)
count += 1
print ' '.join(current_row)
print 'Words: '+', '.join(sorted(self.used_words.keys()))

def solutions(self):
"""Print the solutions (location and direction) to the generated words.

Example Output:
realtor: (8, 1) down
gawk: (1, 2) down-right
marmoset: (13, 9) up
canvasses: (3, 13) right-up
nils: (0, 11) right-up
frizzer: (6, 13) right
unmade: (13, 10) left
engining: (8, 2) left
"""
words = self.used_words
for word in words:
print '{}:'.format(word), self.get_coordinate(words[word]), self.direction_to_text(words[word])


Since I'm just printing the grid, I've no idea how I'd actually write in a bit where you guess, so I've just stuck with the generation side of it.

### 1. Introduction

This is well-documented code but it is complex and awkward to use. Some work is needed to make it simpler.

The key problem, it seems to me, is that the caller is required to proceed in three steps: (i) create the WordSearch object; (ii) load the list of words by calling the format_input_list method; (iii) call the generate method.

It is not clear to me that anything is gained by this division into steps, so if I were writing it I would redesign the interface so that everything is done in one step. An additional advantage of this is that the user only has to read one docstring.

### 2. Review

1. The code could easily be made portable to Python 3 by using the print function instead of the print statement, and using range instead of xrange.

2. width and height would be better parameter names than x and y.

3. The default values to the constructor (x=0 and y=0) are unhelpful. Choosing values for parameters requires experience with an API, but you can't get experience with an API until you've chosen values for parameters. Good defaults help beginners get out of this cycle.

4. There's no need for kwargs in __init__. Specify all keyword arguments explicitly:

def __init__(self, width=10, height=10, difficulty=5):

5. The __repr__ is unhelpful too:

>>> WordSearch()
<__main__.WordSearch object at 0x10442f278>


Did this work or not? It is easier to work with objects that are self-describing.

6. The name format_input_list is misleading: it does not actually format anything.

7. word_length_min is not actually the minimum word length, but one less than the minimum. Possibly word_length_min < len(i) should be word_length_min <= len(i).

8. direction_coordinate is way too complicated. There are three kinds of decoding going here: (i) location identifiers to location coordinates (ii) direction numbers to direction names; (iii) direction names to directions. The fact that you need debug_grid is a sign that you've over-complicated things.

I would avoid (i) by representing the grid as a list of lists instead of a single list; and I would avoid (ii) by working directly with direction names instead of direction numbers. Using this approach you could cut out direction_coordinate completely.

To implement (iii), the code builds a decoding table every time direction_coordinate is called. But the decoding table is the same every time, so this is a waste. It would be better to make this a global variable, as in my revised code below.

9. Representing difficulty levels as numbers is hard to understand and needlessly complex (because there have to be encoding and decoding steps). It would be clearer to represent difficulty levels as collections of directions:

EASY = 'down right'.split()
MEDIUM = 'up down left right'.split()
HARD = 'up down left right upleft upright downleft downright'.split()


Using this approach, you could cut out get_difficulty completely.

10. The string 'abcdefghijklmnopqrstuvwxyz' is built into Python as string.ascii_lowercase.

### 3. Revised code

This doesn't implement everything that the original code does (in particular, it doesn't populate the empty squares); the idea here is to give you an idea of how to go about keeping the code simple and short:

import random
import string

LETTERS = set(string.ascii_lowercase)
EMPTY = '.'
DIRECTIONS = dict(up=(-1,0), down=(1,0), left=(0,-1), right=(0,1),
upleft=(-1,-1), upright=(-1,1), downleft=(1,-1),
downright=(1,1))

class WordSearch:
"""A word search puzzle.

Arguments to the constructor:

width       Width of the puzzle (default: 10).
height      Height of the puzzle (default: 10).
word_list   List of words to use (default: None).
word_file   File to load words from (if word_list is None).
min_len     Minimum length of words (default: 3).
max_len     Maximum length of words (default: None).
directions  Iterable of names of allowed directions (default: all eight).
density     Stop generating when this density is reached (default: .7).

"""
def __init__(self, width=10, height=10, word_list=None, word_file=None,
min_len=3, max_len=None, directions=DIRECTIONS, density=.7):

# Check arguments and load word list.
if max_len is None:
max_len = min(width, height)
if word_list is None:
if word_file is None:
raise ValueError("neither word_list nor word_file specified")
word_list = []
with open(word_file) as f:
for line in f:
word = line.strip()
if set(word) <= LETTERS and min_len <= len(word) <= max_len:
word_list.append(word)
else:
# Take a copy so that we can shuffle it without updating
# the original.
word_list = word_list[:]
random.shuffle(word_list)

# Initially empty grid and list of words.
self.grid = [[EMPTY] * width for _ in range(height)]
self.words = []

# Generate puzzle by adding words from word_list until either
# the word list is exhausted or the target density is reached.
filled_cells = 0
target_cells = width * height * density
for word in word_list:
# List of candidate positions as tuples (i, j, d) where
# (i, j) is the coordinate of the first letter and d is
# the direction.
candidates = []
for d in directions:
di, dj = DIRECTIONS[d]
for i in range(max(0, 0 - len(word) * di),
min(height, height - len(word) * di)):
for j in range(max(0, 0 - len(word) * dj),
min(width, width - len(word) * dj)):
for k, letter in enumerate(word):
g = self.grid[i + k * di][j + k * dj]
if g != letter and g != EMPTY:
break
else:
candidates.append((i, j, d))
if candidates:
i, j, d = random.choice(candidates)
di, dj = DIRECTIONS[d]
for k, letter in enumerate(word):
if self.grid[i + k * di][j + k * dj] == EMPTY:
filled_cells += 1
self.grid[i + k * di][j + k * dj] = letter
self.words.append((word, i, j, d))
if filled_cells >= target_cells:
break

def __repr__(self):
grid = (''.join(row) for row in self.grid)
words = ('{} at ({},{}) {}'.format(*w) for w in self.words)
indent = lambda lines: '\n'.join('    ' + line for line in lines)
return "Grid:\n{}\nWords:\n{}".format(indent(grid), indent(words))


For example:

>>> WordSearch(word_file='/usr/share/dict/words', density=.9)
Grid:
..tsoob.a.
ejectedus.
vlns.in.s.
iaaceclyed
biohloptne
rrmipogrtk
aeppragiir
tsesortpna
owarlikegp
sessilitys
Words:
warlike at (8,1) right
assenting at (0,8) down
vibrato at (2,0) down
stilt at (0,3) downright
chip at (3,3) down
sparked at (9,9) up
boost at (0,6) left
sessility at (9,0) right
serial at (7,1) up
ejected at (1,0) right
goes at (5,6) upleft
rose at (7,5) left
unclip at (1,7) downleft
moan at (5,2) up
clog at (3,3) downright
tripe at (4,7) down
ropy at (6,4) upright
pat at (5,4) downright


### 4. Replies to comments

1. My point in §1.3 is that it can be hard learning to use a new interface. Imagine me at the Python prompt, trying to use the WordSearch class for the first time. I try creating an object:

>>> w = WordSearch()
>>> w
<__main__.WordSearch object at 0x10442f278>


Now what? Did it work? How do I see the result? Well, maybe the display method will display it.

>>> w.display()
Traceback (most recent call last):
File "cr92649.py", line 448, in display
print('Words: '+', '.join(sorted(self.used_words.keys())))
AttributeError: 'WordSearch' object has no attribute 'used_words'


Oh, so maybe I need to call generate first:

>>> w.generate()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: generate() missing 1 required positional argument: 'num_iterations'


OK, I missed an argument. I suppose I could try 10 iterations:

>>> w.generate(10)
>>> w.display()
Words:


Now compare with the experience of using my code in §3 above:

>>> WordSearch()
Traceback (most recent call last):
File "cr92649.py", line 500, in __init__
raise ValueError("neither word_list nor word_file specified")
ValueError: neither word_list nor word_file specified


OK, I missed an argument. Let's try word_list:

>>> WordSearch(word_list=['hello', 'world'])
Grid:
..........
.......d..
.......l..
.......r..
.o.....o..
..l....w..
...l......
....e.....
.....h....
..........
Words:
world at (5,7) up
hello at (8,5) upleft


Success! The feedback is much more immediate in this version of the code and likely to lead to faster progress in using it.

2. In §1.4, what I mean is that kwargs should be reserved for the case where you do not know what all the keyword arguments are going to be. In the case where you do know the names of all the keyword arguments, then if you write:

def __init__(self, width=10, height=10, difficulty=5):


this is shorter and clearer than:

def __init__(self, width=10, height=10, **kwargs):
difficulty = kwargs.pop('difficulty', 5)


and you get better error messages. For example, if you misspell the name of the keyword, then in the first version you get:

>>> WordSearch(difficult=1)
TypeError: __init__() got an unexpected keyword argument 'difficult'


but in the second version there's no error message: it appears to work, except that difficulty gets the value 5 when you meant it to be 1.

3. List lookups are cheap, so I doubt that the list of lists implementation makes much difference to the performance of the code. If you are concerned, then measure both and see what the difference is.

• Thanks a lot for the feedback, had a very busy week so sorry about the late reply :) I'll reply to a few of the points I have questions about though. I don't quite get what you mean in 3, the values of 0 and 0 are just so you are not forced to enter anything, and it'll just not generate a grid. With 4, are you meaning no need for kwargs because I only have 1 value (I was leaving it open to adding more things), or is it a bad idea in __init__ in general? – Peter Jun 9 '15 at 18:51
• In 8, I admit I could have optimised the code a lot more, and your 2d lists are a nice idea, though wouldn't it be slower with larger values (editing a list of 100 items within a list of 100 lists as opposed to a single list of 10000 items)? The single list idea was kinda inspired by Minecraft, since the 3d chunks are just a list of integers to save space. I actually really like your idea for 9, it'd never even crossed my mind to do that. Also your density idea is cool. – Peter Jun 9 '15 at 18:59
• As to the first sentence with three steps, I've literally only just realised that WordSearch(10, 10).generate(20, words=['word','other']) doesn't work, it wasn't the intention, I just forgot to test it. I'm off to a festival tomorrow anyway so won't be able to reply for a while, thanks again for the help though :) – Peter Jun 9 '15 at 19:04
• Answers in §4.​ – Gareth Rees Jun 9 '15 at 20:02
• Thanks a lot, it's really useful seeing it from other peoples perspectives, I'm very good at ending up with messy code so it's nice to know how to fix it haha. Anyway I just tried timing the 2d lists vs 1d list by assigning random letters to random indexes, there's no actual difference in speed :) – Peter Jun 9 '15 at 21:12

One suggestion I have is that the directions handling seems a bit awkward. You have eight main directions that you want to combine in different ways, which immediately made me think of a bit mask:

class WordSearch(object):
"""

Directions:

1  2  4
\ | /
8 - + - 16
/ | \
32  64 128

"""

DIFFICULTY = {
0: 0b00010000,
1: 0b01010000,
2: 0b11010000,  # e.g. 2 is right, down-right and down
3: 0b11010110,
4: 0b11011110,
5: 0b11111111,
}

DIRECTIONS = [(-1, -1), ( 0, -1), ( 1, -1),
(-1,  0),           ( 1,  0),
(-1,  1), ( 0,  1), ( 1,  1)]

@classmethod
def get_directions(cls, difficulty):
"""Get corresponding directions for a specified difficulty.

>>> WordSearch.get_directions(2)
[(1, 0), (0, 1), (1, 1)]

"""
return [dir_ for index, dir_ in enumerate(cls.DIRECTIONS)
if 1 << index & cls.DIFFICULTY[difficulty]]


Now you can easily get the actual steps to make within your grid (e.g. right is (1, 0); +1 in the x direction, 0 in the y direction).

• Hmm, that's quite interesting, not come across bit masks before so I'll have a look into them. The only problem with using coordinates though is because the grid is just a list, it doesn't contain x and y values, and the directions are calculated based on what needs to be added or subtracted for to get to the next one (eg, 10x10 grid, up is -10, right is +1 etc). I was aware the numbers weren't great but I didn't know what else to do :) – Peter Jun 4 '15 at 14:53
• @Peter ah, I hadn't realised that; this is probably more use for the cases where the grid is e.g. a list of lists, and you can actually use (x, y) coords. – jonrsharpe Jun 4 '15 at 14:55
• That was my original idea to be fair, but I've never been good at efficiency so thought I'd try something different for once aha. For general use though, taking the directions as an example since they're 0-7, is Python going to be more efficient if you assign the numbers as 3 bits as opposed to integers? – Peter Jun 4 '15 at 14:57
• @Peter no, it wouldn't be any more efficient. The reason I've used 2 ** x instead of x to represent each direction is for the bit masking to combine directions, which you can't do with 0-7. If you want to stick with the single string, DIRECTIONS would be e.g. [-11, -10, -9, -1, 1, 9, 10, 11] instead, and have to be an instance instead of class attribute as it varies with grid size. – jonrsharpe Jun 4 '15 at 15:03