Introduction to Computer Science for Multidisciplinary Studies (CPSC 217) Assignment 3 of 4

University of Calgary Department of Computer Science

Introduction to Computer Science for Multidisciplinary Studies (CPSC 217) Assignment 3 of 4

This assignment is to be completed individually and is due on March 22, 2015. Submit your solution as a single Python source code file (i.e., a “.py” file) Upload your submission to the “Assignment 3 of 4” dropbox in D2L.
Your source code must be commented. Uncommented submissions will be penalized.

Your .py file must be named with your last name, student number, and “Assignment3”, separated by underscores. e.g., Collier_12345678_Assignment3.py

For this assignment you will create a program that will load a “ppm” puzzle image file specified, by name, by the user, and display it on the screen. While it is on the screen, if the user clicks on an individual piece it will be saved to a file and then removed from the image (i.e., painted over in black). To clarify, if the user loads “flamingo- puzzle.ppm” and clicks on the top center “piece” in the puzzle image below…

…that piece should be removed from the image and saved to a separate file. Although it is not necessary to “crop” the newly separated piece (as has been done in the image below), the user must be allowed to continue selecting additional pieces for removal, and every piece removed should be saved (using a function call to savePPM) to a separate file.

University of Calgary Department of Computer Science

Introduction to Computer Science for Multidisciplinary Studies (CPSC 217) Assignment 3 of 4

(continued)

A large part of this assignment is working out “how” to accomplish this task, and you are strongly encouraged to apply a divide-and-conquer approach and create a flowchart (or some descriptive pseudocode) for your design – if you end up seeking assistance on this assignment, from either your TA or your instructor, you will be asked to show this preliminary work.

You should start by examining the file “flamingo-puzzle.gif” that has been uploaded to D2L (and notice that the only black pixels in the image are on the borders between puzzle pieces), so part of your approach should be checking to see on which pixel the user has clicked and whether or not that pixel is black. If it is a black pixel then it isn’t a puzzle piece (i.e., it is a part of the border), but if it isn’t black and the user clicks on it, you should remove it from the image (storing it in a separate image) and then remove any other non-black pixel that it is in contact with, and all the non-black pixels that those are in contact with, etc.

To accomplish this component you should research “flood filling”. The Wikipedia article at “http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations” is an excellent starting point, specifically the first “Alternative Implementation” reproduced below:

Flood-fill (node, target-color, replacement-color):
1. If target-color is equal to replacement-color, return. 2. Set Q to the empty queue.
3. Add node to the end of Q.
4. While Q is not empty:

5. Set n equal to the last element of Q.

6.  6.      Remove last element from Q.
   

7. If the color of n is equal to target-color:
8. Set the color of n to replacement-color and mark “n” as processed.
9. Add west node to end of Q if west has not been processed yet.
10. Add east node to end of Q if east has not been processed yet.
11. Add north node to end of Q if north has not been processed yet.
12. Add south node to end of Q if south has not been processed yet.

Please note that a Python list (and, more simply, two Python lists – one for x co-ordinates and one for y co- ordinates) can be used in place of the “queue” mentioned above, and Python has the append and pop functions for adding and removing items from the end of a list, respectively. Adapting this algorithm for your own use is an example of the related-problem approach to problem solving but please note that a straight implementation of the algorithm above will not be able solve the problem – you will still need to figure out how to use this to solve the problem.

You are welcome to create your own puzzle images for this assignment using the “puzzle-maker.py” program provided on D2L. If you do so and you submit them on D2L they may be shared with the class so please make sure you only use images that you make yourself or that belong to the public domain.