Word search generator in Python

Question

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

Answer 1

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

• Rohit Kumar: 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 :)
• Mike: 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.
• Raimund Krämer: You comment character is wrong. It should be # instead of %.
• Rohit Kumar: @Mike Yeah I am currently trying to implement your pseudo-code
• Rohit Kumar: @RaimundKrämer You are right but it is psuedo-code