ECE 264 Spring 2011

Become a Packing Expert

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

Motivation

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

If you have moved from one apartment to another, you will probably understand the challenge. Sometimes, you may see spare space but no remaining box can fit in the space. When this happens, you can keep the space (and need another trip) or rearrange the boxes to eliminate the wasted space.  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?  How do you schedule classes? Different classes have different sizes (numbers of students) and there are many classrooms. Can you fit all classes into existing classrooms, or you need to construct another building (very expensive)?

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.

Stages

This assignment is divided into three stages

1. sort rectangles by their widths, heights, or areas
2. detect whether a list of rectangles and their placements have overlaps
3. place rectangles as tight as possible

Rules

To simplify the problem, we consider only 2-dimensional rectangles of different sizes. The width and the height of a rectangle must be positive integers.

• 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). However, in determining the minimum area, we assume that the lower left corner starts at (0, 0).
• Input format: Each line represents a rectangle by two integers (separated by single spaces) in the binary (not ASCII) format
  

       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. This is the first stage of the assignment.
• output format: Each line must have three integers (separated by one space) and nothing else in ASCII format
  

       x y r

  The x and y values are the coordinate of the upper left corner (using computer coordinate) 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.

An example of a valid Solution	An example of an invalid solution (overlap)

Inputs

Your program takes two or three arguments:

Two arguments

argv[1] is a string. Use

	if (strcmp(argv[1], "sw") == 0)

to determine whether argv[1] is the same as "sw"

Three arguments

argv[2]: widths and heights of rectangles

argv[3]: placement (x y r)

Please remember that the input files are in the binary format but the output is in the ASCII (i.e., text) format.

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/S2011 purdue-wl-ece264-assignment-read-only

The project contains:

• generator: generate many random rectangles
• reader: read the rectangles created by the generator
• sampledata: files of rectangles created by the generator
• time: use timer. The timer expires after a cerain amount of time

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 ipa2. The file name must be Makefile.
• This program must be named "ipa2" (in Makefile).
• README that explains your strategy, algorithms and data structures used in your program. The file name must be README.
• Create a single zip file. Do not include object files, executable files, sample input, or sample output in your package.

Submission Procedure

You must submit through this web site. This is the only way to submit your exercises and programming assignments. 

You need to provide a user name and a password through Blackboard before submission.  The user name and the password are different from your Purdue career account.

Requirements

In this assignment, your program is allowed to read the file only once. The program must not use rewind or fseek.  Obviously, the program cannot call fopen-fclose and fopen again.  Moreover, your program does not know how many rectangles there are inside a file, the program must use dynamic data structure (linked list). When the program reads data from the file, it should allocate memory as necessary in this format

	while (not end of file)
	{
            allocate memory
            read from the file
            store the data into the allocated memory
	}

The program cannot allocate a very large array regardless of the number of rectangles in the file. For this assignment, you have to use a (or more) linked list.

Memory Management

Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.

Compiler Warnings

You must remove all warning messages reported by gcc -Wall -Wshadow. You will use 0.3 point for each warning message.

Syntax Error

You will receive zero if your Makefile cannot produce an executable called "ipa2".

Run-Time Error

You will receive zero if your has a run-time error (such as "Segmentation Fault").

Stage 1 (3 points)

The output is a list of numbers as the order of the rectangle.  Suppose the input file (after reading from the binary file) contains 4 rectangles

4 2
3 9
7 5
1 6

• If argv[1] is "sw", the output should be

3 2 4 1

because

• The first rectangle's width is ranked the third.
• The second rectangle's width is ranked the second.
• The third rectangle's width is ranked the fourth.
• The fourth rectangle's width is ranked the first.

Please be careful not to make a common mistake and report 4 2 1 3 because "The smallest width is the fourth rectangle."

• If argv[1] is "sh", the output should be

1 4 2 3

because

• The first rectangle's width is ranked the first.
• The second rectangle's height is ranked the fourth.
• The third rectangle's height is ranked the third.
• The fourth rectangle's height is ranked the second.

Do not to make a common mistake and report 1 3 4 2 because "The second smallest height is the third rectangle."

