Ameisenhügel

Ameisen in einem Garten in Pattaya Thailand an der IOI11

Hinweis: Wie jedes Jahr erlaubt euch die Kreativitätsaufgabe, euch an einem etwas umfangreicheren, spannenden Problem zu versuchen. Weil dabei gezielt viele verschiedene Lösungsansätze ermöglicht werden sollen, kann es vorkommen, dass die Regeln des Spiels im Laufe der ersten Runde noch an der einen oder anderen Stelle leicht abgeändert werden müssen. Allfällige Änderungen werden am Ende der Aufgabenbeschreibung aufgelistet.

Hinweis2: Nachdem du die Aufgabenstellung gelesen und verstanden hast, schau dir unsere Beispiel-Bots an, welche dir bestimmt helfen die Aufgabe anzugehen.

Spielidee

Ameisen sind hochintelligente Tiere. Sie verfügen über hervorragende Fähigkeiten, um sich gemeinsam zu organisieren und so gewaltige Bauwerke wie Ameisenhügel zu bauen.

In dieser Aufgabe sollst du den Ameisen helfen den Weg zurück zu ihrem Hügel zu finden. Dazu schreibst du ein Programm, das eine einzelne Ameise steuert und dafür auch nur das Blickfeld einer einzelnen Ameise kennt. Mit Hilfe von Duftstoffen, die deine Ameise ausstossen kann, ist es dir möglich mit anderen Ameisen aus deinem Volk zu kommunizieren, um ihnen beispielsweise den Weg zum Hügel zu erklären oder sie über andere Dinge zu informieren.

Dies ist eine interaktive Aufgabe. Das heisst, du bekommst jeweils einen kleinen Kartenausschnitt, der die Umgebung deiner Ameise repräsentiert, und kannst dich daraufhin für einen Zug entscheiden.

Da dein Ameisenvolk aus mehreren Ameisen besteht, läuft dein Programm auch in mehreren, unabhängigen Instanzen gleichzeitig. Deine Programme dürfen nicht direkt miteinander kommunizieren. Die einzige zulässige Interaktionsmöglichkeit ist das Anbringen von Duftmarkierungen auf der Karte.

Ziel des Spieles ist es, dass es den Ameisen deines Volkes schnellstmöglich gelingt den eigenen Hügel zu finden.

Regeln

Das Spiel findet auf einem Torus statt, dessen Grösse dir bekannt ist. Du kannst dir die Spielfläche auch einfach als Rechtecksfläche vorstellen, die jeweils an den gegenüberliegenden Enden verbunden ist. Das heisst wenn eine Ameise über den nördlichen Rand hinausläuft, dann betritt sie das südlichste Feld in der selben Spalte wieder und analog für Ost und West.

Deine Ameise weiss allerdings nie, wo sie sich in dieser Spielfläche befindet, das heisst du bekommst keine absoluten Koordinaten. Es gibt keinerlei Hindernisse in der Welt der Ameisen, lediglich andere Ameisen und die Hügel der einzelnen Ameisenvölker.

Spielstart

Zu Spielbeginn liest du sieben Ganzzahlen und einen Kleinbuchstaben auf einer einzigen Zeile ein: W H K N Z V S I

Dabei bezeichnen:

  • $W$ und $H$ die Grösse des Spielfeldes (ein Rechteck mit Breite $W$ und Höhe $H$, wobei $1\le W,H \le 1000$)
  • $K$ die Nichtbewegungs-Konstante, wobei $K > 0$ (Erklärung siehe unten)
  • $N$ die Anzahl Ameisen pro Volk
  • $Z$ die Anzahl Ameisen, die den Hügel für das Spielende erreichen müssen, d.h. $1 \le Z \le N$
  • $V$ die Anzahl Ameisenvölker auf dem Spielfeld, $1 \leq V \leq 26$
  • $S$ die Seitenlänge des Quadrates, welches deinen Ameisenhügel repräsentiert
  • $I$ der Identifikationsbuchstabe deines Ameisenvolkes (ein Kleinbuchstabe von 'a' bis 'z')

Beispiel: 10 20 10 15 13 4 1 b

Das Spiel findet auf einem Rechteck mit Breite 10 und Höhe 20 statt. Die Nichtbewegungs-Konstante ist gleich 10. Jedes der 4 Ameisenvölker besteht aus 15 Ameisen, wobei alle Ameisen, die du kontrollierst, mit einem 'b' markiert werden. Sobald ein Volk 13 Ameisen im Hügel hat, hat es gewonnen. Jeder Ameisenhügel besteht nur aus einem einzigen Feld (einem 1×1-Quadrat).

Zu Spielbeginn sind alle Ameisen zufällig über das Spielfeld verteilt.

Spielschritt

Eingabe

Zuerst enthält die Eingabe eine Zeile, die den im letzten Zug ausgeführten Schritt deiner Ameise mit einem einzelnen Buchstaben (und in einem Fall noch zwei Ganzzahlen) beschreibt:

  • N, E, S oder W: Deine Ameise hat sich um ein Feld in die entsprechende Himmelsrichtung bewegt (nach Norden, Osten, Süden oder Westen).
  • H: Deine Ameise blieb im letzten Zug stehen, entweder weil du das wolltest, oder weil ein Konflikt bei der letzten Bewegung auftrat.
  • M: Deine Ameise hat zuvor eine Markierung angebracht.
  • J a b: Weil sich deine Ameise während $K$ Schritten nicht bewegt hat, hat sich deine Ameise gelangweilt und hat sich um $a$ Felder in horizontaler und $b$ Felder in vertikaler Richtung bewegt. Dabei bedeutet $a > 0$ eine Bewegung nach Osten, $a < 0$ nach Westen, $b > 0$ nach Norden und $b < 0$ nach Süden. Dies entspricht also einem kartesischen Koordinatensystem.

Im allerersten Zug ist diese Zeile ein einzelner Buchstabe H.

In jedem Spielschritt bekommt deine Ameise anschliessend zwei nach Norden ausgerichtete 7×7 Kartenausschnitte ihrer Umgebung in folgendem Format:

Der erste Kartenausschnitt besteht aus 7 Zeilen mit je 7 Zeichen, wobei die Zeichen folgende Dinge repräsentieren:

  • '$.$': ein freies Feld
  • Kleinbuchstabe '$x$': eine Ameise aus dem Volk $x$
  • Grossbuchstabe '$X$': der Ameisenhügel des Volkes $x$

Der zweite Kartenausschnitt besteht aus 7 Zeilen mit je 7 ganzen Zahlen (jeweils durch ein Leerzeichen getrennt), wobei die Zahlen folgende Dinge repräsentieren: Zahl m: $0 \le m \le 255$: eine Markierung mit Wert m, beziehungsweise falls das entsprechende Feld ein Ameisenhügel ist, bezeichnet $m$ die Anzahl Ameisen in diesem Hügel.

Beispieleingabe:

InputOutput

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

Erklärung:

Im Schritt zuvor hat sich deine Ameise um ein Feld nach Westen bewegt. Von deiner Ameise aus, ist je eine Ameise des Volkes $a$, $b$, $c$, $d$ und die Hügel der Völker $c$, $e$ und $f$ zu sehen. Zudem sind Felder mit den Duftmarkierungen 33, 44 und 55 zu sehen.

Im Hügel $C$ sind schon zwei Ameisen des Volkes $c$, im Hügel $E$ ist schon eine Ameise und der Hügel $F$ ist noch leer. Jeder Hügel wird hier durch ein Quadrat mit Seitenlänge 2 repräsentiert. Der Wert $S$ ist also 2. Beachte, dass der Hügel F nur zur Hälfte auf der Karte sichtbar ist.

Deine Ameise befindet sich immer in der Mitte, also bist du hier die Ameise des Volkes $d$.

Falls sich deine Ameise im Hügel befindet, wird in der 1. Karte das Zeichen des Hügels angegeben.

Ausgabe

Als Ausgabe gibst du in einer Zeile an, was deine Ameise in diesem Schritt machen soll. Dir stehen folgende Möglichkeiten zur Auswahl:

  • Stehen bleiben: H
  • 1 Feld nach Norden bewegen: N
  • 1 Feld nach Osten bewegen: E
  • 1 Feld nach Süden bewegen: S
  • 1 Feld nach Westen bewegen: W
  • Markierung mit Wert m ($0 \le m \le 255$) anbringen: M m

Detailspezifikationen

  • Wenn deine Ameise eine Markierung anbringt, dann bleibt sie in diesem Schritt stehen. Auf dem Ameisenhügel können keine Markierungen angebracht werden. Der Hügel enthält eine automatische Markierung, die jeweils der Anzahl Ameisen entspricht, die sich zu Beginn des Zuges im Ameisenhügel befinden.
  • Auf jedem Feld kann sich nur eine Ameise gleichzeitig aufhalten.
  • Falls sich im selben Schritt mehrere Ameisen auf das selbe Feld bewegen, dann wird der Zug nicht ausgeführt, und die involvierten Ameisen erhalten ein '$H$' als Rückmeldung im nächsten Zug. Wenn sich deine Ameise auf einen gegnerischen Hügel bewegen will, bleibt sie ebenfalls stehen und erhält ein '$H$' als Feedback.
  • Falls sich eine andere Ameise auf eine markierende Ameise drauf bewegen will, verbleiben die Ameisen unverändert an ihrem Ort, die Markierung wird aber angebracht.
  • Falls sich zwei Ameisen im selben Schritt jeweils auf das Feld der anderen bewegen, also die Plätze tauschen, funktioniert dies problemlos.
  • Markiert eine Ameise ein Feld, so bleibt diese Markierung so lange erhalten, bis die nächste Ameise das Feld markiert. Markierungen sind für alle Ameisen sichtbar und überschreibbar, nicht nur für die Ameisen des eigenen Volkes. Überlege dir also, wie du allenfalls sicherstellen kannst, dass du die Markierungen richtig interpretierst und nicht auf «falsche Fährten» von anderen Ameisen hereinfällst.
  • Um zu verhindern, dass sich Ameisen gegenseitig blockieren, wird verlangt, dass sie sich ab und zu bewegen. Konkret bedeutet dies, dass falls sich deine Ameise innerhalb von $K$ Zügen nicht bewegt, springt die Ameise automatisch an einen zufälligen Ort in der Umgebung (ein Feld mit Distanz $\le 10$ zur alten Position). Beachte, dass die Ameise auf ein beliebiges freies Feld in der nahen Umgebung gesetzt wird, selbst wenn sie sich von der bisherigen Position nicht wegbewegen konnte (z.B. weil sie von anderen Ameisen blockiert wurde).
  • Auf dem Ameisenhügel des eigenen Volkes können sich beliebig viele Ameisen des dazugehörigen Volkes beliebig lange aufhalten und auch beliebig lange stehen bleiben. Eine Ameise, die ihren Hügel betreten hat, darf ihn auch wieder verlassen, wenn sie das will.

