Programming Project 11

Programming Projects are to be submitted to gradescope.

Due date: Friday, May 02, 2025 at 9pm

This programming project is an adaptation of Ben Dicken’s WordSearch Programming Assignment.

WordSearch

In this assignment, you will be tasked with writing a program that finds certain words within a wordsearch grid and returns the word mapped to the line and starting character location of each word. The information of the board, and the words will be provided via files you will need to read in.

You should name the file wordsearch.py. Your code should have a main function that print a dictionary (see specification below).

Words text file

Your program should open up and read a text file name which determines which words you are searching for in your puzzle file! You can assume that each line in the input text file is formatted as follows: each line of the file is a word from the “word bank”.

Contents of words.txt:

computer
science

Puzzle text file

This file contains a grid of letters and hidden within those letters are certain words you will need to be searching for. You will use the words in words.txt to figure out what letter combination of words you need to find. This is an example of what this word-grid file would look like:

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

The puzzle file could have more or less Rows/Columns depending on each test case.

Output

The program should return a dictionary with the starting row / col locations for each word found. Your code should have a main function and you need to call the main function to print this dictionary. The formatting of the dictionary should be something like:

{"word1": [1, 1], "word2": [5, 5]}

Example Run

Say that words.txt contains:

army
navy
star
america
bullet

And then grid.txt contains:

Z S Y M R A Z
R N Z Z A Q L
M A T R T U I
N V Y A S S D
B Y Z T C V B
V B U L L E T
A M E R I C A

Your program should return and print:

{"army": [1, 6],
 "bullet": [6, 2],
 "america": [7, 1],
 "navy": [2, 2],
 "star": [4, 5]}

A word in the grid can be horizontal or vertical, the order of letters may go forward or backward. For example, when searching for the word star, the starting position is row 4 and column 5 for the letter s (vertical backward direction). Another example is the word bullet, the starting position is row 6 and column 2 for the letter b (horizontal forward direction). Consider the cases when a word only show up once in the grid.

Development Strategy 1

This section covers how you should go about structuring and implementing the code. In total, your program should have at least 4 functions. My recommendation for these functions:

# All your functions are defined here

def main():
    # call a function to load in the forwards words, computes the backwards version of each word, and save into a dictionary, passing in the needed arguments
    
    # call a function for transposing the grid, passing in the needed arguments

    # call a function for searching through lines, passing in the needed arguments
    
    # call a function for checking if a word is found on a line and where it is (index), passing in the needed arguments
    
    # print the dictionary with words as keys and their positions as values

main()

You may have other functions as well and use your preferred names for them, but you MUST call your main function when submitting your file. Your main function should call print function only once, which is in the last step to print the dictionary. You may build this program in the following sequence:

(1) Reading in input files

Create a function that will be responsible for opening up the words file and reading in the information. You can pass the file name into this function via arguments / parameters. The function should iterate through the lines and create a dictionary that maps the forwards-spelling to the backwards spelling. After the data is read in, the function should return the dictionary back to main. Next, open word input grid file up.

(2) Word search

Horizontal search is a bit easier than vertical mode, so I recommend that you work on this first. Create a function for this, and pass it the word dictionary, the grid file, and the mode. Iterate through the lines of the file one-at-a-time. For each line you encounter, you can search for all of the words in the word dictionary to see if you can find it.

If you try to do all of this in one function, you will probably end up with 3 or 4 levels of nested loops, which can get rather disorganized. I recommend that you create another function, perhaps called something like search_within_line that handles processing one line of searching. The horizontal function can call this for each line that it encounters.

There will be separate test cases for horizontal and for vertical. I recommend that you get the horizontal ones to pass before moving on to vertical.

In vertical search, you have to search for the words in the columns of the grid, rather than the rows. This is a bit more complex, but still very do-able. The way you should go about this is create a loop where you iterate through the column indexes. Within this loop, create another loop that goes through every character in that column and creates a list of those characters. Then, you can treat this column as if it is a row.

Development Strategy 2

You may also consider another strategy:

# All your functions are defined here

def main():
    # call a function to load in the words and save into a list, passing in the needed arguments
    
    # call a function to get each word of the 4 directions at each position, passing in the needed arguments

    # call a function to save all the words in the 4 directions for all the indices using a dictionary, passing in the needed arguments
    
    # call a function for checking if a word is found in any one of the 4 directions (the value) and where it is (the key), passing in the needed arguments
    
    # print the dictionary with words as keys and their positions as values
    
if __name__ == '__main__':
    main()

The 4 directions are: horizontal forward, horizontal backward, vertical forward, and vertical backward. For example, for position [2, 2], the words are: navybm, ns, nzzaql and nr.