• If argv[1] is "sa", the output should be

2 3 4 1

If two rectangles have the same height, width, or area; they should be sorted with respect to their location in the input file.  For example, if the rectangles are   

2 4
3 5  
2 7
1 5
15 1

• If argv[1] is "sw", the output should be

2 4 3 1 5

because

• The first rectangle's width is ranked the second because it appeared first in the file.
• The second rectangle's width is ranked the fourth.
• The third rectangle's width is ranked the third.
• The fourth rectangle's width is ranked the first.
• The fifth rectangle's width is ranked fifth

• If argv[1] is "sh", the output should be

2 3 5 4 1

because

• The first rectangle's height is ranked the second.
• The second rectangle's height is ranked the third because it appeared first in the file.
• The third rectangle's height is ranked the fifth.
• The fourth rectangle's height is ranked the fourth.
• The fifth rectangle's height is ranked first.

• If argv[1] is "sa", the output should be

2 4 3 1 5

Your output should be in ASCII format. There is one and only one space between two adjacent numbers. The last number should not have a space after it.  Add a new line ('\n') after printing the last number.

If you want to check whether your program can handle large examples correctly, manually sorting many numbers could be tedious.  Consider to use sort program in Linux.

We will use 12 test cases for grading.

Stage 2 (2 points)

Valid Solution 1

Suppose the first input file (widths and heights) is

4 2
3 9
7 5
1 6

The second input file (i.e. the placement file, in binary format) is

	0 0 0
	4 0 0
	7 0 0
	14 0 0

This placement put the rectangles from left to right side by side. There is no overlap and the output (ASCII) is 1 (i.e., valid).

Valid Solution 2

Another valid placement is

	3 5 0
	0 0 0
	3 0 0
	3 7 1

Invalid Solution

If the second input file is

	3 5 0
	0 0 1
	3 0 0
	3 7 1

The second and the third rectangles overlap because the second rectangle (its height is larger than its width) has rotated. The output (ASCII) should be 0 (i.e., invalid).

We will use 10 test cases for grading.

Testcases

You can find a couple of  testcases. The solution of the first testcase is 1 and the solution to the second testcase is 0.

You can find the testcases used for grading.  The solutions are 1 1 0 0 0 1 1 1 1 0.

Determine Overlap

Suppose A and B are two rectangles. They do not overlap if one of the following condition is true:

1. A's left edge is to the right of B's right edge.
2. A's right edge is to the left of B's left edge.
3. A's top edge is below B's bottom edge.
4. A's bottom edge is above B's top edge.

If none of the four condition is true, the two rectangles overlap.

Stage 3 (5 points)

The output of your program should have the same x y r format, written to an ASCII (text) file. For example,

	0 0 0
	4 0 0
	7 0 0
	14 0 0

This solution needs an enclosing rectangle of 15 (width) x 9. The total area is 135. The sum of all rectangle's areas is 8 + 27 + 6 + 35 = 76.

Another valid solution is

	3 5 0
	0 0 0
	3 0 0
	3 7 1

The enclosing rectangle is 10 (width) x 9 = 90.

To write to a file, you need to use something like

FILE * fhd = fopen (filename, "w");
fprintf(fhd, "%d %d %d\n", x, y, r);

Please remember to close the file before the program ends. 

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

The quality of the first solution is 76 / 135 = 0.56. The quality of the second solution is 76 / 90 = 0.84. The second solution is better.

To encourage you to create a really good algorithm, we will use a nonlinear formula to calculate your score:

If your program produces a perfect solution (Quality = 1), you will receive 1.7, namely 0.7 bonus point.

• Five tests will be used. They will have at least 64 and at most 1024 rectangles.
• Each of the five 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 five 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 5 points.
• 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 and you will receive zero for that test.
• 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? As a point of reference, the number of atoms in the universe is estimated to be 10⁸⁰. Hence, 10²⁵⁰ is a really large number. Suppose you can create and compare 1,000,000 solutions each second, it will take more than 10²⁵⁰ years.  It is estimated that the age of this universe is only 10¹⁰ years. 
• 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 waste no more than 10% 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.