jjjjj jjjjj - 7 months ago 136
Python Question

Recursively search

I'm using a txt file as a "word search board" that has words scrambled through it. I am also using a list of words in another txt file that may or may not be located in the word board. Words are found in all directions, north ,south,east,west, NE,NW,SE,SW and reverse of those. The function that is searching through the board must be recursive. In my current

searchBoard()
, I am trying to just search through using the first letter of the word and then check the surroundings for the next letter after and so on. My recursive function is working the way I want it , any tips would be appreciated.

Example text file for board:

G J T P B A V K U V L V
M N Q H S G M N T C E E
Y H I J S G Q E N Y C W
G S K M G H C B M U T H
R A T V M N V D G V U T
E P G U E A B P W Q R T
T J C I D D R Q T E E C
U P C I S E N G B U O B
P S J C I V N F O U N N
M P R O J E C T R R A M
O H Q T P P D S H A P G
C O W U K Q E G I J M S


Other txt file with list of words:

COMPUTER
SCRAM
COURSE
LECTURE
PROGRAMMING
PROJECT
SCIENCE
STUDENT


My code:

#Making the word file into a list
def getWords(wordList):
fname = open(wordList,'r')
lines = fname.read().split()

return(lines)


#Making the puzzle file into a 2d list.
def buildBoard(puzzleBoard):

fname = open(puzzleBoard,'r')
boardList = []
for line in fname:
number_strings = line.split()
letters = [n for n in number_strings]
boardList.append(letters)

fname.close()

print(boardList[1][0])#row ,then col. Both start at 0s

return(boardList)



#Recursively search board
def searchBoard(pos,puzzleBoard,wordList):
for word in wordList:
firstLetter = word[:1]
if puzzleBoard[pos[0]][pos[1]] == firstLetter:
newPos = pos[0][0]
searchBoard(newPos,puzzleBoard,wordList)

#Checking above
if puzzleBoard[pos[0]-1][pos[1]] == firstLetter:
newPos = [pos[0]-1,pos[1]]
searchBoard(newPos,puzzleBoard,wordList)


def main():
print("Welcome to the Word Search")
print("For this, you will import two files: 1. The puzzle board, and 2. The word list.")
puzzleBoard = input("What is the puzzle file you would like to import?: ")
wordList = input("What is the word list file you would like to import?: ")

puzzleBoard = buildBoard(puzzleBoard)
wordList = getWords(wordList)


pos = [puzzleBoard[0][0]]
searchBoard(pos,puzzleBoard,wordList)
main()


Error :

if puzzleBoard[pos[0]][pos[1]] == firstLetter:

TypeError: list indices must be integers or slices, not str

Answer

That was a nice practice :)
I took your input puzzleboard and wrote a small function which recursively searches through the puzzleboard. First it tries to find the first letter of the word text.find(word[0], pos) and then changes the x,y coordinates for each direction by using floor and modulo divisions and looks for the next letter. If the next letter doesn't match, it tries the next direction until either the whole word is found, or the characters don't match or it leaves the boundaries of the puzzleboard.
All words but SCRAM are found in your puzzleboard.

text = """
G J T P B A V K U V L V
M N Q H S G M N T C E E
Y H I J S G Q E N Y C W
G S K M G H C B M U T H
R A T V M N V D G V U T
E P G U E A B P W Q R T
T J C I D D R Q T E E C
U P C I S E N G B U O B
P S J C I V N F O U N N
M P R O J E C T R R A M
O H Q T P P D S H A P G
C O W U K Q E G I J M S"""

#cleans the input puzzleBoard
text = text.replace(' ', '').strip()
#gets the width and height of the puzzleboard
width = len(text.splitlines()[0])
text = text.replace('\n', '')
height = len(text) / width

#a dictionary storing the human readable directions
directions={0:'NW',1:'N',2:'NE',3:'W',4:'',5:'E',6:'SW',7:'S',8:'SE'}

#tries to find a word in a text
#returns x,y of the first character and the orientation of the word
def find_word(text, word):
    pos = 0
    while pos != -1:
        pos = text.find(word[0], pos)
        if pos > -1:
            for ori in [0,1,2,3,5,6,7,8]:
                found = True
                i = 0
                x = pos % width
                y = pos // height

                while found:
                    i += 1
                    if i == len(word) and found:
                        return (pos % width, pos // height, directions[ori])
                    #moves x,y in the selected direction
                    x += ori % 3 - 1
                    y += ori // 3 - 1
                    if x < width and y < height and x > -1 and y > -1:
                        found = text[width * y + x] == word[i]
                    else:
                        found = False
            pos += 1
    #nothing found
    return(-1, -1, directions[4])        

Update

Solving the same problem, but by recursively calling the same function. The function returns the found word, the x,y position of the last letter and the orientation, i.e. one would need to go backwards to find the whole word.

def find_char(text, pos, word, ori):
    x = int(pos % width)
    y = int(pos // height)
    x += ori % 3 - 1
    y += ori // 3 - 1
    if text[pos] != word[0]:
        return None
    if len(word) == 1:
        return (x,y)
    if x < width and y < height and x > -1 and y > -1:
        pos = int(width * y + x)
        if text[pos] == word[1]:
            if len(word) > 1:
                resp = find_char(text, pos, word[1:], ori)
                if resp:
                    return resp
        else:
            return None

word_list = ['COMPUTER', 'SCRAM', 'COURSE', 'LECTURE', 'PROGRAMMING', 'PROJECT', 'SCIENCE', 'STUDENT']
for i in range(len(text)):
    for ori in [0,1,2,3,5,6,7,8]:
        for word in word_list:
            resp = find_char(text, i, word, ori)
            if resp:
                print(word, resp, ori)
Comments