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 1997/1998 und im Sommersemester 1998 die Vorlesung "Algorithmen und Datenstrukturen", gehalten von Prof. Dr. Rudolf Kruse an der Universität Magdeburg, hören. Wer an dem Wettbewerb teilnehmen möchte, meldet sich bitte (am besten per E-mail) 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
Montag, den 15. Juni 1998, 12:00 Uhr mittags,
entweder per E-mail an Christian Borgelt zu schicken oder auf Diskette in den Übungen oder im Raum G206 abzugeben.
Die der Programme werden direkt anschließend auf den Wettbewerbslabyrinthen ausgef"uhrt. Die Siegerehrung findet am Montag, den 29.06.1998, ab 9:00 Uhr im G308 statt.
Statt der ausgegebenen Belegaufgabe über einfach verkettete Listen können Informatiker und Wirtschaftsinformatiker ihren Beleg auch mit einem Hamsterprogramm erwerben (Computervisualisten fragen bitte ihren zuständigen Übungsleiter). In diesem Fall besteht die Belegaufgabe darin
Abgabe der Belegaufgabe über das Hamsterprogramm ist (wie für das Wettbewerbsprogramm) der 15. Juni 1998.
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 |
Zwei besondere Labyrinthe, die nicht im Wettbewerb benutzt wurden (Dank an Aljoscha Klose):
kruse.maz | borgelt.maz |
Alle Labyrinthe als Paket: mazes.zip mazes.tar.gz
Alle Labyrinthe sind im HP-Pool unter ~borgelt/hamster/cont_98/mazes installiert und können auch von dort geladen werden.
Von den Informatikern und Wirtschaftsinformatikern wurden 15 Hamster-Steuerprogramme in C, von den Computervisualisten ein Hamster-Steuerprogramm in Smalltalk abgegeben:
Startnr. | Name | Quelltext |
---|---|---|
01 | Christian Decomain | decomain.c |
02 | Bernd Eckardt | eckardt.c |
03 | Michael Feist | extds.h feist.c |
04 | Kai Fuchs | fuchs.c |
05 | Frank Goldmann/Steffen Lentge | goldmann.c |
06 | Thomas Heinemann | heineman.c |
07 | Thomas Kirschnick | kirschni.c |
08 | Gunnar Klein | klein.c |
09 | Christian Klukas | klukas.c |
10 | Christian Kunze | kunze.c |
11 | Even Langer | langer.c |
12 | Tobias Rudolph | rudolph.c |
13 | Robert Schlesier | schlesie.zip schlesie.tar.gz |
14 | Ingo Thieme | thieme.c |
15 | Christoph Walter | walter.st |
16 | Stefan Weidner | weidner.c |
Alle Steuerprogramme als Paket: src.zip src.tar.gz
Einige Hamster-Steuerprogramme stürzten auf den Wettbewerbslabyrinthen ab (siehe Ergebnisse). In der obigen Tabelle kann auf die korrigierten Versionen zugegriffen werden. Die durchgeführten Korrekturen sind durch Start Korrektur und Ende Korrektur in Kommentaren gekennzeichnet. Der Originalquelltext wurde stets beibehalten, aber durch bedingte Compilierung "auskommentiert".
Alle Hamster-Steuerprogramme, die in C geschrieben wurden, sind als ausführbare Programme im HP-Pool unter ~borgelt/hamster/cont_98/bin installiert und können dort ausprobiert werden: Einfach das Shellscript ~borgelt/hamster/cont_98/xh starten, ein Labyrinth aus ~borgelt/hamster/cont_98/mazes laden und den gewünschten Hamster aus ~borgelt/hamster/cont_98/bin auswählen. Anschließend den Hamster mit dem Menüpunkt Actions>Start Hamster starten.
Die Auswertung der Hamsterprogramme auf den Wettbewerbslabyrinthen wurde für die C-Programme mit der im Hamster-Programmpaket enthaltenen Kommandozeilenversion des Labyrinthprogramms und dem Shellcript contest.sh auf einer Sun Ultra 2 Workstation durchgeführt. Die Auswertung des Smalltalkprogramms wurde von Jörg Hamel auf einem PC unter Microsoft Windows vorgenommen.
1. | Tobias Rudolph | 147.444 Punkte |
2. | Christoph Walter | 146.802 Punkte |
3. | Michael Feist | 146.708 Punkte |
Die vollständige Ergebnistabelle in HTML:
Ergebnistabelle
Die Ergebnistabelle als LaTeX-Datei:
results.tex
und als Postscript-Datei:
results.ps