project-11.qmd

---
title: "Programming Project 11"
---

```{r}
#| echo: false
#| message: false
#| warning: false
library(tidyverse)
library(readxl)
assignments <- read_excel("assessment_schedule.xlsx") %>% 
  mutate(formatted_date = format(due_date, "%A, %B %d, %Y"))
```

Programming Projects are to be submitted to [gradescope](https://www.gradescope.com/courses/934148).

**Due date: `r assignments %>% filter(assessment == "Programming Project 11") %>% pull(formatted_date)` 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 function called `search` that returns 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`:

```{html}
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:

<pre>
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
</pre>

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 function called `search` that returns this dictionary. The formatting of the return dictionary should be something like:

```{python}
#| eval: false
{"word1": [1, 1], "word2": [5, 5]}
```


# Example Run

Say that `words.txt` contains:

```{html}
army
navy
star
america
bullet
```

And then `grid.txt` contains:

<pre>
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
</pre>

Your program should return:

```{python}
#| eval: false
{"army": [1, 6],
 "bullet": [6, 2],
 "america": [7, 1],
 "navy": [2, 2],
 "star": [4, 5]}
```

For example, when searching for the word `star`, the starting position is row 4 and column 5 for the letter `s`. A word in the grid can be horizontal or vertical, the order of letters may go forward or backward. 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 5 functions. My recommendation for these five functions:

* A function to load in the forwards words, computes the backwards version of each word, and save into a dictionary
* One for transposing the grid
* One for searching through lines
* One for checking if a word is found on a line and where it is (index)
* You may have other functions as well. You should 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.

Your functions for this part should be called `text_to_dictionary` and `load_search_grid`.

## (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: 

* A function to load in the words and save into a list
* One to get each word of the 4 directions at each position
  * 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`
* One to save all the words in the 4 directions for all the indices using a dictionary
* One for checking if a word is found in any one of the 4 directions (the value) and where it is (the key)
* You may have other functions as well. You should build this program in the following sequence:

# Example run

```{python}
#| echo: true
#| eval: false
if __name__ == '__main__':
    word_bank = text_to_dictionary("words.txt")
    grid = load_search_grid("grid.txt")
    assert search(word_bank, grid) == {"army": [1, 6],
                                       "bullet": [6, 2],
                                       "america": [7, 1],
                                       "navy": [2, 2],
                                       "star": [4, 5]}
    print("Passed test.")
```