Aufgabenblatt 2

Beachten Sie die leicht modifizierten Anforderungen an Ihre Lösung im Abschnit Bewertungsgrundlage

Abgabetermin ist der 22.05.2018

Aufgabe 0

Die Reise der Abenteurerin durch ein Labyrinth beginnt am nordwestlichsten Punkt auf der Karte. In ihrer Hand befindet sich ein magischer Schlüssel, auf dem sich eine veränderliche Zahl befindet.

Je nachdem, wie sie sich im Labyrinth fortbewegt, verändert sich dieser Zahlenwert. Begibt sie sich in einen Raum, in dem eine mathematische Operation auf dem Boden eingraviert ist, wird diese auf die Zahl auf ihrem Schlüssel angewendet, zusammen mit der eingravierten Zahl des nächsten Raumes, den sie betritt.

Im südöstlichsten Teil des Labyrinths befand sich eine Schatztruhe, die sich nur öffnete, wenn der darauf eingravierte Zahlenwert der Zahl auf dem Papier entsprach und den dafür kürzestmöglichen Pfad zum Schatz einlegte.

• Der Startraum kann nur verlassen und nicht wieder betreten werden
• Der magische Schlüssel darf nur Werte größer Null haben (sonst verschwindet er).
• Die Katakomben lösen eine Falle aus, sollte die Abenteurerin zu lange brauchen und/oder mit dem falschen Schlüsselwert den Schatzraum betreten
• Der Startraum ist immer oben links (Nordwesten)
• Der Schatzraum befindet sich unten rechts (Südosten)
• Ist der Schatz erreicht, kann die Abenteurerin problemlos nach Hause gehen.

22  -   9
 +  4   -
 4  *  11
Schatztruhenwert: 93

(Beispielaufgabe, Lösung SSONOS)

In ihrem letzten Abenteuer hat sie die Herausforderung aus der obigen Abbildung gemeistert. Sie notierte sich als Lösung SSONOS, und meinte damit:

• N, um in den nördlichen Raum zu gehen
• S, um in den südlichen Raum zu gehen
• O, um in den östlichen Raum zu gehen
• W, um in den westlichen Raum zu gehen

Ihr Abenteuer verlief also wie folgt:

• Die Schritte SS bewirkten, dass Startwert 22 und die Zahl 4 sich auf dem Schlüssel addieren -> 26.
• Die Schritte ON bewirkten, dass der aktuelle Schlüsselwert 26 mit 4 multipliziert wird -> 104
• Die Schritte OS bewirkten, dass der aktuelle Schlüsselwert 104 um 11 subtrahiert wird -> 93
• Somit konnte sie den Raum mit der Truhe gefahrlos betreten und den Schatz einsacken

Selbstsicher, dass sie einen Algorithmus für den kürzesten Weg gefunden hat, wagt sie sich in die Katakomben von Keoz (Ihre Puzzleeingabe), von denen sie weiß, dass sie dieselbe Herausforderung darstellen, aber größer sind. Wie wird es ihr dieses Mal gelingen?

Eingabeformat und Lösungskontrolle

Die Puzzleeingabe liest sich wie folgt:

<Schatztruhenwert>
<Anzahl folgender Zeilen>
<Zahl>;<Operation>;<Zahl>;...
...

Ein Beispiel:

448
4
27;+;3;-
-;15;*;19
17;+;14;+
+;6;+;9

Hier lautet der Schatztruhenwert 448. Die Katakomben bestehen aus 4 Zeilen. Der Startpunkt hat den Wert 27, der Endpunkt den Wert 9.

Die Lösung für das Beispiel lautet OOSSONSS

Weitere Beispiele, sortiert nach Schwierigkeitsgrad:

• Easy (Input / Output)
• Medium (Input / Output)
• ADS Studie (Input / Output)
• Schwer (Input / Output)
• Hyperschwer (Input / Output)
• Fast Kursniveau (Input / Output)

Bewertungsgrundlage

Die Bewertung der Abgabe besteht aus den unten folgenden Punkten, die ihr Lösungsprojekt enthalten muss. Nehmen Sie als Vorlage die Musterlösung zu Aufgabe 0 zur Hand.

• Eine schriftliche Ausarbeitung als PDF-Dokument in Ihrem GitLab-Projekt:
  • Analyse des Problems. Behandeln Sie die folgenden Punkte:
    • Welcher Problemkategorie ordnen Sie die Aufgabe ein?
    • Was macht das Problem kompliziert?
    • Skizzieren Sie, falls möglich, einen naiven brute-force Lösungsansatz und ermitteln seine Laufzeit in O-Notation und seinen Speicherbedarf.
  • Beschreiben Sie ihren Lösungsansatz
    • Beschreiben Sie eingesetzte Algorithmen/Lösungsstrategien und Datenstrukturen. Zitieren Sie Sekundärquellen, die zur Lösung beigetragen haben.
    • Ermitteln Sie die Laufzeit Ihrer Lösung in O-Notation.
    • Messen Sie die Laufzeit Ihres Programms auf einem Laborrechner der Hochschule. Verändern Sie, wenn es die Aufgabenstellung erlaubt, die Eingabegröße und messen Sie erneut.
    • Messen Sie alle Beispieleingaben und vergleichen Sie die Laufzeiten
• Lösung der Problems in einem Projektordner in Ihrem GitLab-Projekt
  • Das ausschließlich von Ihnen allein geschriebene Programm soll die gestellte Aufgabe auf einem gewöhnlichen Laborrechner der Hochschule in unter einer Minute Laufzeit lösen.
  • Das Lösungsprojekt darf nur als Quellcode abgegeben werden.
  • Eine ausführliche Bau- und Ausführanleitung ist zwingender Bestandteil der Abgabe. Legen Sie gegebenenfalls Makefiles oder andere Bauskripte bei. Das Bauen und Ausführen des Lösungsprojekts muss in wenigen Schritten möglich sein und auf einem Laborrechner der Hochschule vorgeführt werden können.
  • Ihr Programm muss die Puzzleeingabe von der Standardeingabe einlesen.
  • Ihr Programm darf nur Ihre Lösung auf der Standardausgabe ausgeben. Die Lösung muss in der Form den mitgelieferten Beispielen entsprechen. Zusätzliche Ausgabe zu Debuggingzwecken sind aus der Abgabe vorher zu entfernen. Falls Ihr Programm hilfreiche Detailinformationen zur Lösungsfindung ausgeben kann, dokumentieren Sie, wie sie gesondert aktiviert werden kann.

Seien Sie außerdem darauf vorbereitet, Ihr Projekt während des Praktikumstermins vorzustellen und dazu Fragen zu beantworten.

Abgabemodalitäten

Zur Abnahme ist die persönliche Anwesenheit erforderlich. Ihr Lösungsprojekt muss zum Abgabetermin im vorher von Ihnen eingerichtetem persönlichen, privaten GitLab-Projekt abrufbar sein.