Programmierwettbewerb

Vorlesung Algorithmen und Datenstrukturen
2001

Inhalt

Aktuelles

Einleitung

Seit 1998 wird im Rahmen der Vorlesung Algorithmen und Datenstrukturen ein Programmierwettbewerb durchgeführt - das Hamsterproblem:

Ein Hamster, der seinen Wintervorrat an Getreide noch nicht gesammelt hat, wird in einem Labyrinth ausgesetzt. In diesem Labyrinth ist eine bestimmte Anzahl von Maiskörnern in unterschiedlichen Grössen auf Haufen verteilt. Die Aufgabe des Hamsters ist es, möglichst viele Maiskörner zu sammeln und zu seinem Heimatfeld (von dem er startet) zu bringen. Dabei muss er die Sammelwege natürlich möglichst kurz halten, damit er bei seiner Tätigkeit nicht schon den grössten Teil der gesammelten Maiskörner als Nahrung verbraucht.

In diesem von Christian Borgelt erdachten Programmierwettbewerb soll ein Programm geschrieben werden, das den Hamster durch das Labyrinth steuert. Dazu steht eine Reihe von Funktionen zur Verfügung, mit denen dem Hamster bestimmte einfache Befehle gegeben werden können (z.B. "Drehe Dich um 90 Grad nach links!", "Gehe ein Feld geradeaus!", "Nimm drei Maiskörner auf!") oder mit denen man Informationen über die Umgebung des Hamster erhält (z.B. "Wieviel Mais liegt auf dem Feld auf dem ich gerade bin?")

Wie gut ein Programm die Aufgabe gelöst hat, wird anhand der Anzahl der gesammelten Maiskörner, der Länge des beim Sammeln zurückgelegten Weges und der Zahl der Zusammenstösse mit Wänden des Labyrinthes bestimmt. Die auf der Grundlage dieser Werte berechnete Punktzahl entscheidet schliesslich über die Plazierung im Wettbewerb.

Auch in diesem Jahr soll dieser Wettbewerb ausgetragen werden. Letztes Jahr ist es ein Duke - das Java-Maskottchen - gewesen, dass Kaffeebohnen gesammelt hat. Dieses Jahr soll es wieder ein Hamster sein, der seinen Wintervorrat an Maiskörnern sammelt!

Die Teilnahme am Programmierwettbewerb kann als Alternative zur Belegarbeit gewertet werden, wenn der eingereichte Hamster im Wettbewerb eine höhere Punktzahl erreicht als der Referenz-Hamster.
Seitenanfang

Installation und Nutzung

