Instructions for wordSearch

(produced at 11:13 a.m. UTC on 2021-10-31)

This task is part of ps06 which is due at 23:59 EDT on 2021-11-02.

You have the option to work with a partner on this task if you wish. Working with a partner requires more work to coordinate schedules, but if you work together and make sure that you are both understanding the code you write, you will make progress faster and learn more.

You can submit this task using this link.

Put all of your work for this task into the file wordSearch.py
(which is provided among the starter files)

Word Search

In this task you will implement a program that solves word search puzzles. A word search puzzle consists of a text grid, and a list of words that are hidden in it. The goal is to find all of the words on the list. Words can be hidden vertically, horizontally, or diagonally. They can also be backwards in any direction.

You will complete the provided wordSearch.py file, which simulates solving a word search puzzle.

We have given you some starter code that generates a random word search puzzle, along with a simple fixed test puzzle to experiment with. The function wordPuzzle.generatePuzzle returns two values: a list of strings that represents the rows of a text grid, and a list of words that are hidden within the text grid.

By default, generatePuzzle produces a 10x20 text grid with a list of tea-themed words hidden within it. However, you can supply parameters to change the size and word list. For instance, you could call:

wordPuzzle.generatePuzzle(r=20, c=20, words=["latte","espresso","bean"])

if you want a bigger puzzle that is coffee-themed.

Your solutions should NOT be hard-coded for a particular grid size or word list: they should work for any grid and word list provided, although you may assume that the grid is at least 1x1, and that each word in the provided list of words (which will not be empty) is actually in the provided grid horizontally, vertically, or diagonally.

Note: as usual, each function you write must be documented.

Part A: Printing the puzzle

Your first goal is to print out the text grid for the word search puzzle. The value returned by generatePuzzle is a list of strings representing rows in the text grid. Write a function that prints each row of the puzzle on a separate line.

Call this function printGrid. It must take one parameter: a list containing rows in a text grid. These printGrid examples demonstrate how it should word.

Part B: Retrieving columns

Although we have represented the text grid as a list of rows, words may also be hidden in columns. To make it easier to find these words, write a function that produces a list of the text grid's columns.

Call this function getColumns.

Your function must take the list of rows as a parameter, and return a list of strings, where each string represents a column in the puzzle. These getColumns examples demonstrate how it should work.

Make sure your function works with different puzzle sizes!

Part C: Finding horizontal words

Write a function called findHorizontals that finds all horizontal words in the puzzle. Your function must find all words hidden within rows, even if they are reversed. To reverse a string in Python, you can use this string-indexing shortcut:

mystring[::-1]

findHorizontals must take two parameters: the list of rows in the text grid, and the list of words hidden in the puzzle. It must return a list of words hidden horizontally and their positions.

Each item in the returned list must be a tuple with 4 fields: the word, its row number, the column number of its first letter, and "H" for horizontal. For example, if the only hidden word is the word word 'hello' and it is hidden backwards starting with the 'o' in column 2, row 2, the result would be:

[('hello', 2, 2, "H")]

These findHorizontals examples provide more demonstrations of how findHorizontals must work.

Note that findHorizontals is required to use a nested loop.

Part D: Finding vertical words

Write a function named findVerticals that finds all vertical words in the puzzle. Your function must find all words hidden within columns, even if they are reversed.

findVerticals must take two parameters: the list of columns (not rows) in the text grid, and the list of words hidden in the puzzle. It must return a list of words hidden vertically and their positions.

