Programmierwettbewerb im Sommersemester 2007: Die Aufgabe

Die Aufgabe

Alle Informatiker kennen die Antwort, aber wie heißt die Frage? Diese Frage möchten wie 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 den 4 Grundrechenarten gebildet werden kann und als Resultat die gesuchte Zahl ergibt.

Ein kleines Beispiel:
Gegeben sei 42 und die Liste von Zahlen [1,1,2,3,5,8].
Eine Lösung ist 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 wissen, welche arithmetischen Operationen zugelassen sind und wie die Komplexität eines Ausdrucks gemessen wird.

Die Spielregeln

  • Es wird nur mit natürlichen Zahlen ab 1 gerechnet. Auch alle Zwischenergebnisse müssen immer natürliche Zahlen sein.
    Beispiel:
    (1 + 1) - 1 ist gültig,
    (1 - 1) + 1 ist nicht erlaubt.
  • Als arithmetische Operatoren sind die Addition (+), die Subtraktion (-), die Multiplikation (*) und die Division (/) erlaubt.
  • Die Division muss aufgehen, es darf kein Rest entstehen.
    Beispiel:
    3 / 2 ist nicht gültig.
  • Nur mit den vier Grundrechenarten zu rechnen kann auf die Dauer etwas langweilig werden, außerdem findet man für viele Zahlen dann gar keinen Ausdruck.
    Daher werden zwei etwas ungewöhnliche Operatoren zusätzlich erlaubt: <*> und <+>.
    Diese sind folgendermaßen definiert:
    x <*> y ist gleichwertig zu 3 * x - 2 * y,
    x <+> y ist gleichwertig zu 2 * x - 3 * y.
    Eine Lösung für das obere Beispiel mit 42 ist dann auch: (3 * (5 <*> 2)) <+> 8
  • Die Komplexität eines Ausdrucks wird folgendermaßen festgelegt:
    Alle Zahlen die in dem Ausdruck vorkommen und alle Zwischenergebnisse werden aufsummiert, das Resultat ist die Komplexität.
    Beispiele:
    Die Komplexität von 2 + (5 * 8) ist 97,
    die von 3 + ((8 * 5) - 1) ist 138
    und die von (5 + (((8 <*> 1) <*> 2) <+> 1)) / 3, auch eine Lösung für 42, ist 393.
    Diese letzte Lösung ist also schon ziemlich kompliziert, was unter anderem darin begründet ist, dass die äußerste Operation eine Division ist.
  • Der Wertebereich der Zahlen wird in den zu lösenden Aufgaben den Bereich der 32 Bit Integer Zahlen nicht überschreiten.

Die Aufrufkonventionen

Die Lösungsprogramme werden folgendermaßen aufgerufen:
progName <Liste erlaubter Zahlen> <gesuchte Zahl>
Die Liste der Zahlen wird als [z1,z2,...,zn] angegeben. Bei einem Aufruf aus einer shell ist diese Liste üblicherweise in Hochkommas zu setzen. Diese Liste wird immer mindestens eine Zahl enthalten. Es stehen keine Leerzeichen in der Liste.

Beispiel:
./theQuestion "[1,1,2,3,5,8]" 42

Die Ausgabe

Die gefundenen Ausdrücke werden auf der Standardausgabe ausgegeben. Es ist möglich mehrere Lösungen auszugeben, jede Lösung wird auf eine Zeile geschrieben. Leerraum innerhalb der Lösungsausdrücke sind erlaubt aber nicht notwendig. Als letzte Zeile wird eine Zeile nur aus einem "." bestehend ausgegeben, um anzuzeigen, dass ein Programm sich normal beendet hat. Die letzte ausgegebene Lösung zählt.

Tipp: Wenn Sie mit gepufferter Ausgabe arbeiten, leeren Sie bitte den Ausgabepuffer explizit nach der Ausgabe einer Lösung, damit die Lösung nicht versehentlich im Ausgabepuffer stehen bleibt.

