Programming Project 4

This semester you will be writing a program that models elements of recognizing and creating characters. Optical character recognition is an important area of research that allows photographs or printed documents to be digitized; by doing so, these documents are made available for machine-based searching. On the flip side, http://en.wikipedia.org/wiki/CAPTCHA is a system for differentiating between humans and computers: the goal here is to generate a non-machine readable image that a human could identify. CAPTCHA helps reduce the amount of spam on the Internet.

We will implement a highly limited type of image matching, processing, and creation this semester. Rather than write this project at once, we will break the project down into several two-week sub-projects that are due throughout the semester. The rest of this document will detail the first such assignment.


This third assignment will ask you to write some code that will help you determine if a pixel is part of a number. You will complete two functions available in the template file for project4_template.py. You should save that template file under the name project4.py. You will also need to copy your project 3 solutions into the same directory where you save this file.

You will have to do four things for this assignment:

Step 1: Writing Test Cases
Ideally, you should write your test cases before you write your code. In doing so, your test cases will all initially fail (because you haven't written any code), but that's fine. So, next we're going to explain what the two functions above are supposed to do, and then we'll explain how to format your test cases so you can run them on Marmoset, and how you can run these test cases on code you will write.

We're going to expand the create function in project3.py to create numbers for three, four, and five. Below are some examples of various shapes to help you identify the correct formulas for this function:


create(3,3,"three") would return [1, 2, 3, 5, 6, 7, 8, 9]
 X   X   X 
     X   X 
 X   X   X 


create(3,4,"three") would return [1, 2, 3, 5, 6, 9, 10, 11, 12]
 X   X   X 
     X   X 
         X 
 X   X   X 


create(4,3,"three") would return [1, 2, 3, 4, 7, 8, 9, 10, 11, 12]
 X   X   X   X 
         X   X 
 X   X   X   X 


create(4,4,"three") would return [1, 2, 3, 4, 7, 8, 12, 13, 14, 15, 16]
 X   X   X   X 
         X   X 
             X 
 X   X   X   X 


create(5,5,"three") would return [1, 2, 3, 4, 5, 10, 13, 14, 15, 20, 21, 22, 23, 24, 25]
 X   X   X   X   X 
                 X 
         X   X   X 
                 X 
 X   X   X   X   X 




create(3,3,"four") would return [1, 3, 4, 5, 6, 9]
 X       X 
 X   X   X 
         X 


create(3,4,"four") would return [1, 3, 4, 5, 6, 9, 12]
 X       X 
 X   X   X 
         X 
         X 


create(4,3,"four") would return [1, 4, 5, 6, 7, 8, 12]
 X           X 
 X   X   X   X 
             X 


create(4,4,"four") would return [1, 4, 5, 6, 7, 8, 12, 16]
 X           X 
 X   X   X   X 
             X 
             X 


create(5,5,"four") would return [1, 5, 6, 10, 11, 12, 13, 14, 15, 20, 25]
 X               X 
 X               X 
 X   X   X   X   X 
                 X 
                 X 



create(3,3,"five") would return [1, 2, 3, 4, 5, 6, 7, 8, 9]
 X   X   X 
 X   X   X 
 X   X   X 


create(3,4,"five") would return [1, 2, 3, 4, 5, 6, 9, 10, 11, 12]
 X   X   X 
 X   X   X 
         X 
 X   X   X 


create(4,3,"five") would return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
 X   X   X   X 
 X   X   X   X 
 X   X   X   X 


create(4,4,"five") would return [1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 16]
 X   X   X   X 
 X   X   X   X 
             X 
 X   X   X   X 


create(5,5,"five") would return [1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25]
 X   X   X   X   X 
 X                 
 X   X   X   X   X 
                 X 
 X   X   X   X   X 

The X characters indicate when that tile would be occupied by a colored pixel (as opposed to a white pixel). Your function will return a sorted list of tiles corresponding to the colored pixels in the shape. You may assume that the function will only be called with the numbers one through five, and the width and height will both be at least three, and will both be integers.

You should use the append(...) function to add an element to a list. For example, if you've declared a list called result, you can append the number 3 to with with result.append(3). You may also use the sorted function to sort a list; if result stores [8, 6, 7, 5], sorted(result) would return [5, 6, 7, 8].
You will write a function called draw that takes as arguments a width, height, letter, and number, and returns a string representation of the number with the letter representing the color of each pixel.

For example, draw(4,3,"X","one") will return the string '   X\n   X\n   X\n'. Note that the \n stands for the newline character.

We will guarantee that draw will only be called with valid numbers (one through five), widths and heights that are integers that are at least three, and letters that are exactly one character long.
You will write a function called soften that takes as arguments a two dimensional, 3x3 grid, and counts the number of tiles in the grid, excluding the center, that are not blank (blank tiles are represented by a space). This function could be used to decide whether or not to soften a set of pixels when processing an image, depending on how many neighboring pixels are colored. For this project, the function will simply return an integer corresponding to the number of non-underscore pixels in the grid.

For example, soften([[' ','X',' '],[' ',' ',' '],[' ',' ',' ']]) would return 1.

We will guarantee that the function is called with only 3x3 grids, and each element in the grid is a single character.

Now you should be ready to write test cases for your code, once you understand what arguments each function is expecting, and what it will return and when. For this project, we will expect your test cases to be written to a file called tests.txt (right mouse click and save the file - do not try to click on it in your browser and copy the contents - you will miss the newline at the end). The example shows you the format for one test case of create. Each test case is two lines long: the first line contains the name of the function, followed by a space, followed by all of the arguments to the function, each separated by a single space, and terminated by a newline. Then, on the next line, you should provide the expected answer for that function call, terminated by a newline. Make sure your answer, which is a list, has a single space after each comma (this is how lists are printed in python). Also make sure that your inputs to the draw function, which are lists, do *not* have spaces in them - the driver uses spaces to tokenize the input, so you can't have spaces in your lists that are arguments. In your tests, make sure you include spaces where they need to be, and make sure to include a newline (blank line) after your last test case.

You should write at least 50 cases, and up to 300, for this project. This should not take very long, as each test case is just two lines long.
Step 2: Writing Code
Once you have written your test cases, you can begin to write your code for the project in the files project3.py and project4.py (and remember the link to the template for this file above).

You will need the return statement to get your functions to return a value - DO NOT use the print statement for this!


Step 3: Testing Your Code on Your Test Suite

Please log in again to view this part of the page.



Step 4: Testing Your Code on Our Test Suite
Once you've written your code and tested it on your test suite, check to see that it passes our release_tests.txt by saving that file to the same directory as your other files, and choosing y when you run the driver.
Project Hints and Guidelines

Remember, when designing your own test cases, try to do so in a thoughtful and structured approach, as we have done in class. What is the smallest possible image you could call your functions on? What is the next smallest one? What are all the corner cases?

Like for assessments, you should not hard-code solutions to work for the release tests; when writing your code, pretend you don't have the release tests. Your code should work for any possible valid test inputs.