Programmierwettbewerb im Sommersemester 2016: Brahmin Packer

Die Aufgabe: Puzzeln mit Rechtecken

Gegeben sei ein Brahmin samt Taschen, sowie eine Menge an Waren mit gegebener Größe und Wert. Ziel der Aufgabe ist es den verfügbaren Platz in den Taschen des Brahmins so auszunutzen, dass der Inhalt möglichst wertvoll ist.

Im Rahmen unserer Aufgabe wird das Brahmin und seine Taschen dargestellt durch eine Menge von Rechtecken. Jedes dieser Rechtecke stellt dabei den Verfügbaren Platz in einer Tasche dar. Desweiteren werden die Waren ebenfalls zu Rechtecken vereinfacht.

Die eigentliche Aufgabe für das Programm ist es dann, einen möglichst guten Lösungsvorschlag einzureichen. Dabei dürfen innerhalb einer bestimmten Zeit beliebig viele Vorschläge abgegeben werden. Gewertet wird am Ende der letzte Vorschlag der noch innerhalb der gegebenen Zeit eingereicht wurde.

Beispiel

Name Größe Wert
A \(4 \times 3\) \(10\) Caps
B \(3 \times 4\) \(11\) Caps
C \(5 \times 5\) \(25\) Caps

Dem Händler bleiben jetzt die folgenden Möglichkeiten Waren mitzunehmen:

Nr. Packplan Warenwert ben. Füllung Restwert
1. Ex1 \(21\) Caps \(26\) \(-5\) Caps
2. Ex2 \(35\) Caps \(13\) \(22\) Caps
3. Ex3 \(36\) Caps \(13\) \(23\) Caps

Die effektivste Variante nach den vereinfachten Regeln ist also Nummer 3.

Warengruppen

  1. Handelsware. Der angegebene Punktwert entspricht dem Erlös beim Verkauf, damit auch dem Punktwert am Ende einer Runde. Handelswaren stehen nur in begrenztem Umfang zur Verfügung.
  2. Schrott. Dieser kann nur unter Verlust verkauft werden und hat daher einen negativen Wert. Auch Schrott steht nur in einem begrenztem Umfang zur Verfügung.
  3. Füllmaterial. Dieses steht in unbegrenzter Menge zur Verfügung und wird automatisch in jede freie Ecke der Tasche gestopft um Schäden an der eigentlichen Ware zu vermeiden, es lässt sich leider am Markt nicht weiterverkaufen. Die Kosten für das Füllmaterial variieren von Runde zu Runde.

Die Spielregeln

Die Aufrufkonventionen

Die Teilnehmerprogramme werden für jede Aufgabe neu gestartet und nach abgelaufener Zeit falls nötig gewaltsam beendet. Nach dem Start werden die benötigten Daten über die Standardeingabe übergeben. Mit der Übertragung der Daten beginnt auch die Zugzeit und das Programm kann beliebig viele Lösungsvorschläge einreichen bis die Zeit abgelaufen ist.

Zwischen dem Start des Programmes und der Übergabe der Daten erhalten die Programme immer mindestens 5 Sekunden Zeit. Dieses ist aus Gründen der Chancengleichheit um zB. eine (J)VM oder einen Interpreter vollständig zu starten.

Die Daten werden jeweils in einer Zeile und immer in der folgenden Reihenfolge und Syntax übergeben:

  1. Die zur Verfügung stehenden “Taschen” als eine kommaseparierte, durch eckige Klammern eingeschlossene Liste von 2-Tupeln (breite, höhe). So wird \(10 \times 5\) Tasche von oben dargestellt als [(10,5)]. Eine Runde in der es eine zusätzliche \(12 \times 3\) Tasche gibt hätte die Form [(10,5),(12,3)].
  2. Die zur Verfügung stehenden “Waren” als eine kommaseparierte, durch eckige Klammern eingeschlossene Liste von 3-Tupeln (breite, höhe, wert). Die Waren A, B und C aus dem Beispiel von oben würden übermittelnt als [(4,3,10),(3,4,11),(5,5,25)].
  3. Die letzte Zeile beinhaltet die Kosten für das Füllmaterial als positive Ganzzahl.

Beispiel für einen Aufruf

Das Beispiel von oben könnte also in etwa aufgerufen werden wie folgt:

(sleep 5; echo "[(10,5)]"; echo "[(4,3,10),(3,4,11),(5,5,25)]"; echo "1") | make run

Dabei ist zu beachten, dass während der Durchführung des Wettbewerbs die Standardeingabe nicht geschlossen wird. Es sollte also beim Einlesen der Daten nicht auf ein EOF gewartet werden. Ein besserer Beispielaufruf ist daher:

(sleep 5; echo "[(10,5)]"; echo "[(4,3,10),(3,4,11),(5,5,25)]"; echo "1"; cat) | make run

Die Ausgabe

Die gefundenen Packpläne werden auf der Standardausgabe ausgegeben. Es ist möglich mehrere Lösungen auszugeben, die Lösungen sind dabei durch einen Unix-Zeilenumbruch zu trennen ('\n'). Es wird die jeweils zuletzt ausgegebene Lösung gewertet.

Beachtet hier bitte dass ihr möglicherweise die Ausgabe explizit flushen müsst.

Eine Ausgabe gilt immer erst dann als erfolgt, wenn sie durch ein Newline beendet wird.

Format der Lösung

Ausgegeben wird jeweils eine Liste von Listen von 3-Tupeln (x, y, id). Die äußere Liste stellt die Liste aller Taschen dar. Die inneren Listen sind jeweils die Darstellung einer einzelnen Tasche. Ihre Reihenfolge ist identisch mit der Reihenfolge der Taschen in der Eingabe.

Die Waren/Rechtecke werden innerhalb der Liste durch Tupel dargestellt, deren Aufbau im folgenden beschrieben wird:

Eine Platzierung für ein Rechteck besteht aus einem 3-Tupel von natürlichen Zahlen. Dabei sind die Elemente von Links nach Rechts:

Diese befinden sich in einer kommaseparierten Liste, welche durch eckige Klammern eingefasst ist.

Die Koordinate \((0,0)\) befindet sich unten links.

Das oben aufgeführte Beispiel 3 wäre als Antwort wie folgt:

[[(0,0,1),(3,0,2)]]

Punktewertung

Punktewertung einer Runde

Die jeweils letzte vollständige Ausgabe eines Programmes wird genutzt um die Punkte für die Runde zu ermitteln.

  1. Der Wert der verpackten Handelswaren und des Schrotts wird aufsummiert.
  2. Die Menge an benötigtem Füllmaterial wird ermittelt und seine Kosten errechnet.
  3. Die Kosten des Füllmaterials werden gegen den Wert der verpackten Waren gerechnet.

Es gibt keine Abzüge für nicht verpackte Waren.

Rangpunkte

Nach einer Runde werden alle Teilnehmer anhand ihrer Punktewertung in eine Rangliste einsortiert. Anhand ihrer Platzierung in der Rundenrangliste erhalten sie eine definierte Anzahl an Siegpunkten:

  1. 10 Punkte
  2. 8 Punkte
  3. 6 Punkte
  4. 5 Punkte
  5. 4 Punkte
  6. 3 Punkte
  7. 2 Punkte
  8. 1 Punkt

Bei einem Gleichstand an Spielpunkten werden diese Programme auf dem gleichen Platz platziert und erhalten auch die gleiche Anzahl an Rangpunkten. Eine entsprechende Anzahl an Folgeplätzen wird hierbei übersprungen.

Die Rangpunkte werden über alle Runden aufsummiert und am Ende der Veranstaltung wird aus der Summe der Rangpunkte eine abschließende Rangliste erstellt um den Gewinner zu ermitteln.

Programme ohne (gültige) Ausgabe erhalten unabhängig von ihrer tatsächlichen Platzierung keine Siegpunkte.

Beispiel

Nach der ersten Spielrunde haben wir den folgenden Punktestand:

Das führt zu folgender Platzierungstabelle:

Rang Spielpunkte Rangpunkte
1 20 10
1 20 10
1 20 10
4 10 5
4 10 5
6 8 3
7 7 2
8 -/- 0