1
\$\begingroup\$

I have made a word-search-generator with Python 3 and it works perfectly. Can you please tell me if what I have done is done in the right way? Also, please tell me how the code is performance-wise. I have tried my best to write helpful comments.

import random
from copy import deepcopy
def make(row,column):
    return [['_' for _ in range(column)] for a in range(row)] # Generates a empty array of specified width(column) and height(row)
def add_horizontally(word,array,row,column,backwards=False):
    arr = deepcopy(array) #Copy the array because we may make unwanted mutations
    word = word[::-1] if backwards else word #If backwards is true reverse the word
    somearr = list(word)
    for c in somearr:
        if((arr[row][column] != '_') & (arr[row][column] != c)): #If there already exists a character and it is not same as c then
            raise Exception("Oh the letter is already there") #Throw a error
        else:
            arr[row][column] = c #Else add the letter to the correct row and column
            column += 1 #Increase column by 1
    return arr
def add_vertically(word,array,row,column,backwards=False): #Same as add horizontally except it increases row by 1
    arr = deepcopy(array)
    word = word[::-1] if backwards else word
    somearr = list(word)
    for c in somearr:
        if((arr[row][column] != '_') &  (arr[row][column] != c)):
            raise Exception("Oh the letter is already there")
        else:
            arr[row][column] = c
            row += 1
    return arr
def add_diagonally(word,array,row,column,backwards=False): #Same as add_vertically except increase both row and cloumn by 1
    arr = deepcopy(array)
    word = word[::-1] if backwards else word
    somearr = list(word)
    for c in somearr:
        if((arr[row][column] != '_') & (arr[row][column] != c)):
            raise Exception("Oh the letter is already there")
        else:
            arr[row][column] = c
            row += 1
            column += 1
    return arr
def random_condition(rows,columns,backwards=True,diagonals=True): # Generate a random condition for the placement of word
    row = random.randint(0,rows)
    column = random.randint(0,columns)
    backward = backwards if not backwards else [True,False][random.randint(0,1)] #If backwards is false let it remain so else generate a random value
    diagonal = diagonals if not diagonals else [True,False][random.randint(0,1)] #Same as above
    return (row,column,backward,diagonal)
def check(condition,word): # Check ifthe provided condition is fitting i.e. there should be no out of index problem
    diagonal = condition[0][3]
    row_start = condition[0][0]
    column_start = condition[0][1]
    rows = condition[1]
    columns = condition[2]
    vertical = condition[3]
    if(diagonal):
        if(((rows-row_start) >= len(word)) & ((columns - column_start) >= len(word))):
            return True
        else:
            return False
    if(vertical):
        if(rows-row_start>len(word)):
            return True
        else:
            return False
    else:
        if(columns - column_start>len(word)):
            return True
        else:
            return False
def random_alpha(): # Returns a random alphabet
    return 'abcdefghijklmnopqrstuvwxyz'[random.randint(0,25)]
def randomize(arr): # After the grid is made fill the remaining places with randome characters
    return [[m if m!='_' else random_alpha() for m in a] for a in arr]
def generate(row,column,word_list,backwards=True,diagonal=True): # Uses all the above methods to make array
    if((max(len(w) for w in word_list) > row) | (max(len(w) for w in word_list) > column)): #If the word is larger than row or column length than return 'wrong'.
        return ('wrong',)
    else:
        pass
    array = make(row,column)
    row -= 1 # Because indexing starts at 0!
    column -= 1 # Because indexing starts at 0!!
    for word in word_list:
        i = True
        while(i):
            vertical = False
            conditions = random_condition(row,column,backwards=backwards,diagonals=diagonal)
            if(not conditions[3]): # If diagonal is false
                vertical = [True,False][random.randint(0,1)]
            if (check((conditions,row,column,vertical),word)):
                if(conditions[3]): # If diagonal is true 
                    try: # We may throw a error
                        array = deepcopy(add_diagonally(word,array,conditions[0],conditions[1],conditions[2]))
                        i = False
                    except Exception:
                        pass
                elif(vertical):
                    try:
                        array = deepcopy(add_vertically(word,array,conditions[0],conditions[1],conditions[2]))
                        i = False  
                    except Exception:
                        pass    
                else :
                    try:
                        array = deepcopy(add_horizontally(word,array,conditions[0],conditions[1],conditions[2]))
                        i = False
                    except Exception:
                        pass
    return randomize(array) # Fill with random characters
