Programmierwettbewerb 2002
FAQ und Problemloesungen

zur Wettbewerbsseite


Inhalt

(1) Könntest du mir verraten, wieviel Punkte und Schritte dein Hamster in den Labyrinthen die dabeiliegen erreicht? Ich wollte mal sehen, wie mein Hamster so dasteht und ob ich auf dem richtigen Weg bin.
(2) Wie kann ich meinen Hamster in ein Package legen und Hilfsklassen benutzen?
(3) Erklaer uns bitte ganz ausfuerlich (fuer Windows-User), wie wir die World starten!
(4) Sobald ich in der autoexec.bat den classpath auf das Archiv und das Hamster-Verzeichnis setze, kann ich andere Klassen nicht mehr kompilieren, woran liegt das?
(5): Das Neuladen des Hamsters funktioniert bei mir nicht. Ich muss jedesmal die World beenden und neustarten. Woran liegt das?
(6): In welchem Umfang sollte denn die Dokumentation zum Hamster sein?
(7): Wird der Hamster fuer jede Karte neu erzeugt, oder kann waehrend der Lebenszeit einer Hamster-Instanz die run() mehr als einmal aufgerufen werden?
(8): Was muss unser Hamster tun, um erfolgreich teilzunehmen? Muss der Punktestand im Plus sein? Muss er das gesamte Labyrinth aufdecken bzw. alle Koerner finden? Muessen wir irgendwelche bestimmten Programmstrukturen mit einbauen?
(9): Wieviele Punkte macht dein Hamster H2D2 auf den ersten beiden Wettbewerbslabyrinthen c00 und c20?
(10): Wann werden die Hamster laufen und wann gibts die Ergebnisse? Wie werden die "Formel 1"-Punkte verteilt?



(1) F: Könntest du mir verraten, wieviel Punkte und Schritte dein Hamster in den Labyrinthen die dabeiliegen erreicht? Ich wollte mal sehen, wie mein Hamster so dasteht und ob ich auf dem richtigen Weg bin.

A: Mein Hamster H2D2 erreicht folgende Punkte im MazeRunner:
flat/weg01.maze, Points: 3623, Steps: 577, Corn: 420, Coll: 0, Time: 0 (hier hab ich "zu Fuss" mit einem handgesteuerten Hamster 550 Schritte gebraucht und also 3650 Punkte geschafft)
ext/treppen1.maze, Points: 2016, Steps: 374, Corn: 239, Coll: 0, Time: 0

Uebrigens enthielten die ersten Versionen von contest2002.zip noch ein treppen1.maze, das zu viele Hoehenstufen hat! Die Ergebnisse sind die der aktuellen Version. Diese Punktzahlen sind nicht die Werte an denen eure Hamster gemessen werden, schliesslich gibts die Ergebnispunkte wie im Rennsport (oder so aehnlich) fuer die besten Hamster auf jedem Labyrinth.

(11.02.2002)



(2) F: Wie kann ich meinen Hamster "Jay" in ein Package legen und Hilfsklassen benutzen?

A: Da dein Hamster Jay heissen soll, brauchst du mindestens die folgenden Dateien im Verzeichnis hamster/
Jay.java
jay/Jay.java
jay/readme.txt (oder readme.html oder index.html)

Dabei ist Jay.java die "Startklasse" deines Hamsters, und muss eigentlich nur diese eine Zeile enthalten:
 public class Jay extends jay.Jay{ }
Das Verzeichnis jay/ enthaelt das Package jay, in dem die uebrigen Klassen deines Hamsters liegen sollen, weil ich ansonsten bei 30 Hamstern den Ueberblick verlieren wuerde.
Da nun die Datei jay/Jay.java in einem Unterverzeichnis liegt, befindet sich die darin definierte Klasse in einem Package. Das musst du aber dem Compiler mitteilen, und das geschieht mit der package-Anweisung als erste Zeile im Quelltext:
 package jay;
