Instructions for wordSearch

Click here to toggle highlighting for goal links

Overview

In this task, you will practice nested loops by implementing part of 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.

For example, here is a list of words

cs111, science, center, wellesley, python, computer, nested, loops

that are hidden in the following puzzle. Can you find them?

d s b o s i d d e c x r

u k o p c e n t e r x v

p x k f i m n r h o j x

y e l s e l l e w q s j

t h o e n j k t z u n k

h a o q c i d u a u s 1

o k p p e d l p a y 1 w

n e s t e d n m a 1 h j

s n k p l g v o s f t j

c m w p u l l c d z p l

It's easier to see the placement of the hidden words if we replace all characters not in the hidden words by dashes:

- - - - s - - - - - - -

- - - - c e n t e r - -

p - - - i - - r - - - -

y e l s e l l e w - - -

t - o - n - - t - - - -

h - o - c - - u - - - 1

o - p - e - - p - - 1 -

n e s t e d - m - 1 - -

- - - - - - - o s - - -

- - - - - - - c - - - 

In a traditional word search puzzle, words can be hidden vertically, horizontally, or diagonally. They can also be backwards in any direction. To simplify things, in this task your program will search only for words that are oriented horizontally forward or vertically downward. It will not search for words oriented horizontally backward, vertically upward, or diagonally in any orientation.

For example, in the above puzzle, your program will find the horizontal words center and nested and the vertical words python, loops, and science, but it will not find wellesley, computer, or cs111. (Your program could be expanded to find these other words as well, but that is beyond the scope of this task.)

Grid Representation

In this problem, two-dimensional text grids are represented as a list of strings of the same length. Each string represents one row of the grid, and the length of each row string is the number of columns. For example, the above CS puzzle is the value of the variable TEST_PUZZLE in wordSearch.py:

TEST_PUZZLE = [
    "----s-------",
    "----center--",
    "p---i--r----",
    "yelsellew---",
    "t-o-n--v----",
    "h-o-c--u---1",
    "o-p-e--p--1-",
    "nested-m-1--",
    "-------os---",
    "-------c----"
]

The words placed in this puzzle are the value of the variable TEST_WORDS:

TEST_WORDS = 
    "cs111",
    "science",
    "center",
    "wellesley",
    "python",
    "computer", 
    "nested", 
    "loops"
]

As noted above, your program is not expected to find the words "wellesley", "computer", or "cs111". In this puzzle.

The starter code includes a function wordPuzzle.generatePuzzle that generates random word search puzzles from a list of words to hide in the puzzle. To find out more, see the section on Word Puzzle Generation at the end of these instructions.

Functions to Define

Note that as usual, you must include a docstring for each function you define.

Part A: Printing the puzzle grid

Your first goal is define a function printGrid that displays the text grid for the word search puzzle. It takes a single argument, which is a list of strings, where each string has the same length (the number of columns in the grid). It uses print to display the letters in the grid such that

• there is a single space after every letter
• there is a blank line after each row of letters

These printGrid examples demonstrate how it should work.

Notes:

• Recall that the newline character '\n' causes a printed string to move to the next line.

• Calls to print normally end with a newline, but this can be overridden by the keyword argument end. E.g., print('hello', end=' ') will display the five characters in hello followed by a space rather than a newline.

• Your printGrid function must use a nested loop

• You can test printGrid and the other wordSearch functions by running the file test_wordSearch.py.

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, define a function getColumns that takes a list of row strings as a parameter, and return a list of column strings, where the cth column string is the characters of the cth column of the given row strings.

