Crossword

Write some Python functions to work with crosswords.

Background

Figure 1. Crossword grid (source: Michael J, Wikimedia)

A crossword is a game in which a player fills in a two-dimensional grid of characters with words, based on clues about the meaning of these words. Words can either be filled in across (left to right) or down (top to bottom), and when "across" words intersect with "down" words, they must use the same character(s). For example, here is yesterday’s "mini" crossword from the New York Times:

■

Requirements

You will implement three Python functions that could form part of a crossword game. These three functions should:

provide a string representation of a crossword grid
search a crossword grid for a specific letter
check whether or not a word fits in a grid

In all three of these functions, a crossword grid is represented by a list of lists, where the top-level list contains rows and each row is a list of string values. Each string in a row can be a letter in a word, an empty string (for a blank space) or a black square character ("■", ordinal 9632) for "blocked out" squares.

For example, the grid above would be represented as:

[["■", "A", "D", "S", "■"],
  "P", "L", "A", "N", "T"],
  "J", "O", "N", "A", "H"],
  "S", "U", "C", "K", "Y"],
  "■", "D", "E", "E", "■"]]

If that puzzle was still being played (i.e., not all words had been filled in yet), it might look like:

[["■", "A", "D", "S", "■"],
  "P", "",  "A", "N", "T"],
  "J", "",  "N", "A", "H"],
  "S", "",  "C", "K", "Y"],
  "■", "",  "",  "",  "■"]]

Details

You should implement three (or more!) Python functions according to the descriptions below. Submit your work in a file called crossword.py.

As always, please don’t hesitate to contact me if you have questions! Also as always, remember that assignments are individual work.

String representation

Turn a grid into a string that can be displayed to the user. This should involve, at minimum, putting different rows on different lines (i.e., separated by the newline character "\n"). You can go further than that if you like (e.g., adding lines in between columns with the "pipe" character |), but you don’t have to. You are free to use a space or an underscore (or a Unicode box character, or…) to represent an empty space.

def grid_string(grid):
    """Converts a crossword grid to a string.

    This function should not directly print anything.

    Parameters:
    -----------
    grid : list of lists of strings
      An n x n crossword grid, represented by a list of rows,
      where each row is a list of strings.

      Each string in a row can be a letter in a word, an empty string
      (for a blank space) or a black square character ("■", ordinal 9632).

    Returns:
    --------
    str
      A human-readable string representation of the crossword grid.
    """

Find a letter

Find all instances of a letter within a grid. If the letter doesn’t appear, return an empty set.

def find_letter(grid, letter):
    """Find instances of a letter in a crossword grid.

    Parameters:
    -----------
    grid : list of lists of strings
      An n x n crossword grid, represented by a list of rows,
      where each row is a list of strings.

    letter : string
      A string containing a single letter (i.e., len(letter) == 1).

    Returns:
    --------
    set of co-ordinate tuples
      A set of co-ordinates where the letter was found. Each co-ordinate
      is given as a tuple, where (0,0) is the top-left of the grid
      at row 0 and column 0, (3,5) is row 3 and column 5, etc.
    """

Check a word’s fit

This function should check to see a word can fit in an existing grid with the existing letters. For example, given the following grid:

■

the word DANCE will fit down from row 0 and column 2, but the word DUNCE will not. The word HAT will fit across from row 0 and column 1, but the word GLAD will not.

def check_fit(grid, word, location, direction="across"):
    """Check whether a word fits in a grid.

    Parameters:
    -----------
    grid : list of lists of strings
      An n x n crossword grid, represented by a list of rows,
      where each row is a list of strings.

    word : str
      A word to try and fit into the grid.

    location : tuple
      A (row,col) tuple describing the starting location of the word

    direction : str
      Either "across" or "down"

    Returns:
    --------
    bool
      Whether or not the word fits in the grid in the given location.
    """