ECE264 Programming Assignment 4

Do you need a bigger moving truck?

You are going to be a software developer this summer. You want to carry everything with you.  You have packed all books, clothes, your computer, movie DVDs ... and put them into boxes. You plan to rent a truck to carry these boxes.  You want to rent the smallest truck because it is cheaper.  However, you are not sure whether the boxes can fit in the truck. Do you need a bigger moving truck?

In this assignment, each student is assigned to work with another student also taking this course.  The two-people group is to work on two programs: a solver which can generate a feasible solution to this problem, and a checker which can validate a given solution.

Purpose

This assignment asks you to develop a strategy to minimize the overall space occupied by discrete objects. "Discrete" means that you cannot cut a box 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?

In addition to the problem solver, you are also required to write a solution checker, which can tell if a given solution is valid, that is, whether it conforms all the rules listed below.

Rules

Your solver program must be named 'pa4'.  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.
• 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 must touch the x axis (y = 0).
  • At least one rectangle must touch the y axis (x = 0).
  • It is allowed that no rectangle touches the origin (0, 0).
• Input format: Each line represents a rectangle by four 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.

Your program may place the rectangles in any order, for example, the smallest first or the largest first.  Please ensure that the your program remembers the order of the rectangles and the output must follow the same order.  It is possible that some rectangles have the same width and the same height. You should keep all these rectangles.

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 that does not contain three integers, separated by one space.
• A line contains a negative number.
• Two or more rectangles overlap.

Output Format for Checker

Your checker program must be named 'pa4check'.  It takes two arguments, the original input file, and the name of the file that contains a solution to check (in order).  You may assume that the solution file always have correct format.  If the given solution is valid (does not break any rules stated above), the program prints the following information on the screen:

• The first line of the output is a string 'Sum of areas:' followed by the sum of the rectangles' areas, ended by a newline character '\n'.
• The second line is a string 'Area required:' followed by the area of the minimum rectangle at (0,0) covering all the rectangles in the given solution, ended by a newline character '\n'.

If the solution is invalid, do not print anything on the screen.  Your main function should return 0 whenever a solution is valid and 1 whenever invalid.

Grading

You are required to write two programs for this assignment, one is a solver and another is a checker.  The solver can generate a solution to the problem stated and the checker can check the validity of the solution.

Solver

A simple solution is given to you through svn in sourceforge (more information below).  Therefore, you should be able to generate valid solutions.  Please be aware that this simple solution produces low-quality results.

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

• Since it is easy to obtain valid solutions with low quality, the score is adjusted to award higher quality:
  • If the ratio is below 0.5 (wasting 50% or more space), you will receive 0.5.
  • If the ratio is above 0.5, you will receive (3 * ratio - 1).  This implies that if your program wastes no space at all (produces no hole), you will receive 2. 
• Twelve tests will be used. The top 6 scores are used to determine your grade (0.5 point for each test). The 12 tests contain 10, 30, 50, 70, 90, 100, 200, 300, 500, 800, 900, and 1000 rectangles.
• (0.5pt) You should explain your strategy, algorithms and data structures you've used for the solver with sufficient details in README.
• You receive at least 0.5 point if your program produces a valid solution for each test. Hence, your minimum score should be 3. If your program, however, generates invalid solutions, you will receive zero.
• Performance: Your program has to generate a valid output within 10 minutes for each test input.  You have one-minute no-penalty extension.  After 11 minutes, you will lose 20% for each additional minute. The minimum score is zero (you will not receive a negative score.)  Your program will be graded on a quad-core computer with clock speed of 1GHz or higher and memory of 1GB or larger (quad-core platform is available on 'qstructxx.ecn.purdue.edu' (xx=1~19) computers).
• How do we determine 10 minutes as the limit? There are about 60 students in the class. Each student takes 10 x 12 minutes for 12 tests. This requires 10 x 12 x 60 minutes = 120 hours. If we use six computers to grade, grading can finish in 20 hours.
• You will receive zero if the program cannot be compiled or linked.
• You will receive zero if the program crashes during execution.

Checker

• Five solutions containing indefinitely large number of rectangles will be used to test your checker.  Each test is worth 0.3 point.

Final Score

Your final score for PA4 is (score of Solver) + (score of Checker) - (Penalty).  Penalty will be applied if

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

in either solver or checker.

There is no score limit for this assignment.  The designed full score is 8 points, but you may receive a score more than 8.

Optimization Problems

This assignment is an optimization problem and 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.
• Onec 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.
• Theere 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.  Just in case you wonder, the life of the universe is estimated to be around 13 billion (10¹⁰) years.  You would be very very old if you waited for the answer. Moreover, this considers only whether to rotate each rectangle. You have not considered which rectangles should be adjacent. As another point of reference, the number of atoms on earth is estimated to be 10⁵⁰; 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 0.95 or better (i.e. wasting no more than 5% of area).

Suggestions

• You should use time wisely. Take advantage of the 10 minutes. Do not return bad results too early.
• When your program starts, set a timer that expires after 10 minutes.
• 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.

Bonus Points

The scoring formula already includes bonus points, if your program generates solutions whose qualities are above 0.5.  If your program never wastes any space (very difficult to achieve), you will receive 12 points for placement. This means 6 bonus points.  These bonus points will be added to your programming assignments and are not limited to the 10 points for class participation.

Available Material

A project has been establilshed at sourceforge.net. You can check out the software using the following command

svn co https://ece264s09pa4.svn.sourceforge.net/svnroot/ece264s09pa4 ece264s09pa4

You do not need an account at sourceforge to check out.  The project includes sample inputs/outputs and source codes for sample checker/solver as well as visualizer.  If you use the visualizer, please keep in mind that origin of the screen coordination is at upper-left corner, so the visualized layout is flipped vertically from the actual layout.

If you want to improve the code, you can commit changes. You need an account at sourceforge to commit.

What to Submit?

Please submit a zip file containing the following files:

• Necessary C source codes (*.c and *.h)
• Only one Makefile that generates two executable files named 'pa4'(solver) and 'pa4check'(checker) simultaneously when 'make' is called.
• README that explains your strategy, algorithms and data structures used in your solver program.

Files not listed above will be automatically deleted before the grading process takes place.

Extensions

This is not a part of the assignment.

• Which one is easier to program, the solver 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.