5.1 Test implementieren#

Ziel: Für zwei vorgegebene Tests sollen sie eine zugehörige Funktion implementieren.

Beispiel: Herausfinden aus einem Labyrinth#

In dieser Aufgabe ist ein Labyrinth gegeben. Ähnlich zu einem Adventure-Computerspiel kann hier nur herausgefunden werden, wenn alle im Labyrinth vorhandenen Gegenstände (Zauberbuch, Zaubertrank und Zauberstab) gefunden wurden. Dazu muss das Labyrinth erkundet werden. Die Items werden definiert als Aufzählungstyp:

enum class Item {
    NOTHING, SPELLBOOK, POTION, WAND
};

Das Labyrinth (Maze) ist aufgebaut als eine verschachtelte struct: für jeden einzelnen Raum wird eine solche angelegt und in dieser wird, zum einen, hinterlegt ob und welches Objekt hier vorhanden ist. Zum anderen wird für jede der vier Himmelsrichtungen über einen Zeiger auf den dort angeschlossenen Raum (cell) verwiesen bzw. ein nullptr verwendet, wenn es in der Richtung nicht weitergeht.

Der Typ MazeCell ist als definiert:

 struct MazeCell {
    Item whatsHere; // Item in dem Raum, falls vorhanden.                                  
    MazeCell* north; // Cell nördlich -- oder nullptr, wenn wir nicht nach Norden gehen können.
    MazeCell* south;
    MazeCell* east; 
    MazeCell* west;
};

Hier ist ein Beispiel für ein kleines \(4 \times 4\)-Labyrinth gegeben. Die Startposition ist mit einem Smiley markiert und die Positionen der drei Gegenstände mit Emojis. Für jede MazeCell gibt es eine Variable whatsHere, die angibt, welcher Gegenstand sich gegebenenfalls an dieser Position befindet. Bei leeren Zellen wird whatsHere auf den Wert Item::NOTHING gesetzt.

Um sich im Labyrinth zu bewegen, muss eine Reihe von Richtungsentscheidungen vorgegeben werden, z.B. “ESNWWNNEWSSESWWN”. So wird jeder Weg durch eine Folge von Buchstaben dargestellt (N für Norden, W für Westen usw.).

Teilaufgabe 1: Pfad überprüfen#

Die erste Aufgabe ist es, die Funktion zu schreiben, die für einen vorgegebenen Pfad (Folge von Richtungsanweisungen wie “NSEESW”) für ein Labyrinth überprüft, ob dies ein zugelassener Pfad ist (es wird nicht versucht in Richtung eines nullptr zu laufen) und die testet, ob alle drei Gegenstände eingesammelt wurden.

Implementiere dazu in der Datei Labyrinth.cpp die Funktion

bool isPathToFreedom(MazeCell* startLocation, const std::string& path);

Diese Funktion nimmt als Eingabe deine Startposition im Labyrinth und eine Zeichenkette, die nur aus den Zeichen ‘N’, ‘S’, ‘E’ und ‘W’ besteht, und gibt dann zurück, ob dieser Pfad dich aus dem Labyrinth entkommen lässt. Ein Pfad lässt dich aus dem Labyrinth entkommen, wenn

der Pfad legal ist, d.h. wenn er keinen Schritt macht, der in der aktuellen MazeCell nicht erlaubt ist, und
der Pfad das Zauberbuch, den Zauberstab und den Zaubertrank aufnimmt. Die Reihenfolge, in der diese Gegenstände aufgesammelt werden, ist irrelevant und es ist in Ordnung, wenn der Pfad nach dem Aufsammeln aller Gegenstände weitergeht.

Für diese Funktion sind zwei Tests vorgegeben. Für zwei vorgegebene Labyrinthe sind legale Pfade als Sequenzen von Richtungen gegeben, die aus den Labyrinthen führen (d.h. alle drei Gegenstände finden und nie einem nullptr versuchen zu folgen). Implementiere die Funktion so, dass die Tests erfolgreich durchlaufen und die Funktion auch auf anderen Labyrinthen und korrekten Pfaden funktionieren wird.

Grundlegende Struktur#

Labyrinth.h

#pragma once
#include <string>

/**
 * Type representing an item in the maze.
 */
enum class Item {
    NOTHING, SPELLBOOK, POTION, WAND
};

/**
 * Type representing a cell in the maze.
 */
struct MazeCell {
    Item whatsHere; // Which item, if any, is present.

    MazeCell* north;
    MazeCell* south;
    MazeCell* east;
    MazeCell* west;
};

/**
 * Given a location in a maze, returns whether the given sequence of
 * steps will let you escape the maze.
 *
 * To escape the maze, you need to find the Potion, the Spellbook, and
 * the Wand. You can only take steps in the four cardinal directions,
 * and you can't move in directions that don't exist in the maze.
 */
bool isPathToFreedom(MazeCell* start, const std::string& moves);

test_maze.cpp

#define BOOST_TEST_MODULE boost_test_sequence_per_element
#include <boost/test/included/unit_test.hpp>

#include "MazeGenerator.h"
#include "Labyrinth.h"
#include <iostream>
#include <string>

/* Change this constant to contain your name.
 *
 * WARNING: Once you've set set this constant and started exploring your maze,
 * do NOT edit the value of kYourName. Changing kYourName will change which
 * maze you get back, which might invalidate all your hard work!
 */
