The goal of this assignment is to get you started reading and writing Python code. You’ll understand how to use existing code, call existing functions, write your own functions, and call functions you’ve written. This work is not harder than what you’ve been doing in your exercises, but it will take substantially longer, so start early. Make sure you read this entire document all the way through at least once before you start.
You can complete this assignment using only the material covered in the first four weeks of the course. In particular, you are not allowed to use any loops (there is no good reason to use them in this assignment!), and do not use string and/or list methods.
A crossword puzzle is a rectangular grid of letters that contains specific words that go on the grid horizontally left to right and vertically top to bottom. The rules are:
- Two words that go in the same direction, cannot have characters sitting in neighbor positions.
- Any two (or more) words can cross each other if and only if they run in perpendicular directions, and if and only if the character where they do cross each other, is the same.
We will represent a crossword in a Python program puzzle as a list of strings, one string for each row of the puzzle, using the blank space character to occupy positions that do not contain other puzzle characters. For example, the correct puzzle above, may be represented as follows:
["PYTHON ", " E ", " S ", " STRING", " I ", " N ", " G "]
We will think of it as a rectangular grid of characters, as follows:
PYTHON E S STRING I N G
We are going to number rows and columns of characters that make up the grid as follows:
0123456 0 PYTHON 1 E 2 S 3 STRING 4 I 5 N 6 G
For example, the character Y is located in the intersection of row number 0 and column number 1.
We add word in a crossword puzzle in the horizontal or vertical direction by respecting the rules described in the previous section. If we start with an empty puzzle, and want to add the word PYTHON horizontaly at the position (0,0) (that means the word will occupy six characters of the row 0, starting from column 0 and ending at column 5). Since the puzzle is empty, we do not break any rules, so we can simply make progress by moving from one character of the grid to the next, and writing one character each time. Please note if we move horizontally, the row number remains constant, and the column number increases each time.
Now let’s attempt to add the word TESTING in vertical direction. Obviously we cannot staring adding this word starting from the position (0,0) because the character present in this position is P, whereas the first character of our word is T. We cannot start adding the word TESTING staring from, say, (1,1); if we do so, we would vertically read YTESTING which is not a word at all!
If we check the position (0,2), we see that the letter T fits nicely. Next we must check the position below this letter; it can be obtained from (0,2) by incrementing the row and keeping the column constant. Namely, that position is (1,2). We observe that this position is available; the grid character located in this position is a space, and also the characters to the left and to the right of it are also spaces. This means it is safe to add the letter E in the position (1,2). Of course, we can keep checking each subsequent position on the grid, and conclude we are able to add the word TESTING. Once we are convinced that we can add it, we obviously proceed to do so.
At the top of the file are some comments. Please read those comments now, and complete the header… go on… I’ll wait here.
Complete the docstring and write the code for a function named is_empty that takes as parameter a string, which is a single (may be empty) character, and returns a boolean value, True if and only if the value of the parameter is the empty string or the string composed of a single space character.
Write the code for the function char_left according to the docstring provided in the starter code. Please note the puzzle, width and height are global variables, i.e. you can access them in any of your functions.
Complete the docstring and write the code for a function named char_right that takes as parameters two integers, a row number and a column number, and returns the character to the right of the position (row, col) from the global variable puzzle.
Complete the docstring and write the code for a function named char_above that takes as parameters two integers, a row number and a column number, and returns the character above the position (row, col) from the global variable puzzle.
Complete the docstring and write the code for a function named char_below that takes as parameters two integers, a row number and a column number, and returns the character below the position (row, col) from the global variable puzzle.
Write the code for a function named fit_char_horizontalaccording to the provided docstring. Please note this function returns True if and only if the character described by the formal parameter c can be written as a horizontal continuation of a word in the puzzle.
Write the code for a function named fit_char_verticalaccording to the provided docstring. Please note this function returns True if and only if the character described by the formal parameter c can be written as a vertical continuation of a word in the puzzle.
Complete the code in the function put_word wich actually puts a word in the puzzle.
We have included a file called typechecker.py that runs each of your functions and checks that the type of the return value is correct. Again, you don’t have to understand this code (I wouldn’t expect you to at this stage), you just have to put it in the same directory as your a1.py file and run it.
This file serves 2 purposes, first it calls your functions, so you can be sure that they are named correctly (if they aren’t it will crash). Secondly it checks the type (not the value, just the type) of each function’s return, so you know if you’ve at least got that part right. If there is anything wrong, you will see an error message. If the types are correct, nothing will happen, except a single print statement.
This doesn’t mean that your function works (for example, replacing any of the boolean functions with just the line return True will still pass the type checker, but it’s a good first test. You will still want to test your code further.
You may use doctests by simply running your a1.py (and maybe changing the global variables puzzle, width, height accordingly).
You may also run the provided cwpuzzle.py; feel free to change it if you want to experiment with various crossword puzzles (in fact you are encouraged to do so!).
Please note testing is a very important component of software development; no matter how careful you are when you program, chances are that you will make mistakes and testing is the only process that will reveal your programming errors (of course, if you test properly).
Your assignment will be marked for correctness. This means that your code must do exactly what is described in this handout and starter code. In addition, we strongly encourage you to consider the following criteria as you work on this assignment - paying attention to these will help you as we progress through the course!
- Formatting style: Make sure that you follow PEP-8 style guidelines available at this link: https://www.python.org/dev/peps/pep-0008/.
- Programming style: Your variable names should be meaningful and your code as simple and clear as possible.
- Commenting: be sure to include accurate and complete docstrings in your functions. Follow the design recipe we have been using! In addition, include internal comments for pieces of code that aren’t trivial.
- Code re-use: you should have as little duplicated code as possible. If you find yourself repeating code, there’s a good chance you could find a simpler (lazier) method.
- One more time… this will be marked by an auto-marker. So if your file or one of your functions is named incorrectly, you won’t get any marks for that component of your work.
Submit a1.py on MarkUs. Your file must be named exactly as given here (check that MarkUs says you have submitted all required files after you’re done submitting). You do not need to submit typechecker.py or cwpuzzle.py.
Before you submit:
- Ensure that you have read & added your name and login to the header at the top of the file
- Test your code for PEP-8 compliance
- Run the type checker and make sure it gives no errors
- Re-test all examples