Die Aufgabe für den Programmierwettbewerb besteht darin, ein Java-Programm zu schreiben, das den Hamster durch ein Labyrinth steuert. Voraussetzung dafür ist die Wettbewerbsumgebung, die alle benötigten Klassen und Programme beinhaltet. Diese Umgebung erfordert ein JDK 1.2.2 und läuft unter Linux, Solaris und Windows. Es funktioniert möglicherweise nicht mit dem M$-Zeug! (Weitere Infos, wo's läuft und wo nicht, sind willkommen.)

Installation:

Dabei entstehen In "hamster" liegen zwei Hamster: der Referenzhamster des letzten Jahres und der aktuelle Referenzhamster.
In "mazes" liegen zwei Labyrinthe (eins davon für den Wettbewerb), ein paar mehr sind in der Datei contestmazes.zip herunterladbar, die im gleichen Verzeichnis wie contest2001.zip entpackt wird.
Die Labyrinthe der Wettbewerbs-Umgebung des Jahres 2000 sind auch dieses Jahr verwendbar, gespeichert wird aber stets im neuen Format. Die Labyrinthe von 1999 und vorher sind nicht direkt ladbar, ein Konverter ist als convertmazes.zip (30.04.2001) runterladbar. Die ZIP wird im contest-Verzeichnis entpackt, das Konverterprogramm landet dann im "mazes"-Verzeichnis und kann dort ausgeführt werden.

Das Archiv "contest.jar" enthält die Java-Programme

Hier ist eine Beschreibung der World. Wenn etwas unklar oder nicht wie erwartet ist, lest sie euch nochmal aufmerksam durch. Und wenn ihr in dem Durcheinander tatsächlich keine Antwort auf eure Frage findet, schreibt an einen der Tutoren.

Das Programm World erlaubt das Erstellen neuer Labyrinthe und das Verändern bereits existierender. Die Labyrinth-Dateien (mit der Endung ".maze") sollten im Verzeichnis "mazes" abgelegt werden, weil MazeRunner und MazeRunnerX sie von dort laden.
Ein Hamster-Programm wird als Java-Klasse implementiert, die von der Klasse algds.contest.Hamster erbt. (Siehe Implementierung eines Hamsters weiter unten.) Da die kompilierte Klasse im Verzeichnis "hamster" abgelegt wird, muss man dieses Verzeichnis zusätzlich zum Archiv in den Klassenpfad aufnehmen.

Unix/Linux:
  java -classpath contest.jar:hamster algds.contest.World

Windows:
  java -classpath contest.jar;hamster algds.contest.World

(Unterschied: Unix hat Doppelpunkt als Pfadtrenner, Windows hat Semikolon)

Alternativ können auch die Kommandozeilen-Versionen verwendet werden, wobei hier das Labyrinth (ohne das Verzeichnis "mazes/" und Endung ".maze") und die Hamster-Klasse (ohne "hamsters/" und ".class") als Parameter anzugeben sind:
Mit einfacher Grafikausgabe:

java -classpath contest.jar:hamster algds.contest.MazeRunnerX Maze Hamster

Ohne Grafikausgabe:

java -classpath contest.jar:hamster algds.contest.MazeRunner Maze Hamster

Scripte fuer einen einfacheren Aufruf sind weiter unten.

Seitenanfang

Labyrinth

Ein Labyrinth besteht aus Gängen und Räumen, in denen Maiskörner in unterschiedlicher Grösse abgelegt sind. Der Hamster kann im Labyrinth umherlaufen, sich drehen, nach vorn schauen, Mais aufnehmen und ablegen. Auf den Feldern liegen Maiskörner unterschiedlicher Grössen, die der Hamster stets nur "im Stück" aufnehmen, ablegen oder fressen kann.
Spezielle Felder - die Beamer erlauben den Transport innerhalb einer Ebene oder auf eine andere Ebene. Sie sind bidirektional, erlauben also den Transport in beide Richtungen. Betritt man ein Beamer-Feld kann man durch Aufruf einer speziellen Methode den Beamer aktivieren und gelangt so zu einem festgelegten anderen Beamer irgendwo im Labyrinth.
Die Ausdehnung und Anzahl der Ebenen ist dem Hamster nicht von vornherein bekannt, man muss also mit beliebig grossen Labyrinthen umgehen können, ohne vorher Grösse und Ebenenzahl zu kennen! Es muss nicht jedes Feld des Labyrinths erreichbar sein, so dass der erreichbare Bereich einer Ebene durchaus nicht-rechteckig sein kann, und die Ebenen scheinbar unterschiedlich gross. Jede Ebene ist stets von Wänden umrandet. Es kann also durchaus ein 1000x20-Labyrinth geben, ohne dass der Hamster alle 20000 Felder besuchen können muss. Ausserdem laufen die (x,y)-Koordinaten in den Ebenen nicht von (0,0) bis (Breite-1,Höhe-1), sondern können auch negative Werte annehmen, also z.B. von (-10,-12) bis (9,7) gehen in einer 20x20-Ebene. Die Ebenen sind bei 0 beginnend aufsteigend nummeriert. Das Heimatfeld des Hamsters ist ein beliebiges Feld in einer beliebigen Ebene.


Ein Labyrinth mit Hamster. Beschreibung ist hier.

Seitenanfang

Implementierung eines Hamsters

Das Schreiben eines Hamster-Programms ist relativ einfach: Es stehen nur wenige Steuerbefehle zur Verfügung, die man kennen muss. Die Schwierigkeit besteht vielmehr darin, sich eine geeignete Strategie zum Erkunden des Labyrinthes und Sammeln der Maiskörner zu überlegen.

Jeder Hamster muss als Java-Klasse implementiert und von der Klasse algds.contest.Hamster abgeleitet werden. Das Leben eines Hamsters spielt sich vollständig in der Methode run ab, die für jeden Hamster neu implementiert werden muss. Zur Steuerung stehen die in der Beschreibung zu algds.contest.Hamster dokumentierten Methoden zur Verfügung.

Als Beispiel ist hier der einfache Hamster LeftHand gegeben (ehemals CaffeineJunky), der noch aus dem Wettbewerb des letzten Jahres stammt. (Der aktuelle Referenzhamster ist als einführendes Quellcode-Beispiel eher ungeeignet, bei dem sollte nur die erreichte Punktzahl interessant sein.) Der Quelltext sollte im Unterverzeichnis hamster abgelegt werden. Die Hamster-Klasse ist wie üblich zu kompilieren und ebenfalls im Unterverzeichnis hamster abzulegen:

Rufe den Compiler im Verzeichnis java/contest/hamster (*) so auf:

javac -classpath ../contest.jar LeftHand.java

Anschliessend wird World gestartet, ein Labyrinth und die Hamster-Klasse geladen. Mit dem Start-Button geht's dann los...

Wir empfehlen, für die einzelnen Aufrufe der Programme kleine Script- bzw. Batch-Dateien anzulegen, um mit einem einfachen Aufruf die World oder den Compiler starten zu können (es vereinfacht die Arbeit - besonders an der Konsole - erheblich). Wir stellen hier eine Windows- und eine Unix-Version von Scripten als ZIP zur Verfügung. Diese Scripte sind im Verzeichnis java/contest abzulegen.



Seitenanfang

Regeln

Im Wettbewerb muss jeder Hamster einige Labyrinthe (wiviele, das wissen wir noch nicht) durchlaufen, wobei eines davon zuvor bekanntgegeben wird. Es gelten folgende Regeln: Die erreichte Gesamtpunktzahl berechnet sich danach wie folgt:
Punkte =
30 * (Gesamtgrösse des gesammelten Maises)
-1 * (Anzahl gegangener Schritte)
-20 * (Anzahl Kollisionen)
zusätzlich kommen hinzu:
Wenn Absturz oder Zeitüberschreitung (Schrittzeit oder Gesamtzeit): -5000
sonst Wenn verhungert: -200
sonst Wenn nicht auf Heimatfeld beendet: -100
sonst 0

Für den Wettbewerb ist die Summe der in allen Labyrinthen erzielten Punkte massgeblich.
Seitenanfang

Ablauf

Teilnahmeberechtigt am Wettbewerb sind alle Studentinnen und Studenten, die die Vorlesung Algorithmen und Datenstrukturen von Prof. Reiner R. Dumke im WiSe 2000/2001 und SoSe 2001 hören, und zwar einzeln oder im Team von 2 Personen. Natürlich sind auch andere "Hamstertrainer" willkommen, die würden aber ausser Konkurrenz teilnehmen.

Wir moechten euch bitten, falls ihr vorhabt, an dem Wettbewerb teilzunehmen, schreibt uns kurz, wir sind neugierig, wieviele Hamster wir zu erwarten haben. Eine vorherige Anmeldung ist nicht erforderlich, wer aber am Wettbewerb teilnehmen will wird gebeten, sich zu melden. Man kann auch bis zum 8.6. einen Hamster einschicken und so am Wettbewerb teilnehmen, wenn man sich nicht vorher bei uns gemeldet hat. Auch wenn ihr Labyrinthe erstellt habt, koennt ihr sie uns gern schicken, wir werden sie dann hier veroeffentlichen, damit andere ihre Hamster auch darauf testen koennen.

Jeder Teilnehmer muss bis zum 08.06.2001 (8. Juni 2001) den Quelltext seines Hamsters mit Dokumentation per EMail an contest2001@cs.uni-magdeburg.de senden.

Um teilzunehmen müsst ihr ein Hamster-Steuerprogramm schreiben und eine Dokumentation anfertigen (in einem Windows- und Unix-kompatiblen Format, vorzugsweise als TXT oder HTML), in der das Hamsterprogramm beschrieben wird. Dazu gehört die Beschreibung

Hier sind unsere Wünsche zur Dateistruktur des Hamsters.

Die besten Hamster treten in einer Endrunde mit neuen Labyrinthen an, die in der letzten Vorlesungswoche live ausgetragen wird.
 Die Endrunde ist offensichtlich ausgefallen. Aber ich finde es schon interessant genug, mitzuerleben, wie einige Hamster jetzt nach der Bekanntgabe der Labyrinthe weiter verbessert werden.
Den Siegern winken natürlich tolle Preise !!!

Fragen zur Wertung als Beleg u.ä. richtet ihr bitte an einen Übungsleiter eurer Wahl.
Fragen zur Programm-Umgebung richtet ihr bitte an contest2001@cs.uni-magdeburg.de oder an einen der Tutoren Christian Semrau und Stephan Finn. 

Dankeschön

Dank für die Unterstützung bei der Entwicklung der Wettbewerbsumgebung gilt: Seitenanfang
Status vom 30.04.2001, Stephan Finn, Christian Semrau