const std::string kYourName = "TODO: Replace this string with your name.";

/* Change these constants to contain the paths out of your mazes. */
const std::string kPathOutOfNormalMaze = "SESSWENNENSESS"; //TODO: Replace this string with your path out of the normal maze.";
const std::string kPathOutOfTwistyMaze = "ESWEESWENE"; //TODO: Replace this string with your path out of the twisty maze.";

BOOST_AUTO_TEST_CASE( test_maze )
{
    /* Generate the maze.
     */
    MazeCell* startLocation = mazeFor(kYourName);
    BOOST_TEST( isPathToFreedom(startLocation, kPathOutOfNormalMaze) );    

    /* Generate the twisty maze.
     */
    MazeCell* twistyStartLocation = twistyMazeFor(kYourName);
    
    BOOST_TEST(isPathToFreedom(twistyStartLocation, kPathOutOfTwistyMaze));

}

main.cpp

#include "MazeGenerator.h"
#include "Labyrinth.h"
#include <iostream>
#include <string>

/* Change this constant to contain your name.
 *
 * WARNING: Once you've set set this constant and started exploring your maze,
 * do NOT edit the value of kYourName. Changing kYourName will change which
 * maze you get back, which might invalidate all your hard work!
 */
const std::string kYourName = "TODO: Replace this string with your name.";

/* Change these constants to contain the paths out of your mazes. */
const std::string kPathOutOfNormalMaze = "SESSWENNENSESS"; //TODO: Replace this string with your path out of the normal maze.";
const std::string kPathOutOfTwistyMaze = "ESWEESWENE"; //TODO: Replace this string with your path out of the twisty maze.";

int main(int argc, char* argv[]) {
    /* Generate the maze.
     *
     * Note: Don't set a breakpoint on this line. Otherwise, you'll see startLocation before
     * it's been initialized.
     */
    MazeCell* startLocation = mazeFor(kYourName);
    
    /* Set a breakpoint here to explore your maze! */
    if (isPathToFreedom(startLocation, kPathOutOfNormalMaze)) {
        std::cout << "Congratulations! You've found a way out of your labyrinth." << std::endl;
    } else {
        std::cout << "Sorry, but you're still stuck in your labyrinth." << std::endl;
    }
    
    
    /* Generate the twisty maze.
     *
     * Note: Don't set a breakpoint on this line. Otherwise, you'll see twistyStartLocation before
     * it's been initialized.
     */
    MazeCell* twistyStartLocation = twistyMazeFor(kYourName);
    
    /* Set a breakpoint here to explore your twisty maze! */
    
    if (isPathToFreedom(twistyStartLocation, kPathOutOfTwistyMaze)) {
        std::cout << "Congratulations! You've found a way out of your twisty labyrinth." << std::endl;
    } else {
        std::cout << "Sorry, but you're still stuck in your twisty labyrinth." << std::endl;
    }
    
    return 0;
}

Makefile

maze: main.cpp Labyrinth.cpp MazeGenerator.cpp
	c++ -Wall -std=c++20 main.cpp Labyrinth.cpp MazeGenerator.cpp -o main

test_maze: test_maze.cpp
	c++ -Wall -std=c++20 -I/opt/homebrew/include -L/opt/homebrew/lib -lboost_unit_test_framework test_maze.cpp Labyrinth.cpp MazeGenerator.cpp -o test_maze


clean:
	test ! -f main || rm main
	test ! -f test_maze || rm test_maze

Anweisungen

implementiere die Funktion isPathToFreedom in Labyrinth.cpp.
teste deinen Code gründlich mit unseren Tests. Diese kannst du erzeugen über make test_maze.

Tipp - hier öffnen

Der Code sollte für eine MazeCell zu jedem möglichen Labyrinth funktionieren.
Obwohl das Labyrinth in der vorherigen Abbildung so strukturiert war, dass es bei einer Verbindung von einer Zelle zu einer anderen in Richtung Norden immer eine Verbindung von der zweiten Zelle zurück zur ersten in Richtung Süden gibt, muss dies nicht allgemein gelten!
Ein Pfad kann denselben Ort mehrmals besuchen, auch Orte, an denen sich Gegenstände befinden, können mehrmals besucht werden.
Du musst bei der Lösung dieses Problems keine neuen MazeCell-Objekte zuweisen müssen. Du kannst gerne Variablen vom Typ MazeCell* deklarieren, aber benutze nicht das Schlüsselwort new.
Es steht dir frei, diese Funktion entweder iterativ oder rekursiv zu implementieren, je nachdem, was dir am besten erscheint.
Dein Code sollte das an die Funktion übergebene Labyrinth nicht verändern. Insbesondere solltest du nicht ändern, welche Elemente wo erscheinen oder wohin die Links zeigen.

Referenzen#

Dies Task ist abgewandelt von einem Task des Stanford-Kurses 106B/X zur Programmierung in C++.

Einführung in (C und) C++

5.1 Test implementieren

Contents

5.1 Test implementieren#

Beispiel: Herausfinden aus einem Labyrinth#

Teilaufgabe 1: Pfad überprüfen#

Grundlegende Struktur#

Referenzen#