| | Problem Description
You are in charge of aerial fire fighting over an expanse of land. Some of that land has trees (T), some is clear grassy area with minimal growth (G), and some is water (W). Additionally, there are several cabins (C) dotted across the land. As is often the case in the forest, however, sections of trees sometimes catch fire (F), which can quickly spread to nearby areas. Your job is to stop these fires from spreading, and protect the cabins and trees as best as possible.
Today, you only have a single fire fighting plane available for service. It is your job to direct the plane on where to go. Several cells in the northwest corner of the map represent the starting location of your plane at the service airport (S). Your plane starts at the northwest corner of the map (0,0), with a full tank of water. Whenever the plane flies over water, it will automatically scoop up 1 unit of water per cell, until it is filled to capacity. However, you must manually dictate when water should be dumped from the plane. Dumping (one unit of) water over a burning cell immediately extinguishes any fire, and completely cools the cell. Dumping water over a cell that is heating up, even if it has not yet caught fire, still completely cools the cell.
Cells with grass, trees, or cabins, that are adjacent to fire (to the North, South, East or West) begin to heat up at a rate proportional to how many sides are surrounded by fire. Thus, an area surrounded on only one side will heat up at a rate of one per unit time, while an area surrounded on all four sides heats up by four per unit time. Once a tree exceeds maxHeat, it will immediately catch fire. Cabins are more flammable, and will catch fire once their heat exceeds maxHeat / 2. Grassy areas will only catch fire if their heat exceeds maxHeat * 2.
Of course, cells will not burn forever. After burnTime units of time have elapsed for a tree on fire, the fire will burn itself out, no longer heats up surrounding areas, and cannot catch fire again. An area which has been doused with water, however, may catch fire multiple times until it completely burns out, in which case the time spent burning is cumulative. Grassy areas only burn for burnTime / 2, while cabins will burn for burnTime * 2.
Your code will be called exactly once, and should return a String indicating the movements (N, S, E, W) to be made by your plane. A 'D' character following any move indicates that water should be dumped after moving. Each movement takes exactly one unit of time. Dumping water happens simultaneously, and thus does not use up additional time. If your plane has no water in its tank at the time, nothing will happen, and no error is generated. Beyond that, any invalid characters in the return value will result in a score of 0 for the test case. The return string may be no longer than the total size of the board; for example, a 20x20 map can have a return value up to 400 characters long. After your plane has completed its movement sequence, the simulation will continue until any remaining fires (including any resulting from fire spreading) burn out.
Scoring
Your score for a test case will be based upon the proportion of trees that are burned, and the proportion of cabins that are burned. For purposes of score calculation, burned means having completely burned the cell. If trees is the proportion of trees left unburned, and cabins is the proportion of cabins left unburned, then the score = 1000000 * trees * cabins * cabins. When counting cells, we only consider those that were not on fire at the start of the simulation.
For example, if an area has five cabins, of which one burns, and exactly half of the trees are burned, then score = 1000000 * (1/2) * (4/5) * (4/5) = 320000.
Total score will be calculated using relative scoring, that is, it will be based on Sum of (my_score_for_testcase / best_score_anyone_has_for_testcase). This total will be scaled to 1000000, that is, a total score of 1000000 indicates a competitor who has the best score of anyone on all test cases.
Test Case Generation
- burnTime = Random[5 - 12] * 2
- maxHeat = Min(Random[3 - 10] * 2, burnTime - 2)
- size = Random[10 - 49]
- tankCapacity = Random[size/2 - 3*size/2]
- Set all cells where 2 >= x + y to 'S'.
- waterSeeds = Random[0 - size/5) + 2
- Pick waterSeeds random cells to set as 'W'. (Any selections where 2 >= x + y are discarded without re-selecting.)
- forestSeeds = Random[0 - size/4) + 3
- Pick forestSeeds random cells to set as 'T'. (Any selections where 2 >= x + y are discarded without re-selecting. Trees may replace water in this step.)
- buildRemain = Min(cellCount * 2 / 5 + Random[0 - cellCount / 5), cellCount - 10 - waterSeeds - forestSeeds)
- For each buildRemain, pick a random grass cell that is adjacent to either a Tree or Water, and set it to the same as the adjacent cell. (If a cell is adjacent to both, make it a tree.)
- Pick locations that will become cabins and/or fires:
- Each grass or tree cell is given a weight of 1.0.
- A location is randomly chosen proportional to the weight of each cell.
- After each location is chosen, all cells have their weight multiplied by (1-1/sqrt(r)), where r is the Euclidian distance from the location just chosen. (eg. 0,0 and 3,4 are a distance of 5 apart.) This multiplication is cumulative after multiple locations have been chosen.
- min = cellCount / 200 + 1, max = min(cellCount / 50, 25)
- cabinCount = Random[min - max]
- fireCount = Random[min - max]
- The first cabinCount locations chosen above are set to 'C', and the next fireCount locations are set to 'F'.
Simulation Details
Simulation progresses in the following way:
- Move the airplane in the specified direction, picking up water if the new location is over water.
- Dump water over the new location, if requested and there is water in the tank.
- Advanced the burn progress of any cells on fire, possibly with them burning out.
- Calculate any cell heating, based on fires that still remain.
A visualizer is available here. Please see the visualizer code for more details on case generation, and the simulation details.
|
