Projektspezifikation

Abgabefrist für das Projekt ist Dienstag, der 9. August um 12:00 Uhr. Die Abgabefrist kann auf begründeten Antrag verlängert werden. Schreiben Sie dazu bitte eine Mail an Ihren Tutor bzw. Ihre Tutorin. Wir empfehlen aber sehr, das Projekt sobald wie möglich fertig zu stellen. Die Erfahrung vergangener Jahre zeigt, dass man im Programmieren schnell aus der Übung kommt und es sehr viel mehr Arbeit ist, nach einer längeren Pause wieder anzufangen.

Es gibt drei Projekte zur Auswahl:

Projekt 1: Nerdle, das Spiel

Projekt 2: Nerdle, automatischer Löser

Projekt 3: Ein Projekt eigener Wahl (nur für Fortgeschrittene)

Im Folgenden werden wir zunächst die Spiellogik von Nerdle erklären und danach die drei Projekte detaillierter beschreiben.

Die folgenden Beschreibungen sind noch nicht perfekt und können bis zur nächsten Woche noch leicht angepasst werden.
Die wesentlichen Elemente stimmen aber.

Das Spiellogik von Nerdle

• Selber spielen, dann versteht man es am besten :-)

• Zu Beginn wird zufällig eine mathematische Gleichung ausgewählt, die aus exakt acht Symbolen besteht, zum Beispiel 23+34=57. Welche Gleichungen genau erlaubt sind, wird im Abschnitt "Details" erklärt.

• Ziel des Spiels ist es, die gewählte Gleichung zu "erraten". Zu Beginn kann man wirklich nur raten, im Laufe des Spiele bekommt man Hinweise, die einem helfen, den Raum der möglichen Lösungen einzugrenzen.
• Das Spiel verläuft in Runden
• In jeder Runde muss man eine Gleichung bestehend aus exakt 8 Zeichen eingeben. Es werden nur Eingaben akzeptiert, die auch eine mögliche Lösung sein könnten, siehe zweiter Punkte oben und den Abschnitt "Details".
• Nach der Eingabe erhält man Hinweise, indem jedes Zeichen mit einer der folgenden drei Farben unterlegt wird: grün, magenta, schwarz. Grün bedeutet, dass dieses Zeichen in der zu erratenden Gleichung an genau dieser Stelle vorkommt. Magenta bedeutet, dass dieses Zeichen in der zu erratenden Gleichung vorkommt, aber nicht an dieser Stelle. Schwarz bedeutet, dass dieses Zeichen nicht in der zu erratenden Gleichung vorkommt. Zur Einfärbung, wenn ein Zeichen mehrmals eingegeben wurde, siehe Abschnitt "Details"
• Die Eingabe und Hinweise jeder Runde werden in einer Zeile dargestellt. In der ersten Runde füllt man die erste Zeile aus, usw. Es gibt insgesamt sechs Zeilen und damit maximal sechs Runden. Errät man die Gleichung innerhalb von sechs Runden (in der entsprechenden Zeile sind dann alle Zeichen grün unterlegt), hat man gewonnen. Sonst hat man verloren.

Details

• Erlaubte Gleichungen: Erlaubte Operatoren sind die der vier Grundrechenarten, also * + - / . Es gibt genau ein Gleichheitszeichen. Rechts vom Gleichheitszeichen dürfen nur Ziffern stehen. Es gibt keine Klammern und keine unären Operatoren wie in +3 oder -4. Es gibt keine führenden Nullen wie in 04.

• Farbliche Unterlegung: Wenn ein Zeichen mehrfach eingegeben wurde, wird zuerst geschaut, an welchen Stellen dieses Zeichen auch in der zu erratenden Gleichung vorkommt. Diese Zeichen werden alle grün hinterlegt. Nehmen wir an, das Zeichen wurde noch an k weitere Stellen eingegeben. Wenn das Zeichen in der zu erratenden Gleichung an k' nicht-grünen Stelle vorkommt, dann werden k' dieser k weiteren Stellen magenta eingefärbt (welche ist egal) und die übrigen schwarz.

• Grafik: Jedes Zeichen steht zentriert in einer Box. Alle acht Boxen einer Zeile sind gleich groß und zwischen den Boxen ist etwas Abstand. Auch zwischen den Zeilen ist etwas Abstand. Die Boxen sind und während der Eingabe grau. Nach der Eingabe ändert sich die Farbe entsprechend der Hinweise, wie oben beschrieben. Die Zeichen werden immer in weiß und fett gemalt.

• Tastatureingabe: In der Zeile der aktuellen Eingabe gibt es einen Cursor (die entsprechenden Box ist leicht umrandet). Wird eine Ziffer oder einer der vier zulässigen Operatoren oder ein Gleichheitszeichen eingegeben, ändert sich das Zeichen unter dem Cursor entsprechend und der Cursor wird um eins nach rechts bewegt (falls er nicht schon ganz rechts ist). Mit den entsprechenden Pfeiltasten kann man den Cursor nach links oder rechts bewegen. Bei der Eingabe von backspace hängt das Verhalten davon ab, ob unter dem Cursor ein Zeichen steht. Falls ja, wird das Zeichen gelöscht und der Cursor bewegt sich nicht. Falls nein und der Cursor nicht ganz links steht, wird der Cursos um eins nach links bewegt und falls dort ein Zeichen steht, wird es gelöscht.

Projekt 1: Nerdle, das Spiel

Aufgabe: Implementieren Sie das oben beschriebene Spiel Nerdle mit Konsolengrafik.

Folgende Anforderungen müssen Sie mindestens erfüllen, um volle Punktzahl zu erreichen.

• Korrekte Implementierung der oben beschriebenen Spiellogik, Grafik und Tastenbedienung.
• Zu Beginn muss jede gültige Gleichung die gleiche Wahrscheinlichkeit haben, ausgewählte zu werden (unter der Annahme eines perfekten Zufallszahlengenerators).

• Verwendung einer TerminalManager Klasse (mit Unterklassen) von der Art wie beim 10. Übungsblatt. Sie können die Klassen entsprechend den Anforderungen des Spiels abändern.

• Spiellogik, Ausgabe (Grafik) und Eingabe (Tastendrücke) sollten in getrennten Funktionen stehen. Für jede Methode, die zur Spiellogik oder zur Ausgabe gehört, sollte es einen Unit Test geben. Für die Methoden, die die Eingabe einlesen, brauchen Sie keinen Unit Test zu schreiben.

• Achten Sie selbstverständlich auf alles andere, was Sie in der Vorlesung gelernt haben: gutes und sinnvolles Klassendesign, Trennung in .h und .cpp Dateien, Einteilung in public/private/protected, const correctness, valgrind correctness, sinnvolle Übergabe von Argumenten (ohne unnötiges und teures Kopieren von Objekten), etc.

• Es gelten natürlich auch weiterhin die 10 Gebote und die § 2386 und 2387 BGB.

Wenn Sie möchten, können Sie ihr Spiel um beliebige Funktionalitäten erweitern (müssen es aber nicht, um volle Punktzahl zu bekommen). Hier sind einige Ideen:

• Konfigurierbare Anzahl von Zeichen pro Zeile (9, 10 oder 11 spielen sich auch sehr gut)
• Konfigurierbare Anzahl von Zeilen
• Diverse Verschönerungen der Grafik
• Motivierende Rückmeldung an den Spieler bzw. die Spielerin, wie zum Beispiel "das dauert aber ganz schön lange" oder "schon wieder falsch", wenn mann die Lösung in der zweiten Zeile immer noch nicht gefunden hat.

Projekt 2: Nerdle, automatischer Löser (Solver)

Aufgabe: Implementieren Sie ein Programm, das Nerdle so spielt, dass die Gleichung in möglichst wenigen Runden (Zeilen) gefunden wird.

Als Hilfestellung stellen wir Ihnen eine statische Bibliothek libnerdle.a, sowie die Header-Datei NerdleBenchmark.h. Sie finden die Dateien auf dem SVN unter public/code/projekt. Hier eine kurze Erklärung dazu:

1. Die Header-Datei enthält die Deklaration der Klasse NerdleGameState: ein Objekt dieser Klasse stellt den aktuellen Zustand des Spiels dar (bereits erfolgte Eingaben und die farblichen Unterlegungen dazu).

