Swiss Olympiad in Informatics

Ants are highly intelligent animals. They have outstanding skills to organize themselves, allowing them to build huge buildings such as anthills.

In this task, you will help the ants to find their way back to their hill. You will write a program which controls one ant, and therefore only knows the field of vision of one single ant. Using scents, that your ant can secrete, you can communicate with other ants of your population, e.g. to explain them how to get to the hill or to advise them of other things.

This is an interactive task. This means that at every step, you get a little map representing the environment of your ant, and after that, you can decide what move you want to do.

Since your ant population consists of several ants, your program will be running simultaneously in several independent instances. Your programs are not allowed to communicate directly. The only legal way of interaction is to put scents onto the map.

The goal of the game is that your ants find their own hill as fast as possible.

The game is played on a torus, of which you know the size. You can also imagine the playing field as a rectangle where the opposite sides are connected to each other. This means that if an ant leaves the playing field at the north border, then it enters the field on the south-most tile in the same column, and analogously for west and east.

However, your ant never knows its absolute coordinates. There are no obstacles in the world of the ants, only other ants and the hills of the ant populations.

At the beginning of the game, you read seven integers and a lower-case letter on one single line: W H K N Z V S I

They describe the following:

• $W$ and $H$: the size of the playing field (a rectangle of width $W$ and height $H$, with $1 \le W,H \le 1000$)
• $K$: the non-moving constant, with $K > 0$ (explanation see below)
• $N$: the number of ants per population
• $Z$: the number of ants which must reach the hill for the game to be finished, i.e. $1 \le Z \le N$
• $V$: the number of ant populations on the playing field, , $1 \leq V \leq 26$
• $S$: the side length of the square representing your anthill
• $I$: the identification letter of your ant population (a lower case letter from 'a' and 'z')

Example: 10 20 10 15 13 4 1 b

The game is played on a rectangle of width 10 and height 20. The non-moving constant equals 10. Each of the 4 ant populations consists of 15 ants, and all ants controlled by you are marked with a 'b'. As soon as a population has 13 ants in the hill, they win. Every anthill consists of one single tile (a 1×1 square).

At the beginning of the game, all ants are randomly distributed on the playing field.

In every step, the input contains first one line describing the last move of your ant with a single letter or with a single letter followed by two integers (see below):

• N, E, S or W: Your ant moved by one tile in the corresponding direction (north, east, south or west).

• H: Your ant stayed on the same tile, either because you wanted it, or because there was a conflict at the last move.

• M: Your ant has put a scent on the map.

• J a b: Because your ant has not been moving during $K$ steps, your ant was bored and has moved by $a$ tiles horizontally and by $b$ tiles vertically. $a > 0$ means that your ant moved east, $a < 0$ west, $b > 0$ north and $b < 0$ south. So, this corresponds to a Cartesian coordinate system.

In the very first step, this line is one single letter H.

Then, your ant gets two 7×7 maps of its environment, facing north, in the following format:

The first map consists of 7 lines of 7 characters each, and the characters represent the following:

• '$.$': a free tile

• lower-case letter '$x$': an ant of population $x$

• upper-case letter '$X$': the anthill of population $x$

The second map, starting on a new line, consists of 7 lines of 7 integers each (separated by a space), and the numbers represent the following:

Number $m$: $0 \le m \le 255$: a scent with value $m$, or if the concerned tile is an anthill, then $m$ is the number of ants in this hill. All tiles are initiated with scent 0 at first.

Sample input:

W
...a...
....CC.
b...CC.
...d...
.c.....
.....EE
.FF..EE
0 0 33 0 0 0 0
0 0 0 0 2 2 0
0 0 0 0 2 2 0
0 0 44 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 55 1 1

Explanation:

In the last step, your ant moved one tile to the west. Your ant sees one ant of populations $a$, $b$, $c$, $d$ each, and the hills of populations $c$, $e$, and $f$. Further, it sees tiles with scents 33, 44 and 55.

