Die Mentorengruppe Diskrete Mathematik schreibt aus:

Programmierwettbewerb 2012
„Tetris 3D“

Abgabeschluss: 24.03.2012, 23:59 Uhr

[Update: 28.01.2012 00:23] Testinstanzen verfügbar

[Update: 05.03.2012 21:19] FAQ hinzugefügt

1  Aufgabe

Gegeben ist ein 3D Tetris Spiel: Auf ein rechteckiges Spielfeld fällt eine Menge von achsenparallelen Quadern, die nicht mehr horizontal bewegt oder gedreht werden können. Sie kommen zum Stehen, sobald sie einen anderen Quader oder das Spielfeld berühren. Ziel des Spiels ist es den höchsten Punkt der Anordnung zu finden.

2  Preise

Teilnehmen können Studierende der Universität Bonn. Die Abgabe kann in Gruppen von bis zu drei Personen erfolgen. Preise für die Siegergruppen sind Fachbücher im Gesamtwert von 200 €.

Die Bewertung eines eingereichten Algorithmus richtet sich nach der Geschwindigkeit der Implementierung auf vorgegebenen Testinstanzen. Die Abgabe muss vollständig kommentiert sein und aus den Kommentaren sollte der theoretische Ansatz ersichtlich sein.

3  Spezifikationen

3.1  Eingabe

Das Programm liest von der Standardeingabe. Die erste Zeile der Eingabe besteht aus drei Zahlen A, B, N ∈ ℕ+, wobei A die Länge und B die Breite der rechteckigen Plattform sowie N die Anzahl der Quader angibt. Es gilt: N ≤ 400000 und A,B ≤ 10000.

Es folgen N Zeilen, welche die Quader in ihrer Fallreihenfolge beschreiben. Jede dieser Zeilen besteht aus fünf Zahlen a, b∈ℕ+ h, x, y∈ ℕ0, wobei a die Länge, b die Breite und h die Höhe des Quaders angeben. Sie fallen achsenparallel zur rechteckigen Plattform auf die Fläche (x, x+a) × (y, y+b). Es gilt: x, x + a ≤ A, y, y + b ≤ B und h ≤ 10000.

3.2  Ausgabe

Nachdem alle Quader heruntergefallen sind, soll das Programm die Höhe des höchsten Punktes ausgeben sowie eine neue Zeile beginnen.

3.3  Abgabe

Die Abgabe muss in C oder C++ geschrieben und konsistent formatiert sein. Sie muss korrekt arbeiten und ohne Fehlermeldung mit gcc/g++ (Kompilerflags: -O2 -Wall -W -pedantic) kompilierbar sein. Sie muss auf einem gängigen Linuxsystem funktionieren. Es dürfen mit Ausnahme der Standard C/C++ Library keine externen Bibliotheken eingebunden werden. Der Speicherplatz ist durch 4 GiB begrenzt. Es wird empfohlen, das Speichermanagement mit Hilfe des Tools valgrind zu überprüfen. Einsendungen ohne Speicherfehler erhalten Sonderpunkte. Zusätzlich zum dokumentierten Code wird eine kurze Ausführung (weniger als eine Seite) über die gewählten theoretischen Ansätze verlangt.

Die Abgabe muss bis zum 24. März 2012 um 23:59 Uhr per E-Mail an mentoren@or.uni-bonn.de erfolgen.

4  Beispiel

Eingabe: 

 
4 5 3
2 2 1 1 1
2 2 4 2 2
2 1 3 0 3

Ausgabe:

5

5  Ankündigung

Die Mentoren werden am Donnerstag den 26. Januar 2012 das Wettbewerbsthema ab 18 Uhr (s.t.) im Konferenzraum (2. OG) des Arithmeums genauer erläutern. Hier bietet sich die Möglichkeit detaillierte Fragen persönlich zu klären. Alle interessierten Studenten sind hierzu herzlich eingeladen.

Bei sonstigen Fragen kann sich jederzeit an mentoren@or.uni-bonn.de gewandt werden.

6  Downloads

Einige Instanzen zum Testen gibt es HIER. Die zugehörigen Lösungen stehen unter FAQ.

Die Ausschreibung gibt es hier als PDF zum Download.

7  FAQ

Fragen bezüglich der konkreten Abgabe:

  1. Encoding: Sollen Abgaben im ANSI-Format abgegeben werden? Oder ist auch eine Abgabe im UTF8-Format möglich?
    Dokumentation (als plain text) darf gerne als UTF8 gespeichert werden und auch Mails um UTF8 können wir lesen. Eine einfache Textdatei reicht auch als Dokumentation, Microsoft Word Dokumente o.ä. würden wir nur ungern anschauen.
  2. Umfang: Soll der gesamte Projektordner (src, tex, Doxyfile, makefile) an euch geschickt werden? Oder reicht die Ausführung sowie der Quellcode? .zip oder .tar.gz?
    Wenn du ein umfangreiches Projekt erstellt hast, darfst du uns das auch gerne zusenden. Wir werden die Quellen selber kompilieren, ein vorhandenes Makefile könnte die Sache für uns vereinfachen.

Zulässigkeit von C++ / Verständnis:

  1. Standardbibliothek: Ist die Nutzung von std::map und std::list aus der C++-Standardbibliothek zulässig?
    Das ist zulässig.
  2. Einlesen von der Standardeingabe: Heißt das, dass die Instanzen mittels 
    cat inst.1 | ./tetris.out
    übergeben werden?
    Nicht unbedingt genauso, aber aus Sicht des Programmes macht dies keinen Unterschied.

Fragen bezüglich der Instanzen:

  1. Was sind die Lösungen der Instanzen auf der Mentorenseite?
    inst.1 : 1354992508
inst.2 :  931154263
inst.3 :  506236115
inst.4 :   80912382
inst.5 : 1280833342
inst.6 :  858050478
inst.7 :  429487984
inst.8 :    6130530
inst.9 : 1204261818
inst.10:  779963129
  2. Größe der Instanzen: Testet ihr das Programm mit einer Instanz maximaler Größe? Falls ja, könntet ihr vielleicht eine Instanz solcher Größe veröffentlichen, um etwaige Speicherprobleme im Voraus zu erkennen und zu entfernen?
    Natürlich. Trotzdem bieten sich auch schon die jetzigen Instanzen an, um darauf das Programm mit valgrind zu checken. Es bietet sich auch an sich für die eigene Lösung die worst-case Instanzen zu überlegen und auch auf denen zu testen. Die veröffentlichten Instanzen sind relativ einfach.
    Für die Bewertung werden wir eine ganze Reihe schwierigerer Instanzen benutzen.
  3. Berührung der Quader: Quader "kommen zum Stehen, sobald sie einen anderen Quader [...] berühren". Mit Berühren ist aber hoffentlich das Aufeinandertreffen von Boden und Decke gemeint, nicht das aneinanderschleifen von Seiten, oder?
    Das ist richtig.

    4. This document was translated from LATEX by HEVEA.