Die Ausdrücke müssen nach folgender kontextfreien 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

  • Als Programmiersprachen sind alle Sprachen erlaubt, die auf einem Standard Linux Rechner in den Rechenzentren der FH Wedel zur Verfügung stehen.
  • Die Programme bekommen sämtliche Eingaben über Kommandozeilen-Parameter. Andere Eingabekanäle dürfen nicht verwendet werden. Die Ausgabe erfolgt ausschließlich über die Standard-Ausgabe, und zwar pro Lösung genau eine Zeile, also leeren Sie bitte nach der Ausgabe einer Zeile bei gepufferter Ausgabe immer den Ausgabepuffer explizit.
  • Die Entwicklung der Programme erfolgt wie bei den Übungen über das Versionsverwaltungssystem der FH Wedel. Hierbei muss die Entstehung der Software nachvollziehbar sein, das heißt, nach jedem größeren Entwicklungsschritt sind die neuen Quellen in das Repository einzuchecken. Dieses vielleicht restriktiv klingendes Vorgehen hat mehrere Vorteile: Zum einem wird die Arbeit im Team dadurch erleichtert, gerade dann, wenn die Mitglieder räumlich entfernt arbeiten. Weiter hat man immer eine Datensicherung und kann bei neuen Fehlern auf eine alte Version zurückgreifen. Wir möchten damit aber auch die Versuchung reduzieren, ein fertiges Programm zu nehmen und es unter eigenem Namen laufen zu lassen.
  • Das Projekt sollte auf folgende Art organisiert werden: Im Wurzelverzeichnis muss eine Datei mit Namen Makefile liegen. Diese dient zur Erzeugung des ausführbaren Programms mit dem make System. Im Makefile muss immer das default-Ziel all enthalten sein, das zur Erzeugung des Programms verwendet wird. Sollte das Programm in einer interpretierten Sprache geschrieben werden, so ist hier eine leere Aktion einzutragen. Das Programm muss folgenden Namen tragen pw<gruppennummer>.solve, ausführbar sein und genau in diesem Verzeichnis liegen. Sollten noch weitere Dateien für den Aufruf des Programms benötigt werden, zum Beispiel bei einem Java Programm, das über ein shell-Skript aufgerufen wird um den CLASSPATH zu setzen, so sind alle diese Daten in ein direktes Unterverzeichnis mit Namen pw<gruppennummer>/ zu speichern. Zugriffe auf diese Dateien müssen über relative Pfadnamen gemacht werden, damit ein Verschieben in ein Installationsverzeichnis möglich wird.
  • Zu jeder Lösung gehört ein Projektname. Um den Namen des Projekt festzulegen, definiert man im Makefile ein Ziel: name. Mit make name wird also der Projektname auf die Standardausgabe geschrieben. Der Projektname darf aus genau einer Zeile mit maximal 40 Zeichen bestehen.
  • Ein Minibeispiel für ein Projekt findet man in dem pw00.tar.gz Archiv.
  • Zu dem Wettbewerb gibt es eine Newsgroup: fhw.programmierwettbewerb.

Der Wettbewerb

Die Sieger werden nach dem Prinzip der Reise nach Jerusalem ausgespielt. In jeder Runde wird eine Aufgabe, eine Liste von Zahlen und eine gesuchte Zahl vorgegeben. Dann werden die Lösungsprogramme nacheinander aufgerufen, um ihre beste Lösung zu ermitteln. Dabei wird die Rechenzeit beschränkt werden. Es wird also darauf ankommen, möglichst zielgerichtet eine komplizierte Lösung zu konstruieren oder zu suchen. Bei den einfachen Runden (pwxy.solve "[6,7]" 42) wird eine geringe Zeit zur Verfügung stehen, in den späteren Runden wird die Zeit erhöht werden. Am Ende jeder Runde scheiden die Programme aus, die keine Lösung gefunden haben, oder das Programm mit der einfachsten, der schlechtesten Lösung. Gibt es mehrere gleich schlechteste Lösungen, so scheidet kein Programm aus. Bei der folgenden Runde werden dann aber zwei Programme ausscheiden.

Das Wichtigste

Viel Spaß und Freude beim Knobeln und Bearbeiten und beim Gewinnen.

P.S.

An den Preisen wird noch fleißig von den Projektorganisatoren gearbeitet.