In hill $C$, there are two ants of population $c$, in hill $E$, there is one ant and hill $F$ is empty. Every hill is a 2×2 square, so the value of $S$ is 2. Note that only one half of hill F is on the map.

Your ant is always in the middle, so here, you are an ant of population $d$.

If your ant is in the hill, the first map contains the character of the hill.

Output one line describing what your ant should do in this step. You have the following possibilities:

• Stay on the same tile: H
• move 1 tile to the north: N
• move 1 tile to the east: E
• move 1 tile to the south: S
• move 1 tile to the west: W
• put a scent of value $m$ ($0 \le m \le 255$): M m

• If your ant puts a scent on the map, it stays on the same tile. You cannot put scents on the anthill. The hill has an automatic scent number, which is the number of ants in the hill at the beginning of the step.

• On every tile, there can be only one ant at the same time.

• If several ants want to move onto the same tile in the same step, the move is not executed, and the concerned ants get an $H$ as a feedback in the next step. If your ant wants to move onto an opponent's hill, it does not move and also gets an $H$.

• If an ant wants to move onto an ant secreting a scent, it does not move, but the scent is put.

• If two ants both move on the tile of the other ant in the same step, i.e., if they swap their positions, this works perfectly.

• If an ant puts a scent on a tile, this scent is conserved until the next ant puts another scent on this tile. Scents are visible and overwriteable for all ants, not only for those of your own population. So, think of a way how to make sure you interpret the scents correctly, without being taken by «wrong» scents of other ants.

• In order to avoid that ants block each other, we demand that they move from time to time. In practice, this means that if your ant stays on the same tile during $K$ steps, then your ant automatically jumps to a randomly chosen tile in its environment (a tile with distance $\le 10$ to the old position). Note that the ant will be put onto an arbitrary tile in its close environment, even if it was not able to leave its old position (e.g. because it was completely surrounded by other ants).

• On the anthill of the own population, there can be any number of ants of the corresponding population for as much time as they want, and they can also stay on the same tile as long as they want to. If an ant has entered its hill, it is allowed to leave it again (if it wants to do so).

Your ant population has solved the task successfully as soon as $Z$ out of the $N$ ants are in the anthill.

As soon as $Z$ of your ants have entered the hill, all your $N$ programs get two maps consisting only of dots (first map) or only of zeroes (second map). Then, your program should terminate correctly and free all allocated resources, otherwise, it will be terminated by the server.

You can use your own position as an indicator, i.e., the run time of your ant instance is over as soon as the fourth character in the fourth line of the first map is a dot.

For interactive tasks, it is important that you flush the input/output buffer after every step. Use the following commands:

C/C++: fflush(stdout);

C++: cout << flush;

Pascal: flush(output);

Further, when reading input, it is important that your program does not wait for more characters than the server gives you as input. Especially spaces or line breaks in the format string in C are a common cause of error. For instance, if you read the last variable of the input with scanf("%d ", &x);

During the first round, we are providing a server program which you can use to let your own program compete against your and other programs, as well as a visualization which animates simulated games. You can find those, in addition to sample bots in many different programming languages, on the following website: Server and list of sample-bots for the creativity task. Since they are continuously developed, it is worth having a look at the website from time to time.

Since there is obviously no perfect solution and in order to motivate you even more for this creativity task, the grading scheme for the creativity task is different than for the other tasks. You get:

• 50% of the points for a program which plays the game correctly, i.e. which respects all the rules and plays at least as well as the sample bots. Important: You are not allowed to simply copy and submit the code of the sample bots. However, you are allowed and encouraged to use them as instructions on how to correctly do the input/output in your programming language. To get the 50% of the points, we explicitly do not ask you to lead your ants to the hill in a more clever way than by simply letting them wandering around. But to win the tournament, of course, it is necessary that your ants act as intelligently as possible.
• the remaining 50% of the points are awarded according to the result at the ants tournament at the SOI day.

Submission form