- Contest 2014
Note: As every year, the creativity task allows you to try your hand at a more extensive, interesting problem. Since we deliberately want to allow many different solutions, it might happen that we will have to slightly modify the rules of the game during the first round. Any changes will be listed at the end of the task description.
Note2: Once you read and understood the task description, have a look at Sample Bots to get started.
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:
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):
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
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:
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.
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
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:
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:
cout << flush;
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: