In this problem, you will implement a program that solves the Word Search puzzle

Question

In this problem, you will implement a program that solves the Word Search puzzle, which is to search if a word appears in a two-dimensional 2 table/list of n rows and n columns of upper-case characters. The word can either appear in a row from left to right, in a column from top to bottom, or in a diagonal from top to bottom (either top-right to bottom-left, or top-left to bottom-right). The word may not fill out the entire row/column/diagonal. To break-up your problem into smaller tasks, do the following. (a) Write a Boolean function CheckRow (table, r, pos, word) that checks whether the string word appears in row r of the two dimensional list, table, starting at position pos. (b) Write a Boolean function CheckColumn (table, c, pos, word) that checks whether the string word appears in column c of table starting at position pos. (c) Write a Boolean function CheckDiagonal-TRBL(table, pos, word) that checks whether the string word appears in table starting at position pos and running diagonally from top-right to bottom-left. (d) Write a Boolean function CheckDiagonal-TLBR(table, pos, word) that checks whether the string word appears in table starting at position pos and running diagonally from top-left to bottom-right. Using the above functions, write a program that reads a square table of characters from a text file (the file extension should be “.txt”), and a word from the user, and returns whether or not the word appears in the table, and in case it appears, the position of each character in the table. 3 For example, if the file contains the table below, and the user enters the word “PYTHON”, then your program should output that the word is found at positions (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6) of the table, where the first coordinate stands for the row number and the second for the column number. If the word is not in the table, then your program should simply output that. Please proivide simple python program

C P T P A I R S

N Y Y O R K Q M

A T A T E R S N

B E R T H O L D

L A L A G O O K

B A L O O N N E

T W I N P E A K

V A N N I T Y S

Explanation / Answer

PYTHON 3

from __future__ import print_function

def Row(Matrix, posR, posC, colSize, word):

length = len(word)

for x in range(length):

if posC + x >= colSize or word[x] != Matrix[posR][posC + x]:

return False

return True

def CheckRow(Matrix, row, rowSize, colSize, word):

for x in range(colSize):

if(word[0] == Matrix[row][x]):

if Row(Matrix, row, x, colSize, word) == True:

return x

return -1

def Col(Matrix, posR, posC, rowSize, word):

length = len(word)

for x in range(length):

if posR + x >= rowSize or word[x] != Matrix[posR+x][posC]:

return False

return True

def CheckCol(Matrix, col, rowSize, colSize, word):

for x in range(rowSize):

if(word[0] == Matrix[x][col]):

if Col(Matrix, x, col, rowSize, word) == True:

return x

return -1

def diagonal_L2R(Matrix, row, rowSize, col, colSize, word):

length = len(word)

for x in range(length):

if row + x >= rowSize or col + x >= colSize or word[x] != Matrix[row+x][col+x]:

return False

return True

def diagonal_R2L(Matrix, row, col, word):

length = len(word)

for x in range(length):

if row - x < 0 or col - x < 0 or word[x] != Matrix[row-x][col-x]:

return False

return True

def check(word, Matrix, rowSize, colSize):

wordLength = len(word)

for x in range(rowSize): # for Row

out = CheckRow(Matrix, x, rowSize, colSize, word)

if(out != -1):

print('row :' ,x,out) # PUT LOOP HERE TO PRINT ALL CO-ORDINATES ROW WISE STARTING FROM X,OUT

return

for x in range(colSize): # for Column

out = CheckCol(Matrix, x, rowSize, colSize, word)

if(out != -1):

print('col : ',out,X) # PUT LOOP HERE TO PRINT ALL CO-ORDINATES COLUMN WISE STARTING FROM OUT,X

return

for x in range(rowSize):

for y in range(colSize):

if(Matrix[x][y] == word[0]):

if diagonal_L2R(Matrix, x, rowSize, y, colSize, word) == True:

print('L2R daigonal ', x, y) # CO-ORDINATES PRINT IN TOP LEFT TO DOWN RIGHT STARTING FROM X,Y

return

if diagonal_R2L(Matrix, x, y, word) == True:

print('R2L diagonal ',x,y) # CO-ORDINATES PRINT IN TOP RIGHT TO DOWN LEFT STARTING FROM X,Y

return

return

def main():

row = 7 #input("Row size? ") ## Set it if you want to use it for runtime initialization

col = 8 #input("Column size? ")

Matrix = [['C', 'P', 'T', 'P', 'A', 'I', 'R', 'S'],['N', 'Y', 'Y', 'O', 'R', 'K', 'Q', 'M'],['A', 'T', 'A', 'T', 'E', 'R', 'S', 'N'], ['B', 'E', 'R', 'T', 'H', 'O', 'L', 'D'],['L', 'A', 'L', 'A', 'G', 'O', 'O', 'K'],['B', 'A', 'L', 'O', 'O', 'N', 'N', 'E'],['T', 'W', 'I', 'N', 'P', 'E', 'A', 'K']]

word = input('Enter Search string? ')

check(word, Matrix, row, col)

if __name__ == '__main__':

main()

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.