For example, getColumns( ["abcd", "efgh", "ijkl" ] ) should return the list of column strings ["aei", "bfj", "cgk", dhl"].

These getColumns examples give more examples how it should work.

getColumns basically flips the the orientation of the grid across the diagonal that goes from the upper left to the lower right, causing input columns to become output rows and input rows to become output columns. In mathematics, this operation is known as a transposition when applied to grids.

Notes:

• Make sure your function works with different puzzle sizes!

• You can test getColumns and the other wordSearch functions by running the file test_wordSearch.py.

Part C: Finding horizontal words

Define a function findHorizontals(rows,wordlist) that finds words in wordlist that are hidden in the puzzle in a forward horizontal orientation.. The first parameter, rows, is a list of strings representing the puzzle text grid, and wordlist is a list words (strings) hidden in the grid.

This function returns a list of location entries that indicate which words were found horizontally and where. Each location entry is a tuple with 4 components:

1. The word that was found;
2. The string 'H', to indicate the word was found horizontally;
3. The row (an integer, starting from 0) where the forward horizontal word starts.
4. The column (an integer, starting from 0) where the forward horizontal word starts.

For example, for the findHorizontals(TEST_PUZZLE, TEST_WORDS), the resulting tuples should be:

[('center', 'H', 1, 4), ('nested', 'H', 7, 0)]

because 'center' appears horizontally in TEST_PUZZLE at row 1 and column 4 and 'nested' appears horizontally at row 7 and column 0.

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

Notes:

• The tuples should be ordered so that the found words have the same relative order as the words in wordList.

• To find the first index at which a word appears as a substring in a row string, you must use Python's .find method on strings which returns this index (or -1 if the word is not found). For example:

  • 'concatenate'.find('cat') => 3
  • 'rationalization'.find('tion') => 2 # index for 1st of 2 matches
  • 'concatenate'.find('dog')=> -1

• findHorizontals is required to use a nested loop.

• You can test findHorizontals and the other wordSearch functions by running the file test_wordSearch.py.

Part D: Finding vertical words

Define a function findVerticals(rows,wordlist) that finds words in wordlist that are hidden in the puzzle in a downward vertical orientation. As in findHorizontals, the first parameter, rows, is a list of strings representing the puzzle text grid, and wordlist is a list words (strings) hidden in the grid.

This function returns a list of location entries that indicate which words were found vertically and where. Each location entry is a tuple with 4 components:

1. The word that was found;
2. The string 'V', to indicate the word was found vertically;
3. The row (an integer, starting from 0) where the downward vertical word starts.
4. The column (an integer, starting from 0) where the downward vertical word starts.

For example, for findVerticals(TEST_PUZZLE, TEST_WORDS), the result tuples should be:

[('science', 'V', 0, 4), ('python', 'V', 2, 0), ('loops', 'V', 3, 2)]

because 'science' appears vertically in TEST_PUZZLE at row 0 and column 4, 'python' appears vertically at row 2 and column 0, and 'loops' appears vertically at row 3 and column 2.

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

Notes:

• The tuples should be ordered so that the found words have the same relative order as the words in wordList.

• In this function, you should not loop over wordList or rows and should not call the string .find method. Instead, you should leverage the fact that most of the work of findVerticals can be accomplished by calling findHorizontals on the grid that results from calling getColumns on rows. After all, getColumns converts columns to rows, so why not take advantage of findHorizontals for finding words in these columns-as-rows?

  • For this reason, you must call getColumns and call findHorizontals in the body of findVerticals.

  • The tuples returned by findHorizontals aren't quite right, but you should use a mapping pattern loop (or a list comprehension) to convert these tuples to be the correct tuples for findVerticals.

• You can test findVerticals and the other wordSearch functions by running the file test_wordSearch.py.

Part E: Finding words in either orientation

Define a function findWords(rows,wordlist) that finds words in wordlist that are hidden in the puzzle either in a forward horizontal or a downward vertical orientation.. As in both findHorizontals and findHorizontals, the first parameter, rows, is a list of strings representing the puzzle text grid, and wordlist is a list words (strings) hidden in the grid.

This function returns a list of location entries that indicate which words were found vertically and where. Each location entry is a tuple with 4 components:

1. The word that was found;
2. The string 'H' if the word was found in the forward horizontal direction or 'V' if the word was found in the downward vertical direction.
3. The row (an integer, starting from 0) where the first character of the word is located in the grid.
4. The column (an integer, starting from 0) where the first character of the word is located in the grid.

These location entry tuples must be ordered so that the found words are sorted alphabetically.

For example, for findWords(TEST_PUZZLE, TEST_WORDS), the result tuples should be:

[
  ('center', 'H', 1, 4),
  ('loops', 'V', 3, 2),
  ('nested', 'H', 7, 0),
  ('python', 'V', 2, 0),
  ('science', 'V', 0, 4),
]

because 'science' appears vertically in TEST_PUZZLE at row 0 and column 4, 'python' appears vertically at row 2 and column 0, and 'loops' appears vertically at row 3 and column 2.

These findWords examples provide more demonstrations of how findVerticals must work.

Notes:

• The body of this function should be very simple, involving combining the results of callingfindHorizontals and findVerticals.

• Use the sorted function to sort the location entry tuples. No fanciness with a key argument is required.

• You can test findWords and the other wordSearch functions by running the file test_wordSearch.py.

Word Puzzle Generation

The starter code includes a function wordPuzzle.generatePuzzle that generates random word search puzzles from a list of words to hide in the puzzle. If you're interested, you can use this function to generate other puzzles to experiment with. wordPuzzle.generatePuzzle takes four arguments:

1. the number of rows for the puzzle (defaults to 10)

2. the number of columns for the puzzle (defaults to 20)

3. a list of words to hide in the puzzle (defaults to a list of words related to tea).

4. a boolean that indicates whether all words should be hidden only in the forward and downward orientation. If True, the orientation will be restricted to forward and downward; if False, the orientation can be any direction, including backward, upward, and diagonally.

By default, generatePuzzle produces a 10x20 text grid with a list of tea-themed words hidden within it, and where all hidden words are forward or downward. However, you can supply parameters to change the default parameters. For instance, to create a puzzle with 5 rows, 10 columns, and some coffee-themed words that can be in any orientation, you could call:

wordPuzzle.generatePuzzle(
        numRow=5, numCols=10, 
        words=["latte","espresso", "bean", "mocha"], 
        onlyForwardOrDownward=False
)

wordPuzzle.generatePuzzle returns a tuple with three values:

1. a list of numRows strings, each of length numCols that represents the rows of a text grid
2. a list of the words in words that were successfully placed in the puzzle
3. a list of the words in words that were not able to be placed in the puzzle.