Hamster

Der Programmierwettbewerb
zur Vorlesung "Algorithmen und Datenstrukturen" 1999

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.

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

zurück zum Seitenanfang

Das Hamsterprogramm als Belegaufgabe

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.

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

zurück zum Seitenanfang

Die Teilnehmer und ihre Programme

An dem Wettbewerb nahmen 70(!) Studentinnen und Studenten teil, die in 39 Gruppen zusammenarbeiteten.

Startnr.Name 1Name 2
01Richard Bade Korinna Grabski
02Steven Bergner Frank Kleine
03Marc Blumentritt Nico Suchold
04Matthias Böduel Christian Pachaly
05Angela Brennecke Daniel Holländer
06Mirko Buhle Andreas Marx
07Tobias Cermann Karsten Richter
08Isabelle Côté Michala Weisensee
09Andreas Cyrus Marc Langnau
10Andreas Dammert Jens Winter
11Katrin Diesing Ivonne Riedel
12Andreas Doering .
13Hauke Dost Jörg Hundsdorfer
14Ulrich Eickmann Thorsten Springhart
15Andreas Engel Glen Masgai
16Andreas Esche Lars Schmidt
17Rainer Fauth Christian Vetter
18Falk Feuersenger Mathias Gumz
19Stephan Finn Diana Stölzel
20Frauke Friebe Christian Steinhauer
21Thomas Gabriel .
22André Herms Jan Tusch
23Anja Hildebrandt Claudia Isensee
24Hendrik Hirsch Daniel Tiedge
25Marc Hofmann Andreas Loh
26Steffen Kempe Christian Kolbe
27Eileen Loutchan Burkhard Sell
28Björn Meyer .
29Sebastian Mirschel Andreas Peuler
30Marc Paucke .
31Claudia Prang Melanie Wegner
32Thomas Ritter Marten Wenzel
33Marko Rosenmüller .
34Frederic Rossau .
35Jörg Schönebaum .
36Inga Schulze .
37Daniel Sommer Tino Weilepp
38Martin Spindler Carmen Westermann-Blawert
39Andreas 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.

zurück zum Seitenanfang

Die Ergebnisse

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.

Die Sieger

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.

zurück zum Seitenanfang

Unterlagen und Quelldateien

zurück zum Seitenanfang

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