Next: Project 3: Marriage Market Up: W4444 Programming and Problem Previous: Project 1: Socks
This project is motivated by a recent experience I had as a new grandfather. We purchased two separate sets of materials to construct a baby enclosure. The two sets were from the same manufacturer, but contained pieces (walls, gates) of strangely different sizes. One set had several wall lengths including walls with 13 rungs, for example, while the other had walls with 14 rungs. While each set was designed for a small enclosure, we wanted to put them together to make a larger enclosure. We succeeded, but only after some pen-and-paper design effort.
In your project, you have acquired a variety of walls and gates from different sources, with no guarantee that there will be a balanced number of components of any particular size. Walls come in lengths that are integer unit lengths, with the smallest possible length being 5 units. (A unit is about 4 inches for our set.) A gate is a special kind of wall with internal segment that can open and close.
Walls and gates can be joined with connectors. You start with a fixed collection of connectors that you can use in your construction. The three types of connectors correspond to three joining angles: 180 degrees (straight), 90 degrees (right angle), 135 degrees (45 degree turn from straight). These connectors can be used in either orientation, so that internal angles of 270 degrees and 225 degrees are possible.
You will be given a polygon describing the shape of the room footprint within which the enclosure must fit. The room polygon may be non-convex, but it will not have “holes”. Your goal is to build an enclosure that fits within this polygon, and is complete, i.e., the “last” piece of the wall connects back to the “first” piece. An enclosure must have at least one gate. Every linear face of the enclosure must be no longer than 30 units. A linear face may include several walls joined by 180-degree connectors. Very long linear segments are unstable, and must be avoided. Your solution will need to specify the exact position of the first wall within the room polygon, and the simulator will verify whether your baby enclosure fits within the room polygon. (The method to check enclosure containment will be exposed by the simulator so that your player can check the enclosure and avoid surprises.)
You will also receive in advance a set of weights that describe the criteria by which the prospective parents will judge your solution. A correct solution according to the required criteria will receive a baseline score of 1000 points. A positive weight A will be multiplied by the area of your solution and added to your score, so bigger is better. A negative weight C will be multpilied by the perimeter of your solution and added to your score, since more/longer pieces means a bigger price tag. A nonnegative weight G will be added to your score if there is a second gate on a different face of the enclosure from the first gate. Thus some parents might prefer to have a second gate.
The generation of an incorrect solution will incur a score of -1000 points. The simulator will have a built-in tolerance for small floating-point rounding errors, so your final point and your initial point on the enclosure should be within that tolerance. It is OK for your code to not generate a solution: sometimes you might not have the pieces to make a valid solution. When your code generates no solution, it will get a score of 0 points.
Some initial things to think about: