Aufgabenblatt 3
Die Bewertungsgrundlage ist auch hier leicht anders. Bitte beachten Sie dies.
Abgabetermin ist der 05.06.2018
Aufgabe 0
England im 18. Jahrhundert: Du bist auf der Flucht! Keine Ahnung, wie du da wieder reingeraten bist, aber als einziger verheirateter Mann der Gruppe hast du deinen verliebten Junggesellen geholfen, die ebenso angetanen Damen des Hauses Montgommery während eines Ausflugs in einer Flusslandschaft zu entführen. Deren Vater, ein kontrollsüchtiger, hochrangiger Armeeoffizier, wird bald davon erfahren und alles in Bewegung setzen, um seine Töchter wiederzubekommen.
Die Flusslandschaft trennt das Gelände vereinfacht gesagt in waagerechte Flächen, diese lassen sich so sehr gut durchnummerieren. Die Fläche ganz im Norden ist der Ort, wo die eine Flucht-Kutsche auf die Gesellschaft wartet.
Die Wachen wurden alle überwältigt, aber es bleibt nur ein Transportmittel, ein Kanu, um die gesamte Gesellschaft zu transportieren.
Jetzt beginnen die Probleme:
- Das Kanu kann, außer dir, nur zwei weitere Personen mitnehmen.
- Das Kanu wird nur von dir gefahren, die anderen Personen sind dazu nicht in der Lage.
- Du brauchst aber mindestens eine(n) weitere(n) Mitfahrer(in), da du sonst das Kanu nicht an und von Land bekommst.
Als wäre das schon nicht schwer genug, beginnt die Gruppe sich kritisch zu beäugen:
- Die Junggesellen werden eifersüchtig. Sollte sich eine Frau ohne ihren versprochenen Mann auf einer Insel zusammen mit einem anderen Mann befinden, wird sich die Gruppe zerstreiten und die Flucht mißlingen. Dass du als verheirateter Mann das Kanu fährst, wird von allen akzeptiert.
Du beginnst auf Fläche 0 der Flusslandschaft.
Beispiel
Fläche 0: Lady Anna und Lady Bella Fläche 1: Lady Annas Geliebter Fläche 2: Lady Bellas Geliebter Fläche 3: Nichts
Als Diagramm:
F3 . .. .. .. ..
F2 . .. .. .. GB
F1 . .. GA .. ..
F0 K LA .. LB ..
- F ist die Flächennummer. Auf der obersten Fläche befindet sich die Flucht-Kutsche.
- L steht dabei für Lady und G für Geliebter von
- K ist die Position des Kanus
- Die Anfangsbuchstaben der Frauen ist glücklicherweise für jede Frau ein anderer
Eine mögliche Lösung sieht nun so aus:
- Bring Lady Anna auf Fläche 1. Das ist in Ordnung, weil dort ihr Geliebter wartet.
F3 . .. .. .. .. F2 . .. .. .. GB F1 K LA GA .. .. F0 . .. .. LB .. - Bring Lady Anna und ihren Geliebten auf Fläche 2. Das geht in Ordnung, keine Eifersucht möglich, da der Geliebte dabei ist.
F3 . .. .. .. .. F2 K LA GA .. GB F1 . .. .. .. .. F0 . .. .. LB .. - Nimm Lady Anna mit auf Fläche 1. Die beiden Geliebten alleine zurückzulassen ist in Ordnung.
F3 . .. .. .. .. F2 . .. GA .. GB F1 K LA .. .. .. F0 . .. .. LB .. - Nimm Lady Anna mit auf Fläche 0. Beide Ladies auf einer Fläche ist in Ordnung.
F3 . .. .. .. .. F2 . .. GA .. GB F1 . .. .. .. .. F0 K LA .. LB .. - Nimm Lady Anna und Lady Bella mit auf Fläche 1. Beide Ladies alleine auf Fläche 1 ist in Ordnung.
F3 . .. .. .. .. F2 . .. GA .. GB F1 K LA .. LB .. F0 . .. .. .. .. - Nimm Lady Anna und Lady Bella mit auf Fläche 2. Beide Ladies sind dort zusammen mit ihren Geliebten, sodass kein Streit entstehen kann.
F3 . .. .. .. .. F2 K LA GA LB GB F1 . .. .. .. .. F0 . .. .. .. .. - Nimm Lady Anna und Lady Bella mit auf Fläche 3. Wieder sind beide Ladies alleine auf einer Fläche.
F3 K LA .. LB .. F2 . .. GA .. GB F1 . .. .. .. .. F0 . .. .. .. .. - Nimm Lady Anna wieder zurück auf Fläche 2. Dort wartet weiterhin ihr Geliebter und passt auf sie auf.
F3 . .. .. LB .. F2 K LA GA .. GB F1 . .. .. .. .. F0 . .. .. .. .. - Nimm den Geliebten von Anna und den von Bella mit auf Fläche 3. Dort passt dieser auf Bella auf. Lady Anna alleine
stört sich daran auch nicht.
F3 K .. GA LB GB F2 . LA .. .. .. F1 . .. .. .. .. F0 . .. .. .. .. - Nimm den Geliebten von Lady Anna mit zur Fläche 2.
F3 . .. .. LB GB F2 K LA GA .. .. F1 . .. .. .. .. F0 . .. .. .. .. - Bring Lady Anna und ihren Geliebten mit auf Fläche 3.
F3 K LA GA LB GB F2 . .. .. .. .. F1 . .. .. .. .. F0 . .. .. .. ..
Wir kommen auf 11 Schritte, bis alle zusammen flüchten können.
Aufgabenstellung
Ihre Eingabe beinhaltet ein Diagramm der Form
F3 K LA GA LB GB
F2 . .. .. .. ..
F1 . .. .. .. ..
F0 . .. .. .. ..
wie im Beispiel beschrieben. Jedoch ist die Gruppe größer als im Beispiel. Es gibt fünf Ladies und fünf Geliebte.
Wie lautet die kleinste Anzahl Schritte, um alle konfliktfrei auf die oberste Ebene zu bekommen?
Hinweise seit dem 29.05.18:
- Sie dürfen davon ausgehen, dass nur 5 Paare und 4 Ebenen existieren.
- Bilden Sie Hashes über die Spielzustände, bei denen Sie Dupletten oder bereits besuchte Zustände ausschließen können.
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:
- Anayse 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.
- Anayse des Problems. Behandeln Sie die folgenden Punkte:
- 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.