Project 2: Cookie Cutter

The Unique Cookie Company has thought up a remarkable marketing gimmick. Every bag of cookies contains $n$ identical cookies, but no two bags of cookies contain cookies with the same shape. Thus every customer gets a set of unique cookies!

To support this endeavor, the U.C.C. has purchased a Highly Sophisticated Robot that can automatically configure the cookie shape on the fly. The H.S.R. can cut arbitrary polygonal shapes with up to twelve sides. Since the U.C.C. wants each packet to contain the same weight of cookies, the H.S.R. will be configured to cut cookies of a fixed area $a$.

The robot is positioned over a sheet of dough that is one unit wide, of constant thickness, and of arbitrary length. The robot can translate and rotate the cutter to make cuts at arbitrary places on the dough surface subject to the following constraints:

• The cookie boundary should not cross the edge of the dough, or the edge of a previous cookie.
• In order to keep all cookies of a given shape together, a vertical partition is inserted just after the final cookie for that shape. Cookies for the next shape may not cross the vertical partition.

The following picture shows the basic idea with $n=5$. The H.S.R. first needs to cut out five copies of the 9-sided cookie which it does (without rotation) in space Length1. The dotted line is the vertical partition. Following the partition, the H.S.R. cuts out 5 copies of the 5-sided cookie in space Length2, this time using rotation.

=6in    

Various production costs are proportional to the length of dough needed to cut the cookies. Thus, the U.C.C. would like to minimize the average length of dough needed for the production of a batch of $n$ cookies.

Your job in this project is to program the H.S.R. to cut cookies in a way that minimizes the length of dough required. Your program will need to take a polygonal shape as input, and derive a placement of $n$ polygons satisfying the constraints mentioned above. We will provide software that generates random polygons of a given area, and software to verify that a placement is correct. The placement must be correct 100% of the time in order to merit a score. The score will be equal to the average length used for the set of inputs given. The precise format for the inputs and outputs will be specified later.

We'll run a tournament at the end of the project, using some standard cookie shapes, some randomly generated shapes, and some shapes that you haven't seen before. You should also think yourselves about designing cookie shapes that will provide interesting tests of your programs.

Some initial things to think about:

• What should you do if $a$ and $n$ are both small enough that you can line all the cookies up against the left boundary?
• Is there something special you can do for triangles?
• What kind of polygon is likely to be the ``worst-case'' shape, always requiring a large length?