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:

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:

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:

2016-10-24