Word Search / Find a Word Generator Python

Question

I am trying to code a word search/find a word generator and I'm stuck with some parts. The aim of this code is to take in dimensions and words from user input and generate a random word search/find a word.

The problem is that the letters will occasionally overwrite each other. To try and stop this I have this line of code in my functions:

lines[0][randCoO[0] - (i)][randCoO[1]] == '-':

That line belongs in the function U

It is meant to test if the space is empty (populated by a ' - ' )

I know I'm supposed to try and refrain from putting my whole code in as it is probably long and annoying to read but please, try and help me

This is my code:

    try:
    dim=int(raw_input('How many letters high and long do you want your find-a-word? (It has to be <= 79) '))
except ValueError:
        raise SystemExit, 'Dude, thats not a number!'

if dim > 79:
    raise SystemExit, "\n That number is bigger than 79. It won't print to well. \n"


count=0

allwords = raw_input('What words do you want in your find-a-word?\n(Enter them all together seperated by a comma)')

allwords = allwords.upper()
allwords = allwords.split(', ')
nowords = len(allwords)

while count < nowords:
    if len(allwords[count])>dim:
        raise SystemExit, "\nYour find-a-word is not big enough for one or more of your words.\nIt is doomed to fail! "
    count = count + 1

    randletter = []
    import random
    randrange = random.randrange
    alphabet = ['A', 'B', 'C', 'D', 'E', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

    all_words = ' '.join(allwords)

    print '\n\nTry to find these words in the word find-a-word\n\n'
    count = 0
    while count < nowords:
        print allwords[count],'\n'
        count=count+1

        drctn = ['U','D','L','R','UL','UR','DL','DR']

        randdrctnlist = []

for i in range(nowords):
    randdrctn = drctn[randrange(0,4)]
    randdrctnlist.append(randdrctn)

    d = {}

for i in range(dim):
    d['line' + str(i + 1)] = ['-']*dim

    lines = []
    lines.append(d.values())
    lines.sort()

    CoO1 = []
    CoO2 = []
    CoO = []

for i in range(dim):
    CoO1.append(i)
    CoO2.append(i)    

    CoO.append(CoO1)
    CoO.append(CoO2)

    count = 0

def U(word, wordno, count, dim, lines):
    stop = 0
    randCoO = []
    while count == 0:
        rand = CoO[0][randrange(0,dim)]
        randCoO.append(rand)
        rand = CoO[1][randrange(0,dim)]
        randCoO.append(rand)
        for i in range(len(word[wordno])):
            if randCoO[0] >= (len(word[wordno]) - 1) and lines[0][randCoO[0] - (i)][randCoO[1]] == '-':
                count = 1               
                lines[0][randCoO[0]][randCoO[1]] = word[wordno][0]
                while count < len(allwords[wordno]):
                    lines[0][randCoO[0] - (count)][randCoO[1]] = word[wordno][count]
                    count = count + 1                
            else:
                print randCoO
                randCoO = []
                stop = stop + 1
                print stop
                if stop > dim*dim:
                    raise SystemExit, "\nThe find-a-word is probably impossible to make\nwithout overwriting already placed letters.\nPlease try it again. If this has show up many times in a row try making the dimensions of you find-a-word bigger\n(Or you're just unlucky!)\n"
                break

def D(word, wordno, count, dim, lines):
    stop = 0
    randCoO = []
    while count == 0:
        rand = CoO[0][randrange(0,dim)]
        randCoO.append(rand)
        rand = CoO[1][randrange(0,dim)]
        randCoO.append(rand)
        for i in range(len(word[wordno])):
            if dim - randCoO[0] > len(word[wordno]) - 1 and lines[0][randCoO[0] + (i)][randCoO[1]] == '-':
                count = 1
                lines[0][randCoO[0]][randCoO[1]] = word[wordno][0]
                while count < len(allwords[wordno]):
                    lines[0][randCoO[0] + (count)][randCoO[1]] = word[wordno][count]
                    count = count + 1
            else:
                print randCoO
                randCoO = []
                stop = stop + 1
                print stop
                if stop > dim*dim:
                    raise SystemExit, "\nThe find-a-word is probably impossible to make\nwithout overwriting already placed letters.\nPlease try it again. If this has show up many times in a row try making the dimensions of you find-a-word bigger\n(Or you're just unlucky!)\n"
                break   

def L(word, wordno, count, dim, lines):
    stop = 0
    randCoO = []
    while count == 0:
        rand = CoO[0][randrange(0,dim)]                            
        randCoO.append(rand)
        rand = CoO[1][randrange(0,dim)]
        randCoO.append(rand)
        for i in range(len(word[wordno])):
            if dim - randCoO[1] > (len(word[wordno]) - 1) and lines[0][randCoO[0]][randCoO[1] + (i)] == '-':
                count = 1  
                lines[0][randCoO[0]][randCoO[1]] = word[wordno][0]
                while count < len(allwords[wordno]):
                    lines[0][randCoO[0]][randCoO[1] + (count)] = word[wordno][count]
                    count = count + 1
            else:
                print randCoO
                randCoO = []
                stop = stop + 1
                print stop
                if stop > dim*dim:
                    raise SystemExit, "\nThe find-a-word is probably impossible to make\nwithout overwriting already placed letters.\nPlease try it again. If this has show up many times in a row try making the dimensions of you find-a-word bigger\n(Or you're just unlucky!)\n"
                break

def R(word, wordno, count, dim, lines):
    stop = 0 
    randCoO = []
    while count == 0:
        rand = CoO[0][randrange(0,dim)]                            
        randCoO.append(rand)
        rand = CoO[1][randrange(0,dim)]
        randCoO.append(rand)
        for i in range(len(word[wordno])):
            if randCoO[1] >= (len(word[wordno]) - 1) and lines[0][randCoO[0]][randCoO[1] + (i)] == '-':
                count = 1  
                lines[0][randCoO[0]][randCoO[1]] = word[wordno][0]
                while count < len(allwords[wordno]):
                    lines[0][randCoO[0]][randCoO[1] - (count)] = word[wordno][count]
                    count = count + 1
            else:
                print randCoO
                randCoO = []
                print stop
                stop = stop + 1
                if stop > dim*dim:
                    raise SystemExit, "\nThe find-a-word is probably impossible to make\nwithout overwriting already placed letters.\nPlease try it again. If this has show up many times in a row try making the dimensions of you find-a-word bigger\n(Or you're just unlucky!)\n"
                break

for i in range(nowords):
    count = 0
    print randdrctnlist
    if randdrctnlist[i] == 'U':
        U(allwords, i, count, dim, lines)
    if randdrctnlist[i] == 'D':
        D(allwords, i, count, dim, lines)
    if randdrctnlist[i] == 'L':
        L(allwords, i, count, dim, lines)
    if randdrctnlist[i] == 'R':
        R(allwords, i, count, dim, lines)

for i in range(dim):
    print ' '.join(lines[0][i])

Answer 1

I think you need to rethink the fundamental algorithm. Your code is trying to create words in random directions and then managing the collisions. Instead you could consider all points of intersection between all your words, then build all possible overlaps, and randomly choose from the results.

For example: 'FROG' intersects 'DOG' in two letters, so they could intersect from 7 directions on the 'G' and 6 on the 'O'. 'CAT' and ('DOG' or 'FROG') have no letters in common, so they will not be able to intersect at all. If you try each of the combinations of 'existing solution so far', then call your solution recursively and add a new word in all possible other combinations that fit within the dimensions of the puzzle, you will have all possible find-a-words with the given words.

In order to reduce the dimensionality of this, I think you should first place words that don't intersect. If they don't all fit you can exit with an error. Then deal with words in order of descending size.

You can then either pick randomly or just exit as soon as you find a solution. If you want your answer to have different characteristics (like being more spread out to use the whole given dimensions), I think you can just rearrange the way you try combinations, and choose the first solution given.