ECE 264 Spring 2010

Individual Programming Assignment 4

Become a Packing Expert

A fancy rectangle packing solution (Courtesy of ernop, http://fuseki.net/rect/)

Have you ever moved from one place to another? Have you ever hesitated about how large packing boxes you should buy, or how big trucks you should rent? Now is the time for your ECE264 knowledge to help you avoid excessively large boxes or trucks and save some money!

Purpose

This assignment asks you to develop a strategy to minimize the overall space occupied by discrete rectangular objects. "Discrete" means that you cannot cut an object into smaller pieces.

If you have moved from one apartment to another, you will probably understand the challenge. Sometimes, you may see a hole but no remaining box can fit in the hole. When this happens, you can keep the hole (and need more space) or rearrange the boxes to eliminate the hole.  This problem occurs everyday in many applications.  If you are operating a delivery company, space is money! If you cannot fit the boxes, you need another truck, ship, or plane and this dramatically increases the cost.  This problem is also important if you try to arrange furniture in your house or pack your suitcase before a trip.  This problem is also important for a web browser. Many web pages contain images, videos, commercials ... How does the browser arrange (lay out) the information so that little space is wasted?

Rules

Your program must be named "ipa4".  This program takes only one argument which is the name of an input file.

To simplify the problem, we consider only 2-dimensional rectangles of different sizes.

• All rectangles will be arranged in the first quadrant (x >=0, y >= 0).
• All rectangles must be included. Adding or removing rectangles is not allowed.
• Two rectangles can touch but they cannot overlap.
• The final area is the minimum rectangle that can enclose all rectangles. One of this rectangle's corner is at the origin (0,0). Hence, it is advised that your program makes
  
  • at least one rectangle touch the x axis (y = 0);
  • at least one rectangle touch the y axis (x = 0).
  • Note: it is allowed that no rectangle touches the origin (0, 0).
• Input format: Each line represents a rectangle by two integers (separated by single spaces):
  

       width height

  The rectangles are not ordered in any way. If you want to sort the rectangles by widths, heights, or areas, you have to do that inside your program.
• output format: Each line must have three integers (separated by one space) and nothing else.

       x y r

  The x and y values are the coordinate of the lower left corner of the rectangle. There is no parentheses in the output. The values of x and y must be zero or positive. The value of r indicates whether the rectangle should rotate. If r is 0, the rectangle does not rotate. If r is 1, the rectangle rotates by 90 degrees, i.e., its width and height switched. The value of r can be only 0 or 1. Any other value is an error. Please notice that there are no identifiers for the rectangles; hence, the rectangles in your output must be in the same order as the input.

Invalid Outputs

Your program will receive zero if the following conditions occur. Please be aware that this list may not be complete.

• The output has a different number of lines from the input.
• A line does not consist of three integers, separated by one space.
• A line contains a negative number.
• Two or more rectangles overlap.

Code

A project has been created for you with a sample structure.  Please check out the code by using the following command on a UNIX shell:

svn checkout http://purdue-wl-ece264-assignment.googlecode.com/svn/trunk/2010/IPA4 purdue-wl-ece264-assignment-read-only

The project contains:

• The partial source code for a solution checker (in "checker" subdirectory)
• A simple solution that generates valid but poor-quality outputs.  Demonstration of using timer is also included in the same file. (in "sample" subdirectory)
• Test cases that will be used for grading, for your self-testing purpose.

What to Submit?

Please submit a zip file containing the following files:

• Necessary source code (including all .c and .h needed to generate the final executable).
• Makefile to create the executable. Name the executable as ipa4. The file name must be Makefile.
• README that explains your strategy, algorithms and data structures used in your program. The file name must be README.
• Pack all above files into one zip package. Do not include object files, executable files, sample input, or sample output in your package.

Files not listed above will be automatically deleted before the grading process takes place; grade penalty may be applied meanwhile.

Late Policy

This assignment is due at 10:59AM on 4/20 (Section 1)  2/18 (Section 2).

• Before the deadline, you can submit and resubmit as many times as you wish. You will receive the grading result soon after submission. If you submit multiple times, your score is the highest among all submissions.
• The time is determined by the server's clock, not your watch.
• You must submit early. Sometimes the Internet can be slow. If you wait until a few minutes before the deadline, it is very likely that you will miss the deadline. Another common mistake is submitting wrong files when the deadline is too close.
• Do not send your assignment by email because it is late. Email submission is ignored.
• Every assignment has a no-penalty extension of 5 hours. The extension is not a new deadline. The extension is provided to accommodate unexpected problems, such as slow network. The extension should be sufficient for you to come to school and submit an assignment, if your home computer breaks.
• If Purdue cancels classes on a submission deadline, the deadline is extended to one day after classes resume.
• If the server is down within 12 hours of the deadline, the deadline will be extended by 24 hours.

Policy Handling Dishonest Behavior

You will receive F in this class if you cheat. Your case will always be reported to ECE main office. There is no exception. If you help a student cheat (such as giving your code), you will also receive F. If you want to help a classmate, tell the person to talk to the instructor or the teaching assistants.   You are responsible protecting your assignments. Do not leave a computer unattended. Do not throw away the printout of your programs.

Do not copy code from your classmates or from the Internet.

You are allowed to use the code given to you by the instructor or generated snippets using the tools approved by the instructor. You are not allowed to download code from the Internet and claim the code as yours. If you discover useful code, you must (1) announce the code in Blackboad Discussion so that everyone in the class is aware of the code or (2) request the instructor's written approval or (3) describe with sufficient details where the code comes from and how you use it in your README file. You must request the code owner's permission to use the code and you must cite the source in your submission. You are not allowed to purchase code from, for example, getacoder.com.

There were cases when students claimed they "accidentally" submitted code from the Internet because these students were "studying" the code. In all these cases, the students were considered cheating and received appropriate penalty.  It is not possible to "accidentally" submit the code that is not written by you.If it is your code, you must have spent many hours writing the code. You will treat the code with the greatest care. You will check, double check, and check again before submission. If you have spent so much time on an assignment, you will not accidentally submit wrong code.  "Accidentally submitting wrong code" is an invalid defense and you will receive F in this class.

You should know that advanced tools are available checking programs' similarities. These tools can detect programs of similar structures, even if you rename variables or change for to while (or many other techniques to disguise). These tools have successfully detected many cheating cases.  The very fact that you consider to cheat indicates your lack of programming skills. Hence, you do not have sufficient knowledge to defeat these similarity checkers. If you need help, please talk to the instructor or the teaching assistants, or post your questions in Blackboard Discussion. Do not ask your classmate or anyone that took this course to give code to you.  The submissions from multiple semesters will be checked.

Grading

• For each test input, if your program generates a valid output, the score is calculated using this formula:

  

  The maximum possible score for a single test case is 1.5, when the packing solution is perfect.
• Twelve tests will be used. The top 6 scores are used to determine your grade. The 12 tests contain 10, 30, 50, 70, 90, 100, 200, 300, 500, 800, 900, and 1000 rectangles.
• Each of the 6 scores will be rounded up to 2 decimals (e.g., 0.764 will be rounded to 0.77). The final grade is the sum of the 6 scores, rounded up to 1 decimal (e.g. 4.56 will be rounded to 4.6).
• Good news: you can get a total score of more than 6 points for this assignment! (Maximum score is 9.)
• For each test, if your program generates an invalid solution, you will receive zero for that test case.
• Performance: Your program has to generate a valid output within 1 minute for each test input. After 1 minute, your program will be forced termination.
• You will receive zero for this assignment if the program cannot be compiled or linked, or for whatever reason the desired executable "ipa4" is not generated after running "make".

Penalty

• compiler warnings  (0.5 for each warning message)
• memory leak is detected  (up to 2 points)

Properties of the Problem

This assignment is an optimization problem which has the following properties:

• Finding a valid solution is easy. You can make the first rectangle touch the x and y axes, then put the second rectangle on the top of the first, the third on the top of the second, ....  This is a valid solution. Arranging 1,000 rectangles needs to read the rectangles and put them side by side. This can be done within a second. Since the rectangles have difference sizes, the easy solution probably wastes too much space.
• Once you have a solution, it is easy to validate the solution by checking whether any two rectangles overlap.
• Once you have a solution, it is easy to quantify the quality using the formula shown above. Hence, if you have two solutions, deciding which one is better is easy.
• There are many valid solutions. Finding all possible solutions and selecting the best is impractical. If you have 1,000 rectangles and rotations are allowed, you have 2^1,000 ways to determine whether each rectangle should rotate. How big is this number?  Suppose you can create and compare 1,000,000 solutions each second, it will take more than 10²⁵⁰ years.  As a point of reference, the number of atoms in the universe is estimated to be 10⁸⁰. Hence, 10²⁵⁰ is a really large number.
• If you have a solution, it is difficult to determine whether it would be possible to find a better solution. Maybe your current solution is the best. Maybe it is not.
• It is also difficult to determine whether it would be possible to find a solution that achieves a score of 1 or better (i.e. wasting no more than 33% of area).

Suggestions

• You should use time wisely. Take advantage of the 1 minute. Do not return bad results too early.
• When your program starts, set a timer that expires within 1 minute (e.g. 55 seconds).
• Find one valid solution quickly and store the result. Use the available time to find better solutions.
• When the timer expires, print the best solution you currently have.
• You should make your solutions "correct by construct". Avoid finding solutions, checking whether they are valid, and discard invalid solutions. Your program is likely to waste too much time checking.
• You need a strategy. Do not try random arrangements. They are unlikely to improve your score much.
• Understand that a valid answer is better than no answer.  You will receive some points if you produce valid answers within the time limit. If your program produces no answer within the given time, you receive no point.

Extensions

This is not a part of the assignment.

• If you are to write a checker program that validates the output of your original program, which one is easier to program, the original  program or the checker?  Which one of them takes longer time to produce the result?  Is the answer trivial?
• Can you estimate how much space (percentage) is saved by allowing rotation?
• One may claim that the full score is not possible because there is always wasted space. Can you prove whether this claim is right?  Can you describe the condition that cause wasted space?
• Another student says the full score should be given to the answer in which the wasted space cannot be further reduced. Given an answer, can you prove that the area is the minimum and it is impossible to reduce the wasted space?
• You can extend the problem to more complex shapes such as shown below. Instead of calling them boxes, we call them pieces now. Each piece includes one or several squares arranged in different ways.  The first row shows the pieces of one, two, or three squares. The second row shows the pieces of four squares. The next two rows show the pieces of five squares. You can rotate, move, and mirror, the pieces but you cannot break any piece. This problem is more difficult because you need to consider their shapes to avoid holes.