2. Die Header-Datei enthält außerdem die Deklaration der abstrakten Basisklasse NerdleSolver: Für Ihren Solver sollten Sie eine Unterklasse erzeugen, die insbesondere die Methode nextGuess überschreibt ("override"). Die Methode nextGuess ist die zentrale Methode Ihres Solvers: sie nimmt als Argument den aktuellen Zustand des Spiels und berechnet daraus die nächste Eingabe und gibt sie zurück.

4. Die Bibliothek libnerdle.a liefert die Implementierung einer Grafik, die den Anforderungen des Projekts 1 entspricht, und eines Benchmarks, mit dem Sie Ihren Solver auf einer von uns vorgegebenen Menge von zu erratenden Gleichungen laufen lassen können. Das Vorgehen Ihres Solvers wird dabei grafisch dargestellt (Sie können es automatisch durchlaufen lassen, anhalten und Schritt für Schritt durchgehen) und es werden Statistiken zur Qualität angezeigt, mit denen Sie nachvollziehen können, ob Ihr Solver schon den Anforderungen genügt. Sie können diese Bibliothek wie eine .o Datei einfach dazulinken oder mit -L. -lnerdle (siehe Vorlesung 2). Die Bibliothek enthält eine main Funktion, die den Benchmark ausführt. Sie werden es sehen, wenn Sie das Ü11 bearbeiten.

Folgende Anforderungen müssen Sie erfüllen, um volle Punktzahl zu erreichen.

• Ihr Solver muss für Eingaben der Länge 8, 9, 10 und 11 funktionieren.

• 80% der Funktionalität gemäß Bewertungsschema sind erreicht, wenn Ihr Solver im Durchschnitt nicht mehr als die folgende Anzahl von Runden braucht. Für Eingabelänge 8: TODO. Für Eingabelänge 9: TODO. Für Eingabelänge 10: TODO. Für Eingabelänge 11: TODO. Diese Werte erreicht man schon mit einem konzeptionell einfachen Server, der in jeder Runde alle Eingaben bestimmt, die mit allen bisher erhaltenen Hinweisen in Einklang sind, und davon eine zufällige wählt.

• Die restlichen 20% der Funktionalität gemäß Bewertungsschema sind erreicht, wenn Ihr Solver im Durchschnitt nicht mehr als die folgende Anzahl von Runden braucht. Für Eingabelänge 8: TODO. Für Eingabelänge 9: TODO. Für Eingabelänge 10: TODO. Für Eingabelänge 11: TODO. Diese Werte erreicht man, wenn man vorgeht wie unter dem vorherigen Punkt beschrieben, aber aus der Menge der möglichen Lösungen etwas geschickter wählt als rein zufällig.

• Ihr Solver sollte hinreichend effizient sein. Pro Benchmark sollte die Laufzeit maximal TODO betragen.

Projekt 3: Ein Projekt Ihrer Wahl

Alternativ zu den beiden oben beschriebenen Projekten können Sie auch ein Projekt Ihrer Wahl bearbeiten.

• Ein Projekt eigener Wahl ist nur für diejenigen Kursteilnehmer:innen gedacht, denen die bisherigen Übungsblätter leicht gefallen sind und die dort eine hohe Punktzahl erreicht haben.

• Das Projekt muss von Umfang und Komplexität her vergleichbar sein zu den beiden oben beschriebenen Projekten.
• Sie müssen in der Lage sein, das Projekt selbstständig durchzuführen und bei eventuellen Problemen eigenständig Lösungsstrategien zu erarbeiten. Sie können bei Problemen natürlich gerne im Forum nachfragen. Sie müssen aber damit rechnen, dass wir Ihnen nicht bei jedem einzelnen Problem weiterhelfen können.
• Sind diese Voraussetzungen erfüllt, schreiben Sie bitte bis spätestens Donnerstag, den 21. Juli 2022, eine kurze Mail an Ihren Tutor (mit Cc an Johannes Kalmbach und Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, warum es in Umfang und Komplexität mit Projekt 1 oder 2 vergleichbar ist (ebenfalls ein Absatz). Wir werden Ihnen dann bis spätestens Freitag, den 22. Juli 2022 Bescheid geben, ob wir einverstanden sind.
• Sollten wir einverstanden sein, sind Sie nicht verpflichtet, dieses Projekt auch tatsächlich zu bearbeiten. Sie können jederzeit wieder zu Projekt 1 oder Projekt 2 wechseln.