South Central USA Regional Programming Contest

Problem #2: Manifest Destiny

Introduction

A group of colonists has landed on an uncharted island, looking for that special place to stop and settle. Unfortunately, there are already natives on the island, and now it's a race to see who will be able to survive. In order to settle, a group must find food. The settlers have not learned the arts of agriculture yet, so they will invariably eat all the food and have to move on. If any groups encounter each other, they will fight to the death, since resources are scarce. Your job is to determine who will be alive or dead at the end of N turns and where they are on the island.

The island is a rectangular A x B matrix. Each square is either water, fields, or mountains. Settlers or native groups can only be located on fields (they can neither swim nor climb). Wheat grows in certain locations on the fields and is the only source of food for the groups.

Each group is assigned an identifier and has a certain number of people in it. During each year (or turn), the surviving groups (those with one or more people alive) will perform an action. The group with the lowest identifier goes first, followed by the next lowest, until all groups have had their "turn." A group can only do one of the actions listed below. To determine which action a group does, they try to do the first action. If unable to do that action, the group will try the second action, and so forth until it finds an action that it can perform. Note that a group will always be able to do one of the following actions each turn:

If a group is adjacent to another group, they will attack (in the case of multiple adjacent tribes, the tribe will attack the first tribe it finds in a clockwise search starting at the northern square).
If a group is adjacent to wheat, then the group will eat it and not move (if multiple wheat terrain squares are adjacent to the group, the wheat eaten will be the first encountered using a clockwise search starting from the terrain square to the north of the group). The wheat eaten will be reduced by the number of people in the group. If there are more people in the group than wheat, the next group of wheat in the clockwise search pattern will be eaten until either there is no more wheat in an adjacent terrain square or the total number of wheat units consumed equals the size of the group. Once wheat is completely consumed, the square that the wheat was in should be considered as a normal field.
If a group was not adjacent to any wheat at the beginning of their turn, the group will search for food by moving one square to the North, East, South, or West (see below for moving requirements). If the group is unable to move, it will stay in its current location.

At the end of each group's turn, the number of people in the group and anything they might have encountered is recalculated based on:

If the group ate this turn, the group will grow by 33% (rounded up) of the people that were able to eat. 5% (rounded up) of the people that did not eat will die due to starvation.
If the group attacked another tribe, the group will kill an amount of people equal to its 'strength.' A group's strength is equal to 50% (rounded up) of its population. Because they are not eating while fighting, 10% (rounded up) of the group will die after the fighting is finished. Note that only the group attacking does damage; the other group will have to wait until its turn to retaliate, if it is able to.
If a group moved to another square, 10% (rounded up) of the people in the group will die due to starvation and the rigors of travel.

NOTE: When rounding, round the amount that will be added or subtracted from the group. Only use the cardinal points (N,S,E,W) when determining if a group is adjacent to something.

Movement: Whether a group is comprised of settlers or natives, moving on the island is highly ritualized. Each group follows a set of rules to determine which direction to move in order to find the perfect place to stop and make a (brief) home:

Each group remembers where it has been and determines which direction to go based on a point system. Points will be recalculated each turn as follows:
- Assign each area adjacent to the group (considering cardinal directions only) a number of points equal to the number of times the group has entered that square. Note that if a group moves to and stays in a single square for multiple turns, it has only entered the square once. Starting the simulation in a particular terrain square also counts as entering that square once.
- Groups loath to turn around and go back the way they came, thus the last visited area shall be worth double the points calculated from above.
The group will move in the direction with the lowest points. In case of a tie, the group will give priority to the tied direction appearing first in this list: North, East, South, West.

Since water and mountains are impassible, do not consider moving to terrain squares containing them!

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

Start line - A single line, "START N", where N is a positive integer in the range 1 <= N <= 100 which indicated the number of years that must be calculated.
Starting Map - A map showing the starting position. The map consists of a set of A lines, each describing B terrain squares. Note that the actual size of the A x B map is not given within the input set but will be in the range 1 to 20 inclusive. The terrain squares in each line are separated from one another by a single space, and each terrain square is a pair "identifier number." The identifier may be one of:
The number is an integer in the range [0,999], inclusive. It is only meaningful for groups (detailing how many people are left in that group), or wheat (which is the amount of wheat remaining).
End line - A single line, "END"

Output

For each data set, there will be exactly one output set, and there will be a single blank line separating output sets.

A single output set consists of a series of lines, "GroupID Size Position YearDied", displayed in increasing order of GroupID, where:

GroupID - The group's identification number.
Size - The size of the group at the end of N years.
Position - The position, "(X,Y)" of the group at the end of N years. Where X indicates the column and Y the row, with (0,0) being the most North-West terrain square (the first terrain square in the first line of the StartingMap).
YearDied - The year (or turn) in which this group died (size fell to 0), represented by a positive integer. If the group is still alive at the end of N years, this field will not be output.

Sample Input

START 5
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
W 000 W 000 . 000 . 000 2 060 . 000 w 345 W 000
W 000 . 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 1 140 . 000 . 000 0 050 . 000 . 000 W 000
W 000 W 000 . 000 M 000 M 000 . 000 . 000 W 000
W 000 W 000 w 200 M 000 M 000 . 000 3 025 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 w 115 w 115 . 000 . 000 W 000
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
END
START 3
. 000 2 100 . 000 . 000
0 100 1 050 . 000 . 000
. 000 . 000 . 000 . 000
. 000 . 000 . 000 . 000
END

Sample Output
0 0 (4,2) 2 1 57 (4,1) 2 43 (5,1) 3 31 (6,2) 0 72 (1,0) 1 0 (1,1) 1 2 72 (3,1)

The statements and opinions included in these pages are those of 2001 South Central USA Regional Programming Contest Staff only. Any statements and opinions included in these pages are NOT those of Louisiana State University, LSU Computer Science, LSU Computing Services, or the LSU Board of Supervisors.
© 1999,2000,2001 Isaac W. Traxler