Hamster

Der Programmierwettbewerb
zur Vorlesung "Algorithmen und Datenstrukturen" 1998

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.

zurück zur Vorlesungsseite

Übersicht

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 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

zurück zum Seitenanfang

Das Hamsterprogramm

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

zurück zum Seitenanfang

Der Programmierwettbewerb

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.

zurück zum Seitenanfang

Das Hamsterprogramm als Belegaufgabe

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.

zurück zum Seitenanfang

Die Wettbewerbslabyrinthe

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.

zurück zum Seitenanfang

Die Teilnehmer und ihre Programme

Von den Informatikern und Wirtschaftsinformatikern wurden 15 Hamster-Steuerprogramme in C, von den Computervisualisten ein Hamster-Steuerprogramm in Smalltalk abgegeben:

Startnr.NameQuelltext
01Christian Decomain decomain.c
02Bernd Eckardt eckardt.c
03Michael Feist extds.h feist.c
04Kai Fuchs fuchs.c
05Frank Goldmann/Steffen Lentge goldmann.c
06Thomas Heinemann heineman.c
07Thomas Kirschnick kirschni.c
08Gunnar Klein klein.c
09Christian Klukas klukas.c
10Christian Kunze kunze.c
11Even Langer langer.c
12Tobias Rudolph rudolph.c
13Robert Schlesier schlesie.zip schlesie.tar.gz
14Ingo Thieme thieme.c
15Christoph Walter walter.st
16Stefan 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.

zurück zum Seitenanfang

Die Ergebnisse

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.

Die Sieger

1.Tobias Rudolph 147.444 Punkte
2.Christoph Walter146.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

zurück zum Seitenanfang

Unterlagen und Quelldateien

zurück zum Seitenanfang

© 1998 Christian Borgelt ( christian.borgelt@cs.uni-magdeburg.de), letzte Änderung: 12.01.2000