Programmier­wettbewerb im Wintersemester 2013/2014: Die Aufgabe

Die Aufgabe

Alle Informatiker kennen die Antwort, aber wie heißt die Frage? Diese Frage möchten wir in einem kleinen Knobelspiel beantworten. Aber nicht nur diese, sondern noch einige mehr.

Das kleine zu lösende Rätsel besteht aus folgender Aufgabe: Gegeben sei eine natürliche Zahl, z.B. 42, und eine Liste von weiteren natürlichen Zahlen. Gesucht ist der komplizierteste Ausdruck, der mit den gegebenen Zahlen und Operationen, etwa den 4 Grundrechenarten, gebildet werden kann und das gegebene Resultat ergibt.

Ein kleines Beispiel:

Gegeben sei die Liste von Zahlen [1,1,2,3,5,8], das Resultat 42 und als erlaubte Operationen in diesem Beispiel die vier Grundrechenarten. Eine Lösung ist dann 2 + (5 * 8), eine weitere 3 + ((8 * 5) - 1), eine dritte (3 + ((5 * 8) - 1)) * 1. Man erkennt an den Beispielen, dass die Reihenfolge der gegebenen Zahlen nicht die Lösungsmenge beeinflusst.

Zur Präzisierung der Aufgabe müssen wir nun wissen, welche arithmetischen Operationen im Wettbewerb zugelassen sind und wie die Komplexität eines Ausdrucks gemessen wird.

Die Spielregeln

Hinweis: Achten Sie darauf, dass Zwischenergebnisse nicht zu klein (kleiner gleich Null), aber auch nicht zu groß sind, um die Grenzen ihres Zahlentyps nicht zu sprengen.

Die Aufrufkonventionen

Die Teilnehmerprogramme werden für jede Aufgabe neu gestartet und nach abgelaufener Zeit falls nötig gewaltsam beendet. Nach Programmstart werden die benötigten Daten über die Standardeingabe übergeben. Mit dieser Übertragung beginnt die Zugzeit und es können Vorschläge eingereicht werden. Zwischen dem Start der Programme und der Übergabe der Nachrichten lassen wir aus Gründen der Chancengleichheit genug Zeit, um z.B. eine VM oder einen Interpreter vollständig zu starten.

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

Beispiel für einen Aufruf:

Das oben gewählte Beispiel könnte folgendermaßen ausgeführt werden:

(echo "[1,1,2,3,5,8]"; echo 42) | make run

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

(echo "[1,1,2,3,5,8]"; echo 42; cat) | make run

Die Ausgabe

Die gefundenen Ausdrücke werden auf der Standardausgabe ausgegeben. Es ist möglich mehrere Lösungen auszugeben, jede Lösung wird dabei auf eine Zeile geschrieben. Leerraum innerhalb der Lösungsausdrücke ist erlaubt, aber nicht notwendig. Die letzte ausgegebene Lösung zählt.

Wichtig: Wenn mit gepufferter Ausgabe gearbeitet wird, sollte immer der Ausgabepuffer explizit nach der Ausgabe einer Lösung geleert werden, damit die Lösung nicht versehentlich im Ausgabepuffer stehen bleibt.

Die Ausdrücke müssen nach folgender kontextfreier Grammatik aufgebaut sein:

Ausdruck        ::=  Zahl |  BinärerAusdruck
Zahl            ::=  Ziffer Ziffern
Ziffer          ::=  '0' | '1' | ... | '9'
Ziffern         ::=  | Ziffer Ziffern
BinärerAusdruck ::=  Faktor Operator Faktor
Faktor          ::=  '(' Ausdruck ')' |  Zahl
Operator        ::= '+' | '-' | '*' | '/' | '<+>' | '<->' | '<*>'

Man erkennt an der Grammatik und an den Beispielen, dass ausschließlich mit vollständig geklammerten Ausdrücken gearbeitet wird. Assoziativitäten sind also nicht erlaubt.

Die Projektorganisation

Der Wettbewerb

In jeder Runde wird eine Aufgabe, eine Liste von Zahlen und eine gesuchte Zahl vorgegeben. Dann werden die Lösungsprogramme mit den gleichen Vorgaben aufgerufen, um ihre beste Lösung zu ermitteln. Dabei wird die Rechenzeit beschränkt, es wird also darauf ankommen, möglichst zielgerichtet eine lukrative Lösung zu finden. Bei den einfachen Runden ([6,7] 42) wird weniger Zeit zur Verfügung stehen, als bei späteren Runden. Die erreichten Punkte der besten Lösung jedes Programms werden normalisiert und über alle Runden summiert. Werden invalide Lösungen eingereicht, z.B. Zwischenergebnisse <= 0 oder syntaktische Fehler wie fehlende Klammern, wird das entsprechende Programm von der Wertnug ausgeschlossen.

Preise

Wie bei den letzten Wettbewerben wird es natürlich wieder attraktive Preise geben. Genaueres zu den Preisen werden wir beim Shootout bekannt geben.

Das Wichtigste

Viel Spaß beim Knobeln und Bearbeiten und viel Erfolg!