def text(arr): # Convert given array to text  
    str = ''
    for row in arr:
        for word in row:
            str += word + ' '
        str += '\n'
    return str
open('test.txt','w').write(text(generate(15,15,['Lord','Voldemort','likes','penpineapple','applepen']))) # To test it!

This is what I get by changing line return randomize(array) to return array:

_ _ _ _ _ _ _ _ d r o L _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ a p p l e p e n _ _ _ _ _ _
_ V _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ o _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ l _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ d _ _ _ _ _ _ _ _ _ _
e l p p a e n i p n e p _ _ _
_ _ _ _ _ _ m _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ o _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ r _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ t _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
s e k i l _ _ _ _ _ _ _ _ _ _

And on randomizing it:

s u n e p e l p p a t l e s n
j d l p p s s y n y f w l i j
m b p z n y q h y l m y p w s
a f x f n a j o q e l t p p j
d g o m p r i c t d f j a q d
r g t v l V n j c l k x e f y
o z d r v g o p t h o a n f a
L u g e c s b l v w g b i f l
i l l i k e s q d r z s p p l
s b k g y g c e x e f y n y g
p b c h u k d l b w m e e o h
q a q k h c m h i c c o p h z
h k w g u c l r m c h j r g g
k o v g k n w x y z d j e t x
e b n d x z q d z b w y z p k
\$\endgroup\$
1
\$\begingroup\$
  1. Slight nitpick, but I don't like using the word array in Python. They may have array-like syntax from languages like C, but strictly speaking they aren't arrays.

  2. Sanitize your inputs. If a word contains _ , then I suspect your program will not work as intended. As an addendum, don't use sentinel values that could actually be valid. A better option here would be to store blanks as None.

  3. Refrain from using exceptions unless your case is truly exceptional. In here, it's not very uncommon for a word to conflict with another letter. In this case, performance isn't going to matter but it may in a more CPU-intensive program.

  4. It's quite easy for your program to enter an infinite loop especially if the word list is large. This is because it won't be able to fit all words into the grid and then it'll get stuck. Ideally, you would want to have a way to find a random location amongst those that already work. We don't want to rely on RNG.

Instead of picking a row, column at random and hoping it works, make a generator that yields all locations and orientations that do work for the current word. For this to be correct, it needs to be able to detect when an a grid with a word list is truly impossible. We can use a depth-first search to detect this. The following is pseudo-code on how I would implement it.

 def placements(word, grid):
    Yields the location, orientation that works for word on the grid

 # Fills in a valid configuration for your grid using DFS
 def generate(grid, words, row, col):
       # No more words left to read, we're done
       if len(words) == 0:
         return true
       places = list(placements(word[0], grid))
       # Means current branch won't work !
       if len(places) == 0:
           return false
       random.shuffle(places)
       for (location, orientation) in places:
           cpy = deepcopy(grid)
           Place word[0] into cpy at its location, orientation
           if generate(cpy, words[1:], row, col):
               grid = cpy
               return true 
       return false
\$\endgroup\$
  • \$\begingroup\$ I forgot to mention that I have a main function in another file which checks for the following errors in input :- 1) The words contain any other character than the alphabets 2) If there is any uppercase letter change it to lower case 3) The words can't be less than 4 characters 4) The row and column length can't be less than 5 characters 5) Total no. of letters has to be less than row*column*4/5 Sorry :( And thanks for the infinite loop one :) \$\endgroup\$ – Rohit Kumar Jan 19 '18 at 7:58
  • \$\begingroup\$ Ah that's confusing, as it seems you also do some checking at the beginning of your generate. Note it's still possible to enter an infinite loop even if there are only row * column * (4/5) letters. For example if you had a 6x6 grid and your words were "abcdef", "ghijk", "lmnop", "qrstu", "zzzzzz", then you could place the first 4 words around the boundaries of the grid, and "zzzzzz" would have no where to go. \$\endgroup\$ – Mike Jan 19 '18 at 8:31
  • \$\begingroup\$ You comment character is wrong. It should be # instead of %. \$\endgroup\$ – Raimund Krämer Jan 19 '18 at 8:35
  • \$\begingroup\$ @Mike Yeah I am currently trying to implement your pseudo-code \$\endgroup\$ – Rohit Kumar Jan 19 '18 at 8:48
  • \$\begingroup\$ @RaimundKrämer You are right but it is psuedo-code \$\endgroup\$ – Rohit Kumar Jan 19 '18 at 8:49

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.