Programmierwettbewerb

Vorlesung Algorithmen und Datenstrukturen
2002

zurueck zur Startseite

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 sind Maiskörner 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 möglichst kurz halten. Am Ende muss er wieder zuhause sein, um seinen Winterschlaf beginnen zu können.

Aufgabenstellung

In diesem Programmierwettbewerb soll ein Programm geschrieben werden, das den Hamster so durch das Labyrinth steuert, dass er moeglichst viel Getreide mit moeglichst wenigen Schritten einsammelt.

Dazu steht eine Reihe von Funktionen zur Verfügung, mit denen dem Hamster bestimmte einfache Befehle gegeben werden können (z.B. "Drehe Dich 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?", "Was sehe ich vor mir?").

Wie gut ein Programm die Aufgabe gelöst hat, wird anhand der Anzahl der gesammelten Maiskörner und der Länge des beim Sammeln zurückgelegten Weges entschieden.

Die Teilnahme am Programmierwettbewerb ist eine der vier Aufgaben (neben der Probeklausur und den zwei Belegen), von denen fuer die Zulassung zur Klausur zwei erfuellt werden muessen.

Seitenanfang

Installation und Nutzung

Voraussetzung um einen eigenen Hamster schreiben und testen zu können, ist die Wettbewerbsumgebung, die alle benötigten Klassen und Programme beinhaltet. Diese Umgebung erfordert mindestens ein JDK 1.2.2 und sollte eigentlich auf allen Systemen laufen, auf denen das installiert ist. (Informationen, wo's nicht läuft, sind jederzeit willkommen.)

Installation:

Dabei entstehen In "hamster" liegt ein Beispielhamster (LeftHand), den ihr euch anschauen und testen koennt, aber bitte vergesst seine Strategie und schreibt eine bessere.
In "mazes" liegen schon einige Labyrinthe, ihr solltet aber auch eigene erstellen, um euren Hamster zu testen. (Zur Unterscheidung von einfachen und erweiterten Labyrinthen liegen sie in den Unterverzeichnissen mazes/flat und mazes/ext.)

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 zuständigen 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" (oder einem Unterverzeichnis davon) abgelegt werden, weil MazeRunner sie von dort laedt.
Ein Hamster-Programm wird als Java-Klasse implementiert, die von der Klasse algds.c2002.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 -cp contest.jar:hamster algds.c2002.World
Windows:
  java -cp contest.jar;hamster algds.c2002.World
(Unterschied: Unix hat Doppelpunkt als Pfadtrenner, Windows hat Semikolon)

Alternativ kann auch die Kommandozeilen-Version verwendet werden, wobei hier das Labyrinth (ohne das Verzeichnis "mazes/" und Endung ".maze", aber mit eventuellen Unterverzeichnissen) und die Hamster-Klasse (ohne "hamster/" und ".class") als Parameter anzugeben sind:

java -cp contest.jar:hamster algds.c2002.MazeRunner Hamster Maze

Wenn ihr euren Hamster auf mehreren Labyrinthen direkt hintereinander laufen lassen wollt, koennt ihr RunHamster verwenden:

java -cp contest.jar:hamster algds.c2002.RunHamster Hamster Maze1 ... MazeN
Also z.B.
java -cp contest.jar:hamster algds.c2002.RunHamster LeftHand flat/weg01 ext/treppen1

Ihr könnt statt dieser langen Befehle auch die mitgelieferten Batch-Dateien run, world (Unix-Systeme), run.bat, world.bat (Windows) aufrufen. Auf Unix-Systemen muesst ihr diese Scripte erst mit
chmod 755 run world
lauffaehig machen.

Seitenanfang

Labyrinth

Ein Labyrinth besteht aus sechseckigen Feldern, die wie Bienenwaben angeordnet sind und ein Sechseck bilden. Durch Waende zwischen den Feldern bilden sich Gänge und Räume. Auf einigen Feldern liegen Maiskörner.
Das ganze Labyrinth ist von Wänden umrandet, so dass der Hamster nicht "rausfallen" kann.
Das Heimatfeld des Hamsters ist immer das mittlere Feld des Labyrinths.
In der erweiterten Variante gibt es mehrere Hoehenstufen, die durch Schraegen und Klippen verbunden sind. An Schraegen kann der Hamster in beiden Richtungen (rauf und runter) laufen, an Klippen kann er nur hinunterspringen, jedoch nicht wieder hinauf.
Die Ausdehnung des Labyrinths ist dem Hamster nicht von vornherein bekannt, es gibt aber die Beschraenkung auf eine Seitenlaenge von hoechstens 30 Feldern. Es muss nicht jedes Feld des Labyrinths erreichbar sein, es ist aber auf den Wettbewerbslabyrinthen sichergestellt, dass man von jedem erreichbaren Feld wieder heimkommt (Überprüfungsmöglichkeit in der World).


Ein erweitertes Labyrinth mit Hamster, und ein einfaches Labyrinth. Beschreibung ist hier.

Seitenanfang

Implementierung eines Hamsters

Das Schreiben eines Hamster-Programms ist relativ einfach: Es stehen wenige Steuerbefehle zur Verfügung, die man kennen muss. Die Schwierigkeit besteht 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.c2002.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.c2002.Hamster dokumentierten Methoden zur Verfügung.

Wenn der Hamster nicht nur auf den normalen Labyrinthen laufen soll, sondern auch auf den erweiterten, dann muss er statt von Hamster von Hamster2 abgeleitet werden. Die Klasse algds.c2002.Hamster2 stellt Methoden zur Verfügung, um mit Klippen umzugehen.

Als Beispiel ist hier der einfache Hamster LeftHand gegeben.
Der Quelltext ist im Unterverzeichnis hamster abgelegt. 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 starte World, lade ein Labyrinth und den Hamster. Mit dem Start-Button geht's dann los.

Oder lass den Hamster ohne Grafik laufen (hier auf einem mitgebrachten Labyrinth), indem du im Verzeichnis java/contest(*) diesen Befehl eingibst:

java -cp contest.jar;hamster algds.c2002.MazeRunner LeftHand flat/weg01
bzw.
run LeftHand flat/weg01

Seitenanfang

Regeln

Es gibt zwei Wettbewerbe:
Einen Wettbewerb aller Hamster (einfach und erweitert), der auf einfachen Labyrinthen ausgetragen wird, und einen Wettbewerb der erweiterten Hamster, der auf erweiterten Labyrinthen ausgetragen wird. Diese beiden Wettbewerbe werden getrennt prämiert.

Ein einfaches und ein erweitertes Labyrinth werden Anfang April bekanntgegeben. Die uebrigen Labyrinthe und ihre genaue Anzahl sind bis zum Abgabeschluss geheim (weil wir sie erst kurz vorher erstellen werden :-) ). Es werden aber mindestens 10 Labyrinthe pro Wettbewerb sein.

