Project 1: Pentocity

You have bought a large tract of land, and are developing it for residential and industrial building. Traditional methods of land development would require you to subdivide the land into plots in advance, before seeing what kinds of plots people might want. In this project we'll try to see if we can do better by dynamically developing the tract of land in response to demand.

The land is modeled as a 50x50 grid of cells. A cell can contain one of several types of development, and several contiguous cells can be used to place larger structures. The main structural elements are:

• Residences. These contain 5 contiguous cells, and are one of the 18 possible pentomino shapes (reflective symmetry doesn't apply here).
• Factories. These contain up to 25 cells, and are always rectangular, with between 1 and 5 cells on each side.
• Roads. Road cells must be adjacent to the perimeter of the development, or must be connected via a sequence of orthogonally adjacent road cells to the perimeter.
• Water. A contiguous group of four or more water cells is considered a pond.
• Park. A contiguous group of four or more park cells is considered a field.

At the start of the simulation, the development is a blank slate. A sequence of requests to build residences or factories (i.e., buildings) of particular shapes arrives one at a time -- you don't see ahead to future requests. Most of the time you will agree to build the building, and place it on the development somewhere. At all points in time, the development must satisfy the following constraints:

• Every building must have at least one cell orthogonally adjacent to a road. This may mean that to place a building you may additionally need to place a number of additional road cells to meet this constraint. (Remember that road cells must connect with the perimeter.)
• The footprint of the building must be previously empty. You are permitted to rotate the building in order to place it.
• Factories and residences may not be immediately adjacent to one another. But factories can be adjacent to other factories, and residences to other residences.
• A residence that is placed adjacent to a field achieves a bonus (see below) because the purchaser can see that the value of the property is higher. The bonus is achieved only if the field is present at (or before) the time the residence is placed. Adding a field later does not achieve a bonus for existing adjacent residences.
• A residence that is placed adjacent to a pond achieves a bonus in the same way as a field (see below).

You score one point for each cell of a building that is placed. So residences always score 5 points, and factories score a variable number of points. Fields and ponds that are adjacent to a newly placed residence each yield a 2 point bonus for that residence. A residence that is adjacent to two fields (or two ponds) gets just one bonus, while a residence adjacent to a field and a pond gets two bonuses.

You have the option to reject a building request, but after three rejections, the simulation ends. Even if you do a good job of building placement, eventually you will run out of room and be forced to reject requests. Your goal is to have as many points as possible when the simulation ends.

The distribution of shapes in the request sequence is not necessarily uniform. In fact, it may be deliberately nonuniform, to test the robustness of your strategy. We'll provide a variety of sequence generators, and allow you to specify your own for experimentation. For the tournament at the end of the project, we'll use a variety of generators, some of which you will have seen, and some of which will be new.

Things to think about:

• What kinds of placement give you the most flexibility for later buildings?
• You get to choose the shapes of roads, fields and ponds. What are good shapes?
• What does it take to achieve a ``robust'' strategy?