Projekt zur Vorlesung '''Programmieren in C++''' im Sommersemester 2018
Contents
Es gibt drei Projekte zur Auswahl:
Projekt 1: 橋をかけろ (das Spiel)
Projekt 2: 橋をかけろ (der Löser)
Projekt 3: Ein Projekt eigener Wahl (nur für Fortgeschrittene)
Im Folgenden eine detailliertere Beschreibung der drei Projekte
Projekt 1: 橋をかけろ (das Spiel)
Kurzbeschreibung: Das Spiel Hashiwokakero soll mit Konsolengrafik realisiert werden.
Hintergrund: Eine Online-Version des Spiels findet sich zum Beispiel hier: https://de.puzzle-bridges.com/ .
Anforderungen (Minimum): Folgende Anforderungen müssen für volle Punktzahl mindestens erfüllt sein
Einlesen einer Instanz aus den Formaten .plain und .xy sowie das Einlesen von Lösungen im Format .xy.solution. (Instanzen)
- Bedienung über die Maus.
Wenn ein Lösungsfile (.xy.solution) angegeben wird, ist dieses als Klickfolge auf Inseln zu verstehen, das Spiel sollte entsprechende Brücken bauen oder über ungültige Informieren.
- Konsolengrafik: Um den Klickbereich zu vergrößern soll jede Insel aus mindestens 3x3 Feldern bestehen.
- Farbliche Markierung wenn eine Insel die korrekte Anzahl Brücken besitzt und falls zu viele Brücken vorhanden sind.
- Undo Funktion, wobei die Anzahl Züge die man höchstens hintereinander rückgängig machen kann ein Argument in der Kommandozeile sein sollte (Default: 5).
- Alle Funktionalität, die mit Ein- bzw. Ausgabe zu tun hat, sollte sauber getrennt von den anderen Teilen in eigenen Methoden stehen und diese Methoden brauchen nicht getestet zu werden. Für alle anderen Methoden soll es selbstverständlich wie gehabt einen Unit Test geben.
Es soll selbstverständlich auf alles geachtet werden, was Sie in der Vorlesung gelernt haben: gutes Klassendesign, Trennung in .h und .cpp Dateien, const correctness, valgrind soll ohne Fehler durchlaufen, allgemein die 10 Gebote des Ü1.
Anforderungen (optional): Hier ein paar Ideen für optionale Erweiterungen:
- Generieren von neuen Instanzen (wenn diese konstruktiv erzeugt werden ist ein Solver nicht nötig)
Zur Laufzeit umschaltbarer Markierungsmodus der alle möglichen Nachbarninsel hervorhebt. Im Idealfall ohne das die Insel angeklickt wurde sondern nur durch drüberfahren und h drücken.
- Einlesen mehrerer Instanzen + ein Menu im Programm, in dem man die Instanz auswählen kann + Möglichkeiten, die Instanzen der Reihe nach zu lösen.
- Prüfen ob die Klickfolge minimal war.
- Farben benutzerdefiniert machen.
Ausgeben der Spielerzugfolge als Lösung im Format .xy.solution.
- Animiertes darstellen einer Lösung.
- Was immer Ihnen noch (Sinnvolles und Sinnloses) einfällt.
Projekt 2: 橋をかけろ (automatischer Löser)
Kurzbeschreibung: Ein Programm, das versucht eine gegebene Instanz zu lösen und dabei einfache Strategien verwendet um nicht nur Brute-Force zu nutzen, auch sollten unlösbare Instanzen effizienter als nur durch Probieren erkannt werden. Die im SVN unter public/projekt angegebenen Instanzen sollten dabei alle korrekt gelöst werden.
Hintergund: Grundlegende Techniken werden auf http://www.conceptispuzzles.com/de/index.aspx?uri=puzzle/hashi/techniques erklärt.
Anforderungen (Minimum): Folgende Anforderungen müssen mindestens erfüllt sein, um die volle Punktzahl erreichen zu können.
Einlesen einer Instanz aus den Formaten .plain und .xy. (Instanzen)
Ausgabe der Lösung(en) in den Formaten .plain.solution und .xy.solution. .plain.solution für die direkte optische Verifikation, .xy.solution für die Verifikation durch eine Spielinstanz.
- Dieselben Anforderungen an Unit Tests und allgemeine Eigenschaften des Codes wie für Projekt 1.
- Beim Lösen nicht einfach nur probieren sondern auf die grundlegenden Techniken zurückgreifen -siehe Link
- 1. Inseln mit einem einzigen Nachbarn
- 2. Inseln mit einer 3 in der Ecke, einer 5 an der Seite und einer 7 in der Mitte
- 3. Besondere Fälle von 3 in der Ecke, 5 an der Seite und 7 in der Mitte
- 4. Der besondere Fall einer 4 an der Seite
- 5. Der besondere Fall einer 6 in der Mitte
Anforderungen (optional): Hier ein paar Ideen für optionale Erweiterungen:
- Beim Lösen die Isolierungstechniken beachten
- Ausgabe aller Lösungen.
Formate für Projekt 1 und 2
Allgemein: Zeilen beginnend mit # sind Kommentare und müssen nicht vorkommen, bzw. können ignoriert werden.
.plain / .plain.solution
Die Instanz ist explizit gegeben, Dateiendung .plain:
# 7:7 (plain)
1 2
2 5 1
4 7 3
2
2
3 3 2 3Für Lösungen Dateiendung .plain.solution:
1----2 2==5-1| H | 4==7--3 H 2H | H H2 | 3-3 2=3
.xy / .xy.solution
Für Instanzen .xy:
# 7:7 (xy) # x,y,count 0,1,2 0,3,4 0,6,3 1,0,1 2,4,2 2,6,3 3,1,5 3,3,7 3,5,2 4,6,2 5,1,1 6,0,2 6,3,3 6,6,3
Für Lösungen .xy.solution (Koordinaten der angeklickten Inseln):
# (xy.solution) # x1,y1,x2,y2 # Single bridge 1,0,6,0 # Double bridge 0,1,3,1 0,1,3,1 3,1,5,1 0,3,3,3 0,3,3,3 3,3,6,3 0,6,2,6 4,6,6,6 4,6,6,6 1,6,3,6 3,1,3,5 3,1,3,5 0,3,0,6 0,3,0,6 2,4,2,6 2,4,2,6 3,3,3,5 6,3,6,6
Projekt 3: ein Projekt eigener Wahl
Kurzbeschreibung: Ein Projekt eigener Wahl, das den beiden vorherigen von Umfang und Komplexität vergleichbar ist.
Hintergrund: Ihnen überlassen.
Anforderungen (Minimum):
- Ein Projekt eigener Wahl ist nur für diejeniger Kursteilnehmer*innen gedacht, die in den bisherigen Übungsblättern fast volle Punktzahl erreicht haben und die das bisher vermittelte Wissen relativ problemlos voll durchdrungen haben.
- Das Projekt sollten von Umfang und Komplexität her den beiden Projekten oben vergleichbar sein.
- Sie sollten in der Lage sein, das Projekt selbsttätig durchzuführen. (Bei allgemeinen Programmierfragen können Sie trotzdem gerne auf das Forum zurückgreifen.)
- Sind diese Voraussetzungen erfüllt, bitte bis Donnerstag, den 12. Juli 2018, eine kurze Mail an Ihren Tutor / Ihre Tutorin (mit Cc an Axel Lehmann und an Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, dass es an Umfang und Komplexität mit Projekt 1 oder 2 oben vergleichbar ist (ein Absatz). Wir werden diese Fälle dann am Montag, den 16. Juli 2018 von 15 - 16 Uhr besprechen und Ihnen dann anschließen Bescheid geben, ob wir einverstanden sind.