Vorlesung Algorithmen und Datenstrukturen
2001
Inhalt
|
|
Aktuelles
-
03.07.2001: Nun endlich sind die Ergebnisse des Wettbewerbs da. Ihr
koennt sie euch auf dieser
Seite ansehen.
Die Labyrinthe sind auch von dort zu laden.
-
08.06.2001:
Die entgueltigen Hamster sind bis zum 15.06.2001 15:00 einzureichen!
Ihr werdet informiert, falls euer Hamster Exceptions und Timeouts produziert.
Andere Probleme, die die Hamster haben, betrachten wir als zur Sammel- und
Suchstrategie gehoerig.
Hat sich jemand von euch die Muehe gemacht, eigene Labyrinthe zu kreieren?
Ich
bin immer an neuen interessiert, und werde sie, wenn ihr erlaubt, nach
Abgabeschluss veroeffentlichen. Oder einfach nur benutzen, um die Hamster
eingehender zu untersuchen.
- ...
-
30.04.2001: Endlich! Der Referenzhamster Toto
ist im Netz, das erste Wettbewerbslabyrinth contest01.maze,
und die Quellcodes der gesamten Laufumgebung
als contestsrc.zip (08.06., 88KB).
Die Wettbewerbsumgebung mit dieser Dokumentation (ohne Quelltexte der Umgebung,
aber mit Referenzhamster und Wettbewerbslabyrinth) ist in
contest2001.zip (05.06., 170KB).
Eine kleine Sammlung von Labyrinthen ist
contestmazes.zip (12.03., 30KB).
Ein Konverter für Labyrinthe von 1999 ist in
convertmazes.zip (30.04.2001).
Hinweise auf Fehler werden gern entgegen genommen.
-
26.04.2001: [...] Wer Fragen hat, kann uns per
EMail fragen,
oder auch mich persoenlich (donnerstags 15-17 in 03/304b ist mein Tutorium).
Ach ja, etwas was mir wichtig ist: Ich wuensche euch beim Programmieren und
Austesten des Hamsters soviel Spass und Freude wie ich sie beim Programmieren
und Testen der Laufumgebung hatte. Christian
-
12.04.2001: [...] Bemerkungen zur Voranmeldung sind weiter unten.
-
12.03.2001: [...] Scripts zum Ausführen der JAVA-Programme sind für
Unix und Windows
als ZIP herunterladbar.
-
01.02.2001: [...] Am 08.06.2001 ist Abgabeschluss.
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:
-
Download der Umgebung und speichern unter dem Namen
contest2001.zip
Wir wählen hier als Speicherort das Verzeichnis java/contest,
um einen Anhaltspunkt zu haben, wenn wir uns auf Verzeichnisnamen beziehen.
Alle Befehle bei denen nichts anderes gesagt ist, sind dann in diesem
Verzeichnis auszuführen.
-
Auspacken des Archives mit winzip oder jar:
jar xvf contest2001.zip
Dabei entstehen
-
eine Datei "contest.jar" mit den Klassen der Laufzeitumgebung,
-
ein Verzeichnis "html" mit dieser Dokumentation,
-
ein Verzeichnis "mazes" für die verschiedenen Labyrinthe,
-
ein Verzeichnis "hamster" für die Wettbewerbsprogramme.
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
-
World, zum Erzeugen und Editieren von Labyrinthen und zum graphischen
Lauf des Hamsters,
-
MazeRunnerX, eine Kommandozeilen-orientierte graphische Ablaufumgebung
für des Hamsters,
-
MazeRunner, eine Kommandozeilen-orientierte grafiklose Ablaufumgebung
für schnelle Durchläufe,
-
RunAll, lässt einen Hamster auf mehreren Labyrinthen mit
dem MazeRunner laufen.
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.
- ch: Compiliert den Hamster. Ihr muesst die Datei so aendern,
dass der Name eures Hamsters verwendet wird.
- run MAZE HAMSTER: Startet den MazeRunner.
- runall HAMSTER: Lässt den Hamster mit dem MazeRunner auf
allen in der Script-Datei angegebenen Labyrinthen laufen und speichert die
Ergebnisse in res_HAMSTER.txt (die Datei wird jedesmal überschrieben).
- world [MAZE]: Startet die World [mit einem
geladenen Labyrinth].
- x MAZE HAMSTER: Startet den MazeRunnerX.
- zh: Packt den Hamster komplett in eine zip-Datei. Ihr muesst
die Datei so aendern, dass der Name eures Hamsters verwendet wird.
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:
-
Es darf nur die dokumentierte Schnittstelle der Klasse
algds.contest.Hamster
verwendet werden, insbesondere ist das Laden der Labyrinthe und das
Auslesen der Struktur direkt durch den Hamster nicht erlaubt.
Es ist also verboten, auf die internen Strukturen der Laufumgebung
zuzugreifen, oder das Labyrinth selbstaendig von der Platte zu laden.
Die Verwendung des Wissens, was er schon gesehen hat, halte ich fuer
absolut notwendig, um einen guten Hamster zu programmieren.
-
Pro gesammeltem Maiskorn der Grösse 1 erhält der Hamster
30 Punkte, grössere Körner ergeben proportional mehr Punkte
(Grösse 2 bringt 2*30=60 Punkte, Grösse 3 bringt 3*30=90 Punkte
usw.) Es werden dabei nur die Körner gezählt, die auf dem
Heimatfeld abgelegt sind.
-
Der Hamster hat ein Backenvolumen von 20, d.h. er kann maximal 20
Körner der Grösse 1 gleichzeitig tragen. Von der
Grösse 2 passen nur 10 hinein usw. Er kann natürlich
Körner unterschiedlicher Grössen gleichzeitig tragen, solange die
Gesamtgrösse 20 nicht überschreitet. Es gibt Körner der Grössen 1,2,3,4,5,6,7.
Auf jedes Feld des Labyrinths passt ein Volumen von 500 Körnern. Die
einzige Ausnahme davon ist das Heimatfeld, das unbegrenzt belegt werden
kann. Der Hamster kann nicht mehr als 500 auf ein Feld ablegen, es kann aber
nicht ausgeschlossen werden, dass beim Start bereits mehr auf einem Feld
liegen, denn im Editor existiert diese Grenze nicht!
-
Der Hamster verbraucht beim Bewegen Energie. Er hat zum Start einen
Energievorrat von 4000. Den kann er durch Fressen von Körnern bis
auf maximal 20000 erhöhen.
Für jedes gefressene Korn der Grösse 1 erhält er
200 Energiepunkte, für grössere Körner proportional mehr.
Pro Schritt verliert er 4 Energiepunkte, pro Vierteldrehung einen Energiepunkt.
Sinkt der Energievorrat auf 0 oder darunter, so verhungert der Hamster.
Man sollte den Hamster also von Zeit zu Zeit anweisen etwas zu fressen,
um seinen Energievorrat aufzufüllen.
-
Ein Beamvorgang wird sowohl bei der Bepunktung als auch bei den
Energiewerten als ein Schritt gezählt, d.h. es wird 1 Schritt gemacht
und 4 Energiepunkte abgezogen. Kann nicht gebeamt werden, so wird kein
Schritt gemacht, aber trotzdem die Energie abgezogen.
-
Für jeden Schritt des Hamsters wird 1 Punkt abgezogen.
-
Eine Kollision mit der Wand wird mit 20 Minuspunkten bestraft und der Hamster
macht eine Vierteldrehung nach links, bei der er 20 Energiepunkte verliert.
-
Verursacht der Hamster eine Exception, die seinen Lauf stoppt
("Absturz" des Hamsters), wird er mit 5000 Minuspunkten betraft (mit
Ausnahme der beiden von der Laufumgebung erzeugten Exceptions
algds.contest.HamsterDiedException
und algds.contest.HamsterStopException).
Also: Sehr wichtig ist, dass euer Hamster wirklich fehlerfrei läuft!
Letztes Jahr sind ein paar gute Hamster durch einen einzigen Absturz weit
in der Wertung zurückgefallen. Dieses Jahr wollen wir ein paar mehr
als nur 7 Labyrinthe haben, auf denen auch mehr Punkte zu holen sind
(auf den Labyrinthen der Sammlung schaffen LeftHand und Toto im Durchschnitt
ueber 3000 Punkte pro Runde).
-
Wenn der Hamster während des Wettbewerbs in der grafikfreien Umgebung
für drei Minuten (3 min) keinen Schritt macht, wird sein Lauf beendet
und der Hamster mit 5000 Minuspunkten bestraft.
Zusätzlich wird ein Zeitlimit von zwei Stunden (120 min) gesetzt,
in dem der Hamster seinen Lauf beenden muss. Schafft er es nicht in der
vorgegebenen Zeit, so wird sein Lauf abgebrochen. Auch dafür wird er
mit 5000 Minuspunkten bestraft. (Falls die Zeitueberschreitung JAVA-intern
behandelt werden kann, sind das -5000 Extrapunkte, falls ein Abbruch von
ausserhalb noetig ist, bei dem die bereits erreichte Punktzahl nicht
verfuegbar ist, ergeben sich insgesamt -5000 Punkte fuer den Lauf).
Diese Regel sollte eigentlich für funktionierende Hamster nicht
gefährlich werden, denn die Hamster, die ich kenne,
brauchen pro Schritt höchstens 3 Sekunden und schaffen selbst
grosse Labyrinthe (beim grafikfreien Lauf) in 5 Minuten.
Nachtrag, 03.06.2001: Nachdem ich einige Hamster bereits gesehen habe,
fuerchte ich, dass die Zeitbegrenzung ein Problem werden koennte.
Wir nehmen den schnellsten Rechner den wir finden fuer den Wettbewerb.
-
Wenn der Hamster verhungert, wird er mit 200 Minuspunkten bestraft.
-
Um seinen Lauf zu beenden, verlässt das Hamsterprogramm einfach die
run-Methode (mit der der Hamster gestartet wurde). Beendet der Hamster
seinen Lauf nicht auf den Heimatfeld, wird er mit 100 Minuspunkten bestraft.
Verhungert der Hamster und ist dabei nicht auf dem Heimatfeld, so wird
er nicht für beides bestraft, sondern nur mit den 200 Punkten fürs
Verhungern.
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
-
des Lösungsansatzes (der Sammelstrategie),
-
der verwendeten Datenstrukturen
-
und der Programmstruktur (Klassen, Methoden).
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:
-
Rainer Habrecht (Umgebung von 2000)
-
Lothar Schlesier (Umgebung von 2000)
-
Johannes Zander (MazeRunnerX von 2000)
-
Christian Semrau (Umgebung von 2001)
-
Stephan Finn (Umgebung von 2001)
Seitenanfang
Status vom 30.04.2001, Stephan Finn, Christian Semrau