Programming Project 3

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 second assignment will ask you to write some code that will help you determine if a pixel is part of a number. You will complete one function available in the template file for project3_template.py. You should save that template file under the name project3.py.

You will have to do two 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 function above is supposed to do, and then we'll explain how to format your test cases so you can get credit for them on Marmoset, and how you can run these test cases on code you will write.

We're going to write a function to create numbers of various sizes. The create function will take as arguments a width, height, and number, and returns a list of all the tile numbers that make up that number of that size. Recall, on our images, pixels are labeled starting with 1 at the top left corner.
For this project, we will ask you to implement create to handle the numbers one and two up to any arbitrary size. Below are some examples of various shapes to help you identify the correct formulas for this function:


create(3,3,"one") would return [3, 6, 9]
         X 
         X 
         X 


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


create(3,4,"two") would return [1, 2, 3, 5, 7, 10, 11, 12]
 X   X   X 
     X     
 X         
 X   X   X 


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


create(4,4,"two") would return [1, 2, 3, 4, 6, 7, 9, 13, 14, 15, 16]
 X   X   X   X 
     X   X     
 X             
 X   X   X   X 


create(5,5,"two") would return [1, 2, 3, 4, 5, 10, 12, 13, 14, 16, 21, 22, 23, 24, 25]
 X   X   X   X   X 
                 X 
     X   X   X     
 X                 
 X   X   X   X   X 


create(10,10,"two") would return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 42, 43, 44, 45, 46, 47, 48, 49, 51, 61, 71, 81, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
 X   X   X   X   X   X   X   X   X   X 
                                     X 
                                     X 
                                     X 
     X   X   X   X   X   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 and two, 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].

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). Make sure to include a newline (blank line) after your last test case.

You should write at least 5 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 file project3.py (and remember the link to the template for this file above).

This problem is mathematically very simple, and can be solved with just addition/subtraction, multiplication/division, and modulus, if-else statements, and loops.

Where do you start writing your code? Pseudocode! First, you will want to think of some mathematical formulas or rules for determining when a tile is part of a shape, and when a tile is on a certain row or column. The examples above should be sufficient for you to figure out these formulas.

You will also have to use if-else statements. 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?