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 or vertically, not diagonally.

For example, in the above puzzle, your program will find the horizontal words center, nested , and wellesley and the vertical words python, loops, computer, and science, but it will not find cs111.

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 word `"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 matrices.

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 findHorizontal(rows,word) that finds a single word that is hidden in the puzzle in a horizontal orientation. It should find words both in the forward and backward direction. The first parameter, rows, is a list of strings representing the puzzle text grid, and word is the word to find hidden in the grid.

This function returns a list of positions that indicate where the target word was found (note there might be more than one copy of it). Each location entry is a tuple with 2 components:

1. The row (an integer, starting from 0) where the word was found.
2. The left-most column (an integer, starting from 0) of the word. For forwards words, this is the position of the first letter; for backwards words this is the position of the last letter.

When there are multiple matches, they should be ordered according to their row and then column values (matches in earlier rows first, and within a row, matches in earlier columns first).

For example, for the findHorizontal(TEST_PUZZLE, 'center'), the resulting list of tuples should be:

[(1, 4)]

because 'center' appears horizontally in TEST_PUZZLE once at row 1 starting in column 4.

If instead we had the grid:

selfish = [
    '-meme',
    'me---'
]

and we ran findHorizontal(selfish, 'me') we should get the following list of matches (without the commentary):

[
    (0, 1),  # first 'me' in row 0. Row 0 comes before row 1.
    (0, 2),  # start of backwards 'em' that's part of 'meme'
    (0, 3),  # second 'me' in row 0
    (1, 0),  # the 'me' in row 1 (second row)
]

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

Notes:

• If a word matches both forwards and backwards starting at a particular location (e.g., 'racecar'), we only count that as one match. Because of this, it is not possible for this function to ever return a list containing duplicate positions.

  • A strategy of looking leftwards from an index for a backwards match isn't a good one beacuse of this. Looking rightwards for letters in reverse order is better.

• If the word is not found anywhere in the grid, return an empty list.

• findHorizontal must use a nested loop.

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

• To count as a match, the letters of a word must appear next to each other in the correct order (or exactly backwards). Letters that are spaced out with other letters in between don't count as a match, even if they all appear in the right order.

Part D: Finding words from a list in either orientation

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

This function returns a list of location entries that indicate which words were found and where. Note these are not the same as the positions findHorizontals returns. Each location entry is a tuple with 3 components:

1. The word that was found;
2. The row (an integer, starting from 0) where the top-left-most character of the word is located in the grid.
3. The column (an integer, starting from 0) where the top-left-most character of the word is located in the grid.

These location entry tuples must be ordered as follows:

1. They respect the order of words in the words list, so matches for words earlier in the list come before all matches for later words.
2. Within matches for a word, all horizontal matches come before all vertical matches, regardless of locations.
   • Within horizontal matches, they're ordered by row, then column, just the way findHorizontal orders them.
   • Within vertical matches, they're ordered by column, then row, just the way findHorizontal will order them when applied to columns instead of rows.

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

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

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

Notes:

• To find vertical matches, you can simply apply findHorizontal to columns instead of rows. Use the getColumns function you wrote earlier to get the columns. Your code must call getColumns at least once and must call findHorizontal at least twice.

  • Note that when you do this, you will need to swap the row & column numbers in the result since finding a "horizontal" word in "row 1" of the getColumns result really means you found a vertical word in column 1 of the actual puzzle.

• If you order your loops correctly, no extra code is necessary to achieve correct ordering of the final result list.

• 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.