Es gelten folgende Regeln:

Die erreichte Punktzahl berechnet sich wie folgt:
P = 10 * gesammelteKoerner - gegangeneSchritte - 200 * gemachteKollisionen
zusätzlich kommen hinzu: Wenn Absturz oder Zeitüberschreitung (Schrittzeit oder Gesamtzeit): -3000, sonst Wenn nicht auf Heimatfeld beendet: -1000, sonst 0
Labyrinthpunkte = max(P, -10000)

Den Siegern winken natürlich tolle Preise !!!

Seitenanfang

Ablauf

Teilnahmeberechtigt am Wettbewerb sind alle Studentinnen und Studenten, die die Vorlesung Algorithmen und Datenstrukturen von Prof. Roesner im WiSe 2001/2002 und SoSe 2002 hören, und zwar einzeln oder im Team von 2 Personen (keine grösseren Gruppen!). Natürlich sind auch andere "Hamstertrainer" willkommen, die würden aber ausser Konkurrenz teilnehmen (so wie mein eigener Hamster).

Falls ihr vorhabt, an dem Wettbewerb teilzunehmen, schreibt mir bis Ende Februar eure Namen. (Nach neuesten Informationen ist die Angabe der Uebungsgruppe und auch der Matrikelnummer nicht notwendig!)
Bis Ende Maerz habt ihr Zeit, euch einen Namen fuer euren Hamster auszudenken. Sobald ihr euch entschieden habt, schreibt mir den Klassennamen und eventuell den vollstaendigen Hamsternamen (falls der vom Klassennamen abweicht), damit wir doppelte Namen vermeiden koennen. Ausserdem moechte ich von euch bis Ende Maerz wissen, ob ihr einen einfachen oder erweiterten Hamster einreichen wollt (ein einfacher erbt von Hamster, ein erweiterter von Hamster2).
Ihr koennt spaeter sagen, dass ihr nicht mehr teilnehmen wollt (oder einfach keinen Hamster schicken), aber nur wer sich angemeldet hat, wird gewertet (als Beleg und im Wettbewerb).
Abgabeschluss ist der 30.04.2002.

Natuerlich stehen wir gern fuer Fragen zur Verfuegung, per EMail oder im Tutor-Forum (auf der Tutorseite).

Um teilzunehmen müsst ihr ein kommentiertes 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 des Lösungsansatzes (der Erkundungs- und Sammelstrategie), und der verwendeten Datenstrukturen (wie wird das Labyrinth im Hamsterprogramm dargestellt). Auf ein javadoc des Programms koennen wir verzichten, geht lieber im Dokumentationstext auf die Aufgaben eurer Klassen und Methoden ein.

Ein Hamster hat erfolgreich teilgenommen, wenn er funktioniert und gut dokumentiert ist, also die gestellte Aufgabe im einfachen Labyrinth erfuellt (insbesondere keine Exceptions erzeugt, Nachbesserungen sind möglich) und man aus der Beschreibung erkennen kann, wie der Hamster was tut.

Hier sind unsere Wünsche zur Dateistruktur des Hamsters.

Jeder Teilnehmer muss spätestens am 30.04.2002 den Quelltext seines Hamsters mit Dokumentation (alles in einer ZIP-Datei gepackt) per EMail an [eine nicht mehr vorhandene Adresse] senden.

Wir drei Tutoren (Stephan Finn, Thomas Steube und Christian Semrau) werden entscheiden, welcher Hamster den Beleg kriegt. Dazu werden wir alle Hamster auf einem Satz einfacher Labyrinthe (die Wettbewerbslabyrinthe) laufen lassen, und anhand der Ergebnisse entscheiden, welcher Hamster in der Lage ist, "mit moeglichst wenigen Schritten moeglichst viel Getreide einzusammeln". Ausserdem sollen die Hamster gut dokumentiert und der Quelltext kommentiert sein.
Zusaetzlich werden die erweiterten Hamster auf einem Satz von erweiterten Labyrinthen laufen, die dort erzielten Ergebnisse sind fuer den Wettbewerb relevant, aber nicht fuer den Beleg!
Fragen zur Programm-Umgebung richtet ihr bitte an Christian Semrau (contest2002 (at) chsemrau (punkt) de).

Betreuer des Wettbewerbs sind neben mir
Thomas Steube und Stephan Finn.

Seitenanfang
Status vom 18.12.2005, Christian Semrau