Each item in the returned list must be a tuple with 4 fields: the word, the row number of its first letter, its column number, and "V" for vertical. For example, if the word "goodbye" were hidden vertically starting in the 2nd row (i.e., row #1) and the 3rd column, the result would be:

[('goodbye', 1, 4, "V")]

This example of findVerticals further demonstrates how it will work.

Note that findHorizontals and findVerticals are very similar functions, although they have slight but important differences. Also, just like findHorizontals, findVerticals is required to use a nested loop.

Part E: Finding horizontal and vertical words

Using the functions you have written so far, write a function called findOrthogonalWords that finds vertical and horizontal words in a puzzle. Your function should do two things: (1) return a list of all horizontal and vertical words, with their positions; and (2) print all words that you have failed to find (diagonal words).

findOrthogonalWords must take three parameters: (1) a list of rows in the text grid, (2) a list of columns in the text grid, and (3) a list of words hidden in the puzzle. This example of findOrthogonalWords demonstrates how it should work.

Note that findOrthogonalWords must call findHorizontals and call findVerticals, and it must use a loop and it must call print within that loop.

Part F: Highlighting found words

Note: This part of the task is only covered by extra goals in the rubric, so you should not attempt it unless you have completed all of the core goals and are planning to complete all the extra goals.

Write a function called highlightWords that takes a text grid and a list of found words (with their positions), and produces a text grid where each found word is UPPERCASE.

highlightWords must take two parameters: a list of rows in the text grid, and a list of found words that includes positions and orientations (in the format returned by findOrthogonalWords). It should print out a copy of the text grid where each found word is in UPPERCASE and the rest of the puzzle is unchanged.

These examples of highlightWords demonstrate how it should work.

Examples

printGrid examples

These examples demonstrate how printGrid should work.

In []:
printGrid(['abcd', 'efgh', 'ijkl'])
Prints
abcd efgh ijkl
In []:
printGrid(['ab', 'cd', 'ef', 'gh', 'ij'])
Prints
ab cd ef gh ij

getColumns examples

These examples demonstrate how getColumns should work.

In []:
getColumns(['abcd', 'efgh', 'ijkl'])
Out[]:
['aei', 'bfj', 'cgk', 'dhl']
In []:
getColumns(['ab', 'cd', 'ef', 'gh', 'ij'])
Out[]:
['acegi', 'bdfhj']

findHorizontals examples

These examples demonstrate how findHorizontals should work.

In []:
findHorizontals(['----', 'find', '-me-'], ['find', 'me'])
Out[]:
[('find', 1, 0, 'H'), ('me', 2, 1, 'H')]
In []:
findHorizontals(['dnif', '-e--', '-m--'], ['find', 'me'])
Out[]:
[('find', 0, 0, 'H')]
In []:
findHorizontals( ['soacbykymduioaaiylyf', 'tghvnekchamomileztfd', 'arggfqavbkettleigedv', 'chonunnrvipeetsxzafc', 'jgbornnslrehucoqopjh', 'pcwliewixggevzdxyova', 'czpombclperkhlyeztti', 'wayoriouihiexqizxyrm', 'jmgyfngsaioryztcysax', 'ilrovurzcskenimsajny'], ['chai', 'oolong', 'earlgrey', 'rooibos', 'saucer', 'teapot', 'chamomile', 'jasmine', 'kettle', 'steep'] )
Out[]:
[('chamomile', 1, 7, 'H'), ('jasmine', 9, 11, 'H'), ('kettle', 2, 9, 'H'), ('steep', 3, 10, 'H')]

findVerticals examples

These examples demonstrate how findVerticals should work. Note that the first argument to findVerticals is a list of columns, not a list of rows, so it is still looking for the words along each string it is provided with, and will not find words whose letters are scattered across the columns it receives (so in the third example below, it finds nothing). Pay close attention to the row and column numbers it returns.

In []:
findVerticals(['----', 'find', '-me-'], ['find', 'me'])
Out[]:
[('find', 0, 1, 'V'), ('me', 1, 2, 'V')]
In []:
findVerticals(['dnif', '-e--', '-m--'], ['find', 'me'])
Out[]:
[('find', 0, 0, 'V')]
In []:
findVerticals(['-f-', '-im', '-ne', '-d-'], ['find', 'me'])
Out[]:
[]
In []:
findVerticals( ['stacjpcwji', 'ogrhgczaml', 'ahgobwpygr', 'cvgnolooyo', 'bnfurimrfv', 'yeqnnebinu', 'kkannwcogr', 'ycvrsilusz', 'mhbvlxpiac', 'dakirgehis', 'umepegriok', 'iotehekere', 'omteuvhxyn', 'ailtczlqzi', 'alesodyitm', 'ieixqxezcs', 'yzgzoyzxya', 'lteapotysj', 'yfdfjvtran', 'fdvchaimxy'], ['chai', 'oolong', 'earlgrey', 'rooibos', 'saucer', 'teapot', 'chamomile', 'jasmine', 'kettle', 'steep'] )
Out[]:
[('chai', 3, 19, 'V'), ('oolong', 2, 3, 'V'), ('teapot', 1, 17, 'V')]

findOrthogonalWords examples

These examples demonstrate how findOrthogonalWords should work. Note that findOrthogonalWords is given the list of rows and the list of columns as two separate arguments, so it does not have to use getColumns itself. Also note that it cannot find diagonal words, but it will also print a line for each missing word it cannot find, ordered by their order in the provided words list.

In []:
findOrthogonalWords( ['----', 'find', '-me-'], ['-f-', '-im', '-ne', '-d-'], ['find', 'me'] )
Out[]:
[('find', 1, 0, 'H'), ('me', 2, 1, 'H')]
In []:
findOrthogonalWords( ['d--', 'nem', 'i--', 'f--'], ['dnif', '-e--', '-m--'], ['find', 'me'] )
Out[]:
[('find', 0, 0, 'V'), ('me', 1, 1, 'H')]
In []:
findOrthogonalWords( ['f--e', '-im-', '--n-', '---d'], ['f---', '-i--', '-mn-', 'e--d'], ['find', 'me'] )
Prints
Missing find Missing me
Out[]:
[]
In []:
findOrthogonalWords( ['soacbykymduioaaiylyf', 'tghvnekchamomileztfd', 'arggfqavbkettleigedv', 'chonunnrvipeetsxzafc', 'jgbornnslrehucoqopjh', 'pcwliewixggevzdxyova', 'czpombclperkhlyeztti', 'wayoriouihiexqizxyrm', 'jmgyfngsaioryztcysax', 'ilrovurzcskenimsajny'], ['stacjpcwji', 'ogrhgczaml', 'ahgobwpygr', 'cvgnolooyo', 'bnfurimrfv', 'yeqnnebinu', 'kkannwcogr', 'ycvrsilusz', 'mhbvlxpiac', 'dakirgehis', 'umepegriok', 'iotehekere', 'omteuvhxyn', 'ailtczlqzi', 'alesodyitm', 'ieixqxezcs', 'yzgzoyzxya', 'lteapotysj', 'yfdfjvtran', 'fdvchaimxy'], ['chai', 'oolong', 'earlgrey', 'rooibos', 'saucer', 'teapot', 'chamomile', 'jasmine', 'kettle', 'steep'] )
Prints
Missing earlgrey Missing rooibos Missing saucer
Out[]:
[('chai', 3, 19, 'V'), ('oolong', 2, 3, 'V'), ('teapot', 1, 17, 'V'), ('chamomile', 1, 7, 'H'), ('jasmine', 9, 11, 'H'), ('kettle', 2, 9, 'H'), ('steep', 3, 10, 'H')]

highlightWords examples

These examples demonstrate how highlightWords should work. Note that you may assume that the found word list it gets is actually accurate.

In []:
highlightWords( ['----', 'find', '-me-'], [('find', 1, 0, 'H'), ('me', 2, 1, 'H')] )
Prints
---- FIND -ME-
In []:
highlightWords( ['d--', 'nem', 'i--', 'f--'], [('find', 0, 0, 'V'), ('me', 1, 1, 'H')] )
Prints
D-- NEM I-- F--
In []:
highlightWords( ['soacbykymduioaaiylyf', 'tghvnekchamomileztfd', 'arggfqavbkettleigedv', 'chonunnrvipeetsxzafc', 'jgbornnslrehucoqopjh', 'pcwliewixggevzdxyova', 'czpombclperkhlyeztti', 'wayoriouihiexqizxyrm', 'jmgyfngsaioryztcysax', 'ilrovurzcskenimsajny'], [('oolong', 2, 3, 'V'), ('teapot', 1, 17, 'V'), ('chai', 3, 19, 'V'), ('chamomile', 1, 7, 'H'), ('jasmine', 9, 11, 'H'), ('kettle', 2, 9, 'H'), ('steep', 3, 10, 'H')] )
Prints
soacbykymduioaaiylyf tghvnekCHAMOMILEzTfd argGfqavbKETTLEigEdv choNunnrviPEETSxzAfC jgbOrnnslrehucoqoPjH pcwLiewixggevzdxyOvA czpOmbclperkhlyezTtI wayOriouihiexqizxyrm jmgyfngsaioryztcysax ilrovurzcskENIMSAJny

Rubric

 
unknown Style Requirements
How your code is written.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown All functions are documented
Each function you define must include a non-empty documentation string as the very first thing in the function.
 
unknown Procedure Requirements
What code you use to solve the problem.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown Define printGrid
Use def to define printGrid
 
unknown Call print
Within the definition of printGrid, call print in at least once place.
 
unknown Define getColumns
Use def to define getColumns
 
unknown Use a loop
Within the definition of getColumns, use a for or while loop in at least once place.
 
unknown Use a return statement
Within the definition of getColumns, use return _ in at least once place.
 
unknown Define findHorizontals
Use def to define findHorizontals
 
unknown Use a loop
Within the definition of findHorizontals, use a for or while loop in at least once place.
 
unknown Use a loop
Within the loop within the definition of findHorizontals, use a for or while loop in at least once place.
 
unknown Use a return statement
Within the definition of findHorizontals, use return _ in at least once place.
 
unknown Define findVerticals
Use def to define findVerticals
 
unknown Use a loop
Within the definition of findVerticals, use a for or while loop in at least once place.
 
unknown Use a loop
Within the loop within the definition of findVerticals, use a for or while loop in at least once place.
 
unknown Use a return statement
Within the definition of findVerticals, use return _ in at least once place.
 
unknown Define findOrthogonalWords
Use def to define findOrthogonalWords
 
unknown Use a loop
Within the definition of findOrthogonalWords, use a for or while loop in at least once place.
 
unknown Call print
Within the loop within the definition of findOrthogonalWords, call print in at least once place.
 
unknown Call findHorizontals
Within the definition of findOrthogonalWords, call findHorizontals in at least once place.
 
unknown Call findVerticals
Within the definition of findOrthogonalWords, call findVerticals in at least once place.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown Define highlightWords
Use def to define highlightWords
 
unknown Use a loop
Within the definition of highlightWords, use a for or while loop in at least once place.
 
unknown Call print
Within the loop within the definition of highlightWords, call print in at least once place.
 
unknown Product Requirements
Your code's result values.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown getColumns returns the correct result
The result returned when your getColumns function is run must match the solution result.
 
unknown findHorizontals returns the correct result
The result returned when your findHorizontals function is run must match the solution result.
 
unknown findVerticals returns the correct result
The result returned when your findVerticals function is run must match the solution result.
 
unknown findOrthogonalWords returns the correct result
The result returned when your findOrthogonalWords function is run must match the solution result.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown findHorizontals returns the correct result
The result returned when your findHorizontals function is run must match the solution result.
 
unknown findVerticals returns the correct result
The result returned when your findVerticals function is run must match the solution result.
 
unknown findOrthogonalWords returns the correct result
The result returned when your findOrthogonalWords function is run must match the solution result.
 
unknown Behavior Requirements
What your code does from the user's perspective.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown findOrthogonalWords prints the correct output
The output printed when your findOrthogonalWords function is run must match the solution output.
 
unknown printGrid prints the correct output
The output printed when your printGrid function is run must match the solution output.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown findOrthogonalWords prints the correct output
The output printed when your findOrthogonalWords function is run must match the solution output.
 
unknown highlightWords prints the correct output
The output printed when your highlightWords function is run must match the solution output.