Python代写:CS110 2D Grid Algorithms



In this project you will continue to practice developing algorithms to solve problems and practice implementing them in the Python programming language. In particular, you will focus on 2D grids.


Log in to gemini and enter these commands to start the project:

start wordfind
cd ~/110/wordfind

This will copy the “skeleton program” to your account.

Next steps

Write a set of functions that solves the problem of finding words in a grid. These are like word search puzzles.

The primary function is wordfind. It takes two parameters: a grid of lower-case single-letter strings, and a list of lower-case words. For each word, find it in the grid, if possible. If found, then for each letter comprising the word in the grid, change the letter to its capitalized version. wordfind returns the number of words that were found. Words can occur in any of the 8 directions. They can also overlap in one or more letters. A word will only occur once in the puzzle.

For example, if we begin with a grid:

j m w e
e e p p
q o x u
w w e d
w g j o

and a list of words [‘meow’, ‘wed’, ‘do’, ‘justice’], the wordfind function modifies the grid:

j M w e
e E p p
q O x u
w W E D
w g j O

and returns 3. No output is produced.

You can (and should!) break this problem into smaller secondary helper functions. Hint: one of those functions should do a case-insensitive match. You can use the .lower() string method to convert to lower case.

What to hand in

Submit your work using the course submission procedure. In this case it is

cd ~/110/wordfind
submit wordfind

This will collect the file. We will only be testing your wordfind function.

Evaluation Criteria

Your work will be evaluated according to criteria in two general categories, style and correctness. Each category counts for half of your grade. For this assignment, the criteria are:

  1. Style
    • The header (large docstring at the top) contains all the appropriate information: your name, the name of the file, etc; and that the program description is accurate and complete,
    • The logic (approach to solving the problem) is clear and reasonably simple,
    • Variable names are descriptive, that is, they accurately describe the values they name,
    • Commenting is accurate and complete, and
    • The horizontal and vertical spacing effectively enhances the structure of the program.
    • The program is efficient and avoids redundant computations. If the same calculation is used twice, it is better to do it once and store the result in a variable.
    • No variables are unnecessary. A rule-of-thumb is that a variable is necessary only when it names an important part of the logic, or when it is used in the logic more than once after it is assigned.
    • The program makes appropriate use of functions. Your program should be composed of several functions.
    • The program uses simple and clear algorithms that are general and scale well.
    • You use appropriate citations for the work of others (TA’s, web sites, etc.) at the location in the program that the citation applies.
    • “Magic” numbers are avoided. Obvious literals like 1 and 0 are fine, but other numbers should be named by variables for clarity in the logic.
  2. Correctness
    • The submission system will evaluate how well your program passes the automatic tests.