Spielende

Dein Ameisenvolk hat die Aufgabe erfolgreich gelöst, sobald sich $Z$ der $N$ Ameisen im Ameisenhügel aufhalten.

Sobald $Z$ deiner Ameisen den Hügel erfolgreich betreten haben, erhalten alle deine $N$ Programme im nächsten Zug zwei Kartenausschnitte, die nur aus Punkten (1. Karte) respektive Nullen (2. Karte) bestehen. Dein Programm soll sich dann korrekt beenden und alle allozierten Ressourcen wieder freigeben, andernfalls wird es vom Server terminiert. Du kannst deine eigene Position als Indikator benutzen, d.h. die Laufzeit deiner Ameiseninstanz ist genau dann vorbei, wenn das 4. Zeichen in der 4. Zeile der ersten Karte ein Punkt ist.

Tipps

Bei interaktiven Aufgaben ist es wichtig, dass du den Input-/Output-Buffer jeweils nach jedem Zug leerst. Benutze dazu in:

C/C++: fflush(stdout);

C++: cout << flush;

Pascal: flush(output);

Ameinsen in einem Garten in Pattaya Thailand an der IOI11 Zudem ist es wichtig, dass dein Programm bei der Eingabe nicht auf mehr Zeichen wartet, als dir vom Server als Eingabe gegeben werden. Insbesondere Leerzeichen oder Zeilenumbrüche im Formatstring für das Einlesen in C sind eine häufige Fehlerquelle. Wenn du beispielsweise mit scanf("%d ",&x); das erste Zeichen, welches kein Leerzeichen oder Zeilenumbruch ist. Ein solches bekommst du aber erst nachdem du deinen Zug bekannt gegeben hast. Somit würde dein Programm hier blockieren.

Server und Visualisierung

Zu dieser Aufgabe stellen wir ein Serverprogramm zur Verfügung, mit dem du dein Programm gegen dein eigenes und andere Programme testen kannst, und eine Visualisierung, die schon simulierte Spiele animiert. Da diese regelmässig weiterentwickelt werden, lohnt es sich ab und zu auf der Homepage nachzuschauen. Hier findest du den Server und ausserdem eine grosse Sammlung an Beispiel-Programmen in diversen Programmiersprachen: Server und Liste mit Beispiel-Programmen für die Kreativitätsaufgabe

Bewertung

Da es für diese Aufgabe natürlich keine perfekte Lösung geben kann und auch ein wenig um dich für die Teilnahme bei der Kreativitätsaufgabe zusätzlich zu motivieren, ist das Bewertungsschema für die Kreativitätsaufgabe anders als bei den anderen Aufgaben. Du erhältst:

  • 50% der Punkte für ein Programm, welches das Spiel korrekt spielt, das heisst sich an alle Regeln hält und mindestens eine mit den Sample-Bots vergleichbare Spielstärke aufweist. Wichtig: Du darfst den Code der Sample-Bots nicht einfach kopieren und einsenden. Die Sample-Bots dürfen und sollen dir aber gerne als Anleitung dienen, welche dir zeigen, wie du Ein- und Ausgabe in deiner Programmiersprache korrekt durchführst. Es wird ausdrücklich nicht gefordert, dass dein Programm die Ameise auf intelligentere Art und Weise zum Hügel führt, als ziellos umherzuirren, um die 50% der Punkte zu erhalten. Um das Turnier zu gewinnen ist es aber natürlich wichtig, dass deine Ameisen möglichst geschickt vorgehen.
  • Die restlichen 50% der Punkte werden entsprechend dem Resultat beim Ameisen-Turnier am SOI-Tag vergeben.

Einsendung