Word Search Generator

Question

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 = [0]
        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:
                word_list = f.read().split('\r\n')

        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[0] or word_section[1] != word_len:

                        new_word = word[random.randint(0, word_section[0]):random.randint(word_section[1], 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)[0]
                            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[0]]
                        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][0]), self.direction_to_text(words[word][1])

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.

Answer 1

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.

Answer 2

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).