Um einen zusätzlichen Anreiz zum Programmieren zu schaffen, bieten wir für die Hörer der Einführungsvorlesung "Algorithmen und Datenstrukturen" einen Programmierwettbewerb an.
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 unterschiedlich großen Haufen verteilt. Die Aufgabe des Hamsters ist es, möglichst viele Maiskörner zu sammeln und zu seinem Ausgangspunkt zu bringen. Dabei muß er die Sammelwege natürlich möglichst kurz halten, damit er bei seiner Tätigkeit nicht schon den größten Teil der gesammelten Maiskörner als Nahrung verbraucht.
In diesem Programmierwettbewerb soll ein Programm geschrieben werden, das den Hamster durch das Labyrinth steuert. Dazu steht eine überschaubare Menge 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!" etc.
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öße mit Wänden des Labyrinthes bestimmt. Die auf der Grundlage dieser Werte berechnete Punktzahl entscheidet schließlich über die Plazierung im Wettbewerb.
Eine genauere Beschreibung des Hamsterproblems gibt es hier: contest.ps
Wie sich der Hamster bewegt, kann mit der zur Verfügung gestellten graphischen Oberfläche in einem Fenster, in dem das Labyrinth angezeigt wird, verfolgt werden (siehe unten). Der Hamster ist der rote "Pacman" rechts unterhalb der Labyrinthmitte. Er ist auf dem grau unterlegten Feld gestartet. Die gelben Kreise stellen unterschiedlich große Maiskornhaufen dar.
Die graphische Oberfläche des Hamsterprogramms und ein Beispiel-Steuerprogramm sind im HP-Pool unter ~borgelt/src/hamster installiert. Die graphische Oberfläche kann mit dem in diesem Verzeichnis liegenden Shellscript xh gestartet werden. Nach dem Initialisieren des Labyrinthes über Actions > Randomize Maze... kann das Beispiel-Steuerprogramm mit Actions > Start Hamster ausgeführt werden.
Eine genauere Beschreibung des Hamsterprogramms gibt es hier: contest.ps
Am Hamster-Programmierwettbewerb können alle Studenten teilnehmen, die im Wintersemester 1998/1999 und im Sommersemester 1999 die Vorlesung "Algorithmen und Datenstrukturen", gehalten von Frau Dr. Maritta Heisel an der Universität Magdeburg, hören. Wer an dem Wettbewerb teilnehmen möchte, meldet sich bitte (am besten per E-mail) bei Ilona Blümel oder bei Christian Borgelt, damit aktuelle Informationen ggf. auch per E-mail verteilt werden können.
Der Wettbewerb wird auf einem festgelegten, für alle Programme gleichen, aber bis zur Ausscheidung geheimen Satz von Labyrinthen durchgeführt, die zum Teil per Hand konstruiert, zum Teil zufällig erzeugt sind.
Der Quelltext des fertigen Hamster-Steuerprogramms ist bis zum
Freitag, den 11. Juni 1999, 12:00 Uhr mittags,
entweder per E-mail an Ilona Blümel oder an Christian Borgelt zu schicken oder auf Diskette in den Übungen, im Raum 03.205a oder im Raum 03.206 abzugeben.
Die der Programme werden direkt anschließend auf den Wettbewerbslabyrinthen ausgeführt. Die Siegerehrung findet am Donnerstag, den 01.07.1999, ab 14:00 im H3 statt.
Statt mit der ausgegebenen Belegaufgabe kann man seinen Beleg auch mit einem Hamsterprogramm erwerben. In diesem Fall besteht die Belegaufgabe darin
Abgabe der Belegaufgabe über das Hamsterprogramm ist (wie für das Wettbewerbsprogramm) der 11. Juni 1999.
Der Hamster-Programmierwettbewerb wurde auf folgenden Labyrinthen ausgetragen:
konstruierte Labyrinthe | zufällige Labyrinthe |
---|---|
center1.maz | rand0.maz |
center2.maz | rand1.maz |
drop.maz | rand2.maz |
larders.maz | rand3.maz |
leave.maz | rand4.maz |
nowalls.maz | rand5.maz |
seduce.maz | rand6.maz |
serpent.maz | rand7.maz |
spiral.maz | rand8.maz |
tree.maz | rand9.maz |
wirble.maz | . |
waben.maz | . |
split.maz | . |
Die drei letzten konstruierten Labyrinthe stammen von Studenten: waben ist von Thomas Gabriel. Leider habe ich vergessen, mir die Namen der anderen Konstrukteure aufzuschreiben. Bitte melden!
Alle Labyrinthe als Paket: mazes.zip mazes.tar.gz
Alle Labyrinthe sind im HP-Pool unter ~borgelt/hamster/cont_99/mazes installiert und können auch von dort geladen werden.
An dem Wettbewerb nahmen 70(!) Studentinnen und Studenten teil, die in 39 Gruppen zusammenarbeiteten.
Startnr. | Name 1 | Name 2 |
---|---|---|
01 | Richard Bade | Korinna Grabski |
02 | Steven Bergner | Frank Kleine |
03 | Marc Blumentritt | Nico Suchold |
04 | Matthias Böduel | Christian Pachaly |
05 | Angela Brennecke | Daniel Holländer |
06 | Mirko Buhle | Andreas Marx |
07 | Tobias Cermann | Karsten Richter |
08 | Isabelle Côté | Michala Weisensee |
09 | Andreas Cyrus | Marc Langnau |
10 | Andreas Dammert | Jens Winter |
11 | Katrin Diesing | Ivonne Riedel |
12 | Andreas Doering | . |
13 | N.N. (entf. 01/2008) | Jörg Hundsdorfer |
14 | Ulrich Eickmann | Thorsten Springhart |
15 | Andreas Engel | Glen Masgai |
16 | Andreas Esche | Lars Schmidt |
17 | Rainer Fauth | Christian Vetter |
18 | Falk Feuersenger | Mathias Gumz |
19 | Stephan Finn | Diana Stölzel |
20 | Frauke Friebe | Christian Steinhauer |
21 | Thomas Gabriel | . |
22 | André Herms | Jan Tusch |
23 | Anja Hildebrandt | Claudia Isensee |
24 | Hendrik Hirsch | Daniel Tiedge |
25 | Marc Hofmann | Andreas Loh |
26 | Steffen Kempe | Christian Kolbe |
27 | Eileen Loutchan | Burkhard Sell |
28 | Björn Meyer | . |
29 | Sebastian Mirschel | Andreas Peuler |
30 | Marc Paucke | . |
31 | Claudia Prang | Melanie Wegner |
32 | Thomas Ritter | Marten Wenzel |
33 | Marko Rosenmüller | . |
34 | Frederic Rossau | . |
35 | Jörg Schönebaum | . |
36 | Inga Schulze | . |
37 | Daniel Sommer | Tino Weilepp |
38 | Martin Spindler | Carmen Westermann-Blawert |
39 | Andreas Tappenbeck | Christian Teutsch |
Die Quelltexte aller Hamster-Steuerprogramme als Paket: src.zip src.tar.gz
Alle Hamster-Steuerprogramme sind als ausführbare Programme im HP-Pool unter ~borgelt/hamster/cont_99/bin installiert und können dort ausprobiert werden: Einfach das Shellscript ~borgelt/hamster/cont_99/xh starten, ein Labyrinth aus ~borgelt/hamster/cont_99/mazes laden und den gewünschten Hamster aus ~borgelt/hamster/cont_99/bin auswählen. Anschließend den Hamster mit dem Menüpunkt Actions>Start Hamster starten.
Die Auswertung der Hamsterprogramme auf den Wettbewerbslabyrinthen wurde mit der im Hamster-Programmpaket enthaltenen Kommandozeilenversion des Labyrinthprogramms und dem Shellcript contest.sh auf einem PC unter S.u.S.E. Linux 6.0 durchgeführt.
1. | Daniel Sommer | Tino Weilepp | 176.700 Punkte |
2. | Steffen Kempe | Christian Kolbe | 176.322 Punkte |
3. | Thomas Gabriel | . | 176.314 Punkte |
4. | André Herms | Jan Tusch | 175.218 Punkte |
5. | Isabelle Côté | Michala Weisensee | 175.014 Punkte |
Die vollständigen Ergebnistabellen in HTML:
Ergebnistabellen
Die Ergebnistabellen als LaTeX-Datei:
results.tex
und als Postscript-Datei:
results.ps
Einige Hamster-Steuerprogramme stürzten auf den Wettbewerbslabyrinthen ab oder gerieten in Endlosschleifen (in der vollen Tabelle markiert). Bei einer Endlosschleife, in der der Hamster noch läuft, können im Prinzip beliebig viele Minuspunkte erreicht werden, da ja jeder Schritt des Hamsters einen Punkt kostet. Um in einem solchen Fall das Ergebnis unabhängig von der Rechnergeschwindigkeit zu halten (je schneller der Rechner, um so größer die Zahl der Minuspunkte bis zur Zeitüberschreitung), wurde die auf einem Labyrinth zu erzielende Punktzahl nach unten auf -10000 begrenzt.