Damit weiss der Compiler, dass die folgende Klassendefinition sich auf eine Klasse im Package jay bezieht.
Nun folgen die Import-Anweisungen, mit denen man sich Zugang zu Klassen aus anderen Packages verschafft. Solche Klassen sind zum Beispiel die Hamster-Basisklassen, die man mit diesen Anweisungen erreichbar macht (die anderen Klassen des Packages algds.c2002 duerft ihr nicht verwenden, also brauchst du sie erst gar nicht zu importieren):
 import algds.c2002.Hamster;
 import algds.c2002.Hamster2;
 import algds.c2002.Constants;
Wenn du nun zusaetzlich noch z.B. die Klassen Vector oder LinkedList benutzen willst, brauchst du noch
 import java.util.*;
Wenn du naemlich diese Anweisung nicht schreibst - und so kommen wir zum eigentlichen Zweck dieser Anweisung - muesstest du statt
 Vector myvector = new Vector();
schreiben
 java.util.Vector myvector = new java.util.Vector();
weil der Compiler ansonsten nicht weiss, wo sich die Vector-Klasse befindet.
Die Hamsterklasse kann nach den package- und import-Anweisungen dann so beginnen:
 public class Jay extends Hamster {
Durch die package-Anweisung generiert der Compiler jetzt nicht die Klasse Jay, sondern die Klasse jay.Jay die also in dem Package liegt.
Du kannst auch auf das import verzichten, musst dann aber immer statt Hamster schreiben algds.c2002.Hamster usw.
Wenn du jetzt zusaetzlich zur Klasse jay.Jay noch Hilfsklassen benutzen willst, dann liegen die auch in dem Package!
Wir nehmen mal an, du willst die erkundete Karte in einer Klasse Map speichern. Die Datei jay/Map.java beginnt dann so
 package jay;
 import algds.c2002.Constants;
 class Map implements Constants {
Durch die implements-Klausel kannst du in der Map-Klasse direkt auf die Hamster-Konstanten zugreifen, ohne jedesmal Constants davorschreiben zu muessen (da algds.c2002.Hamster schon Constants implementiert, ist das in jay.Jay nicht mehr noetig). Falls du ein eigenes Interface mit Konstanten anlegst, kannst du das natuerlich auch implementieren.
Um nun von jay.Jay aus auf jay.Map zuzugreifen, musst du nichts importieren, denn Klassen aus demselben Package werden automatisch importiert (und zusaetzlich die Klassen aus java.lang, was auch nicht importiert werden muss).
Du kannst also in jay/Jay.java eine Variable map so anlegen:
 Map map = new Map();
Was du allerdings nicht kannst, ist Jay von Map erben zu lassen. Das ist eigentlich auch nicht vorgesehen.

(Nachtrag:)
Nachdem du die Klassen geschrieben hast, willst du sie natuerlich kompilieren. Dazu musst du im classpath das Basisverzeichnis angeben, in dem sich die Packages (nicht die Klassen) befinden. Wenn wir also annehmen, dass deine Klassen sich jetzt in hamster/jay befinden, brauchst du hamster/ im classpath (und ausserdem brauchst du noch das Archiv, in dem die Hamsterbasisklassen liegen).
Du kompilierst die Klassen also so:
 .../hamster/jay> javac -classpath ..;../../contest.jar Jay.java
oder so:
 .../hamster> javac -classpath .;../contest.jar jay/Jay.java

(16.02.2002)



(3) F: Erklaer uns bitte ganz ausfuerlich (fuer Windows-User), wie wir die World starten!

A: Fangen wir mal am Anfang an.
(Nachtrag: Bevor das Ganze losgeht muesst ihr das JDK installiert haben und das Verzeichnis mit den java-Programmdateien, also irgendwas wie C:\jdk1.3\bin in den Pfad aufnehmen! Wie das geht steht im Windows-Handbuch.)
Ihr legt ein Verzeichnis an, in dem ihr die Programme haben wollt. Das nenn ich jetzt mal C:\java\contest\ Wenn ihr ein anderes habt, aendert die Pfadangaben entsprechend.
Dann ladet ihr contest2002.zip runter und speichert das Archiv im eben angelegten Verzeichnis. Dort packt ihr es aus, so dass die Dateien in diesem Verzeichnis landen. (WinZip, oder ein Kommandozeilen-unzip)
Da muesste dann also eine Datei C:\java\contest\contest.jar rumliegen, und ein Verzechnis C:\java\contest\docs\, ein hamster\, ein mazes\ und ein images\ sowie ein paar Batch-Dateien (run, run.bat, world, world.bat) und html-Dateien (z.B. index.html als Startseite der Dokumentation).
Nun macht ihr eine MSDOS-Eingabeaufforderung auf. Darin wechselt ihr ins Verzeichnis C:\java\contest mit den Befehlen
 C:
 cd \java\contest
Und dann gebt ihr mal ein
 run LeftHand flat/weg01
Wenn dann sowas kommt wie
 Points: 1680, Steps: 720, Corn: 240, Coll: 0, Time: 0
dann habt ihr alles richtig gemacht und das Programm funktioniert.
Wenn nicht diese Ausgabe kommt, sondern eine andere, dann schreibt mir, was stattdessen ausgegeben wird (und zwar woertlich!!)
Wenn das klappt, koennen wir endlich mal die World starten mit dem einfachen Befehl
 world
Wenn dann statt eines huebschen Fensters nur eine Fehlermeldung kommt, schreibt mir was da steht!
Ansonsten, willkommen in der Hamsterwelt!

(14.02.2002)



(4) F: Sobald ich in der autoexec.bat den classpath auf das Archiv und das Hamster-Verzeichnis setze, kann ich andere Klassen nicht mehr kompilieren, woran liegt das?

A: Die wahrscheinlichste Ursache ist, dass der Compiler die anderen Dateien nicht findet, obwohl du den Compiler im selben Verzeichnis aufrufst, weil er gar nicht in diesem Verzeichnis sucht.
Die einfachste Loesung dafuer ist, dass du zusaetzlich zu den bisherigen Angaben noch das aktuelle Verzeichnis "." in den classpath aufnimmst:
 set classpath=C:\java\contest\contest.jar;C:\java\contest\hamster\;.

(11.02.2002)



(5): F: Das Neuladen des Hamsters funktioniert bei mir nicht. Ich muss jedesmal die World beenden und neustarten. Woran liegt das?

A: Das liegt daran, dass bei dir der Standard-Klassenlader eingestellt ist.
Auszug aus worlddoku.html

Der Menu-Eintrag Programm/Eigenschaften öffnet ein Dialogfenster, das bestimmte Eigenschaften des Programms setzt:
Standard ClassLoader
Angabe, ob zum Laden der Hamster der Standard-Klassenlader oder der eigene Lader verwendet werden soll.
Der Standard-Lader erkennt keine zwischenzeitlichen Neukompilierungen des Hamsters [...] Der eigene Lader erkennt, wenn der Hamster zwischendurch rekompiliert wird und laedt mit Hamster laden oder Hamster neuladen den neuen Hamster (und alle seine Unterklassen) von der Platte. Er nimmt dabei an, dass die Klassendateien im Unterverzeichnis hamster liegen.

(14.02.2002)



(6): F: In welchem Umfang sollte denn die Dokumentation zum Hamster sein?

A: Die Dokumentation sollte die folgenden Themen abdecken.

Es soll die Strategie erklaert werden, die der Hamster beim Erkunden verfolgt: Manche Hamster bevorzugen eine Himmelsrichtung, andere gehen geradeaus woimmer sie gerade hinschauen, einige laufen spiralig um das Heimatfeld herum, zwei im letzten Jahr liefen Zickzack. Dieses Verhalten ist gut zu erkennen auf einem leeren Labyrinth.

Weiterhin ist wichtig, welche Moeglichkeit der Hamster waehlt, das naechste zu besuchende Feld zu bestimmen: Sucht der Hamster immer das naechstgelegene Feld, welches "noch nicht betreten wurde oder Getreide enthaelt", oder gibt er Feldern "mit Getreide" den Vorrang vor "noch nicht betretenen Feldern ohne Korn", oder erkundet er das gesamte Labyrinth, bevor der das Einsammeln beginnt?

Es soll auch erwaehnt werden, was der Hamster mit Klippen macht: H2D2 geht Klippen erst hinunter, wenn er schon einmal unten war (es sei denn es gibt keinen anderen Weg mehr den er gehen koennte), und somit sofort weiss, wie es von da nach Hause geht. Alternativ kann man sofort jede Klippe runterspringen und dann den Heimweg suchen. Ich bin ausserdem gespannt, ob es jemandem gelingt, die dropForward()-Methode sinnvoll zu nutzen.

Wie ist der Algorithmus des Hamster aufgebaut? Welche Klasse ist fuer was zustaendig, welche wichtigen Methoden hat der Hamster und wie arbeiten sie (Hilfsmethoden, die z.B. nur einzelne Werte setzen und auslesen, muessen nicht einzeln beschrieben werden).

Wie werden die Informationen gespeichert, die der Hamster sammelt? Bei H2D2 ist das ein 2D-Array von Cell-Objekten, die die Informationen eines Feldes kapseln. Andere haben ein 3D-int-Feld, dessen dritte Dimension die Informationen enthaelt, einige haben eine sortierte Liste von Knoten... Wichtig ist mir auch, welches Koordinatensystem der Hamster nutzt. Denn irgendwie muessen die Felder des Labyrinth-Sechsecks ja nummeriert sein (oder vielleicht auch nicht?).

(28.02.2002)



(7): F: Wenn der Hamster mehrere Karten in einem Durchlauf abgrasen muss, wird dann fuer jede Karte der Hamster neu geladen/erzeugt, und die run() EINMAL aufgerufen, oder kann es sein, dass waehrend der Lebenszeit einer Hamster-Instanz die run() MEHR als einmal aufgerufen wird?

A:Es wird fuer jeden Start des Hamsters eine neue Instanz erzeugt. Das heisst, fuer jede Hamster-Instanz wird die run()-Methode nur einmal aufgerufen.

(04.03.2002)



(8): F: Was muss unser Hamster tun, um erfolgreich teilzunehmen? Muss der Punktestand im Plus sein? Muss er das gesamte Labyrinth aufdecken bzw. alle Koerner finden? Muessen wir irgendwelche bestimmten Programmstrukturen mit einbauen?

A: Ihr habt erfolgreich am Wettbewerb teilgenommen, wenn euer Hamster funktioniert und gut dokumentiert ist.
Das heisst, er muss auf den einfachen Labyrinthen in der Lage sein, Getreide einzusammeln und darauf achten, seine Wege zu minimieren. Dabei darf er keine Exceptions erzeugen (Nachbesserungen sind dafuer moeglich, werden aber dann nicht mehr in den Wettbewerb einbezogen). Der Quelltext soll gut strukturiert und kommentiert sein. Zur Dokumentation siehe Frage (6).
Beachtet: Auch ein erweiterter Hamster muss fuer die Zulassung nur auf den einfachen Labyrinthen bestehen, sein Verhalten auf den erweiterten Labyrinthe enscheidet nur ueber seine Platzierung im erweiterten Wettbewerb.

Es gibt Labyrinthe, in denen der Punktestand nach einer vollstaendigen Erkundung negativ ist, weil zuwenig Getreide vorhanden war. Deshalb gibt es keine Bestimmungen fuer die zu erreichende Punktzahl im Wettbewerb. Wir werden aber gegebenenfalls pruefen, warum einzelne Hamster extrem wenig Punkte erreichen, und diese Hamster moeglicherweise deswegen als nicht erfolgreich werten.

Wenn der Hamster entscheidet, dass es nicht mehr lohnt, weiter das Labyrinth zu erkunden, dann kann er aufhoeren (z.B. wenn das moeglicherweise noch vorhandene Getreide zu weit weg ist). Er sollte das aber auf dem Heimatfeld tun, sonst gibts Strafpunkte (schliesslich soll euer Hamster seinen Winterschlaf auch zuhause antreten).

Ihr sollt fuer eure Loesungsstrategie angemessene Datenstrukturen und Algorithmen benutzen. Ob das Felder oder Listen, Rekursionen oder Schleifen, innere Klassen, Klassen im gleichen Package oder in Subpackages sind, bleibt euch ueberlassen.

(13.03.2002)



(9): F: Wieviele Punkte macht dein Hamster H2D2 auf den ersten beiden Wettbewerbslabyrinthen c00 und c20?

A: Das werde ich nicht verraten. Es sind aber mehr als 1100 bzw. mehr als 4400 Punkte.



(10): F: Wann werden die Hamster laufen und wann gibts die Ergebnisse? Wie werden die "Formel 1"-Punkte verteilt?

A: Die Hamster sind auf die drei Tutoren aufgeteilt, da der Zeitaufwand, alle Hamster zu begutachten, sonst zu hoch ist. Fuer die Ergebnisse im Wettbewerb werde ich alle Hamster bei mir zuhause laufen lassen (Athlon XP 1700+, 256 MB, JDK 1.3).
Wir entscheiden bis 17.05., welcher Hamster den Beleg kriegt und welcher nicht. Das wird dann sofort bekanntgeben.
Die Ergebnisse des Wettbewerbs (also die genauen Punktzahlen und Platzierungen) werden allerdings erst zur Preisverleihung im Juni verraten. Die Wettbewerbslabyrinthe werden erst kurz vor der Preisverleihung veroeffentlicht.

Die Bewertungspunkte (BP) fuer den einfachen Wettbewerb sind so verteilt (geaendert am 14.05.):

100, 88, 77, 67, 58, 51, 46, 41, 37, 33,
 29, 25, 21, 17, 14, 12, 10,  9,  8,  7,
  6,  5,  4,  3,  3,  2,  2,  1,  1,  1
Das bedeutet, dass der Erstplatzierte auf einem Labyrinth 100 BP bekommt, der Zweitplatzierte 88 BP usw. bis zum 30. Hamster, die uebrigen gehen leer aus. (Hamster mit gleicher Punktzahl auf einem Labyrinth liegen beide auf demselben Platz, nachfolgende Plaetze werden uebersprungen, es gibt dann z.B. die Platzierungen 1, 2, 2, 4, 5, ...)
Die Platzierung im Wettbewerb richtet sich dann nach der Summe der erzielten Bewertungspunkte. Bei gleicher Bewertungspunktzahl im Endergebnis entscheidet die Anzahl der 1., 2., ... Plaetze ueber die Gesamtplatzierung (derjenige mit mehr 1. Plaetzen ist der bessere, bei Gleichheit entscheidet die Anzahl der 2. Plaetze usw. Sollte da voellige Uebereinstimmung herrschen, wird nach der Summe der in den Labyrinthen erzielten Punkten entschieden).
Es sollte also bei dieser Platzierung niemanden wundern, falls ein Hamster mit weniger Punkten besser platziert wird. Dieses Bewertungsschema soll vereinzelte extreme Punktzahlen relativieren, also z.B. Fehlverhalten von Hamstern auf einzelnen Labyrinthen, die ansonsten gleichmaessig gut sind.

Fuer den erweiterte Wettbewerb gibt es aufgrund der geringeren Teilnehmerzahl eine andere Punktetabelle (nämlich die Formel1-Werte):

100, 60, 40, 30, 20, 10
Die uebrigen Regelungen sind aber gleich.

(14.05.2002)



Seitenanfang
02.05.2002, Christian Semrau