C++ Wortsuche



  • Guten Abend,
    wir haben über die Feiertage die Aufgabe bekommen einen Programm in C++ zu schreiben, welches Wörter in mittels txt - Datei bereitgestellten Matrizen sucht. Dafür dürfen wir jedoch nur die C++ iostream und fstream nutzen. Strings sind nicht erlaubt. Das Programm soll die txt von links nach rechts, von rechts nach links, von oben nach unten und von unten nach oben durchsuchen können. Die drei zu suchenden Wörter sollen vom Nutzer zuvor eingegeben werden. Final sollen die gefunden Wörter wie folgt ausgegeben werden: wort [zeile] [spalte] richtung
    Zeile und Spalte bezieht sich hierbei auf den ersten Buchstaben des jeweiligen Wortes. Alle Wörter können mehrmals in der Matrix vorkommen. Ich habe bereits den Quelltext für das Einlesen der txt - Datei, jedoch weiß ich nicht, wie man beim Matrizendurchsuchen vorgehen soll. Diesbezüglich hatten wir noch keine Vorbereitungsseminare 😕

    LG, Peter



  • @Peter98 sagte in C++ Wortsuche:

    jedoch weiß ich nicht, wie man beim Matrizendurchsuchen vorgehen soll

    Was ist das Problem? Wie sieht die "Matrix" aus?

    Strings sind nicht erlaubt.

    YAIT (yet another incompetent teacher)

    wir haben über die Feiertage

    Die sind gleich rum 😉



  • Schöne Aufgabe!

    @Peter98 sagte in C++ Wortsuche:

    Diesbezüglich hatten wir noch keine Vorbereitungsseminare

    ??? Was denn für Vorbereitungsseminare!? Du sollst dir was ausdenken!



  • @manni66 Ich weiß nicht, wie ich die Matrix durchsuchen kann, weil wir das noch nicht 😞

    Die Matrix, die wir bekommen haben sieht so aus:

    i i i i i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i i
    i i i p u m a i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i f i i i i i
    i i i i i i i i i i i i i i u i i i i i
    i i i i i i i i i i i i i i c i i i i i
    i i i i i i i i i i i i i i h i i i i i
    d r a p o e l i i i i i i i s i i i i i
    i i i u i i i i i i i i i i i i i i i i
    i i i m i i i i i i i i i i i i i i i i
    i i i a i i i i i i i i i i i i i i i i
    i i i i i i i i i i i i i i i i i i i s
    i i i i i i i i i i i i i i i i i i i h
    i i i i i i i i i i i i i i i i i i i c
    i i i i i i i i i i i i i i i i i i i u
    i i i i i i i i i i i i i i i i i i i l

    Ich kann die Matrix leider nicht besser hier einfügen 😕 Ach und mir ist aufgefallen, dass ich die Größe vergessen habe. Die Matrix aus der txt soll die Größe [20] [20] haben.

    PS: Feiertage war vielleicht etwas ungünstig formuliert 😃 Haben bis 03.01. noch Ferien 😉



  • @Jockelx
    Tut mir leid, wenn ich vielleicht einen inkompetenten Eindruck mache. Ich habe jedoch absolut keine Idee, wie man mit C++ ohne Strings suchen kann (weil das in der Literatur zum üben auch keiner macht). Ein Vorbereitungsseminar wäre dahingehend schön gewesen, dass man mal sieht, wie die Suche ablaufen kann und wie solche Suchprozesse ablaufen.



  • Und danke erst einmal an euch, dass ihr mir helft 🙂



  • Du könntest mal zeigen was Du bisher gemacht hast.
    Wenn Du Code einfügst dann schreibe bitte in eine Zeile vor Deinem Code ``` und in eine Zeile nach Deinem Code ```. Alternativ markiere Deinen Code und klicke auf das </> in der Symbolleiste über dem Eingabefeld.



  • @Peter98 sagte in C++ Wortsuche:

    Ich habe jedoch absolut keine Idee, wie man mit C++ ohne Strings suchen kann

    Wie gesagt, Sinn ist sich was auszudenken und nicht irgendwelche string-Funktionen zu kennen. Mit c++ hat die Aufgabe nichts zu tun. Du weisst wie man auf Array-Einträge zugreift? Du weisst wie man Zeichen vergleicht? Du kennst Schleifen?
    Mehr braucht es erstmal nicht.



  • @Peter98 sagte in C++ Wortsuche:

    @Jockelx
    Tut mir leid, wenn ich vielleicht einen inkompetenten Eindruck mache. Ich habe jedoch absolut keine Idee, wie man mit C++ ohne Strings suchen kann (weil das in der Literatur zum üben auch keiner macht)

    Wie würdest Du die Aufgabe denn mit Strings lösen?



  • @Peter98 sagte in C++ Wortsuche:

    Ich habe jedoch absolut keine Idee, wie man mit C++ ohne Strings suchen kann (weil das in der Literatur zum üben auch keiner macht).

    Die einfachste Lösung ist alle möglichen Positionen zu prüfen wo das Wort stehen kann.
    D.h. du gehst einfach alle Positionen in der Matrix durch, und prüfst ob das Wort an dieser Position in der gewünschten Richtung geschrieben steht.

    Dazu brauchst du nicht mehr als ein paar Schleifen, Array-Zugriffe und Vergleiche.

    Irgendwo musst du dir dann noch merken ob bzw. wo die Wörter gefunden wurden, damit du die Ausgabe wie gefordert zum Schluss machen kannst. Das kannst du aber erstmal vertagen und die Ausgabe direkt dort machen wo du den Treffer feststellst. Wenn das mal funktioniert, kannst du dich dann um diesen Teil kümmern.



  • @hustbaer sagte in C++ Wortsuche:

    Dazu brauchst du nicht mehr als ein paar Schleifen, Array-Zugriffe und Vergleiche.

    Für einen Anfänger kann die Aufgabe schon erschlagend wirken!?

    #include <limits>     // std::numeric_limits<>
    #include <cstdlib>    // EXIT_FAILURE
    #include <memory>     // std::make_unique<>()
    #include <fstream>    // std::ifstream
    #include <iostream>   // std::cin, std::cout, std::cerr
    
    enum direction_t { none, right, left, down, up, dir_max };
    char const *direction_names[] = { "none", "right", "left", "down", "up" };
    
    struct find_result_t
    {
        direction_t direction = direction_t::none;
        std::size_t row = 0;
        std::size_t col = 0;
    
        operator bool() const { return direction != direction_t::none; }
    };
    
    auto strlen(char const *str) -> std::size_t
    {
        auto ori{ str };
        while (*str++);
        return str - ori - 1;
    }
    
    void rewind(std::istream &is)
    {
        is.clear();
        is.seekg(0);
    }
    
    bool validate_input(std::istream &is, std::size_t &rows, std::size_t &cols)
    {
        rewind(is);
        rows = 1;
        cols = 0;
        std::size_t cur_cols = 0;
        for (char ch; is.get(ch);) {
            if (ch == '\n') {
                if (rows > 1 && cur_cols != cols) {
                    std::cerr << "Row " << rows << " contains " << cur_cols << " columns. Expected " << cols << " columns :(\n\n";
                    return false;
                }
                cur_cols = 0;
                ++rows;
            }
            else if (ch != ' ') {
                if (rows == 1)
                    ++cols;
                else
                    ++cur_cols;
            }
        }
        return true;
    }
    
    void read_input(std::istream &is, char *matrix)
    {
        rewind(is);
        std::size_t i = 0;
        for (char ch; is.get(ch);)
            if (ch != '\n' && ch != ' ')
                matrix[i++] = ch;
    }
    
    void print_matrix(char *matrix, std::size_t rows, std::size_t cols)
    {
        for (std::size_t i = 0; i < rows * cols; ++i) {
            std::cout << matrix[i] << ' ';
            if ((i + 1) % cols == 0)
                std::cout.put('\n');
        }
    }
    
    bool strcmp(char *str, char const *word, long long delta = 1)
    {
        while (*word) {
            if (*word != *str)
                return false;
            ++word;
            str += delta;
        }
        return true;
    }
    
    auto find_word(char *matrix, std::size_t rows, std::size_t cols, char const *word, find_result_t last_result = find_result_t{}) -> find_result_t
    {
        find_result_t result;
    
        auto length{ strlen(word) };
        if (!length)
            return result;
    
        if (last_result.direction != direction_t::none) {
            if (last_result.direction == direction_t::up) {
                last_result.direction = direction_t::right;
                if (last_result.col == cols) {
                    last_result.col = 1;
                    last_result.row++;
                }
                else ++last_result.col;
            }
            else last_result.direction = static_cast<direction_t>(static_cast<int>(last_result.direction) + 1);
        }
    
        for (std::size_t row = last_result.row ? last_result.row - 1 : 0; row < rows; ++row) {
            for (std::size_t col = row == last_result.row - 1 && last_result.col ? last_result.col - 1 : 0; col < cols; ++col) {
                if (matrix[row * cols + col] == word[0]) {
                    result.col = col + 1;
                    result.row = row + 1;
    
                    if (last_result.direction <= direction_t::right && cols - col >= length && strcmp(&matrix[row * cols + col], word, 1)) {
                        result.direction = direction_t::right;
                        return result;
                    }
    
                    if (last_result.direction <= direction_t::left && col + 1 >= length && strcmp(&matrix[row * cols + col], word, -1)) {
                        result.direction = direction_t::left;
                        return result;
                    }
    
                    if (last_result.direction <= direction_t::down && rows - row >= length && strcmp(&matrix[row * cols + col], word, cols)) {
                        result.direction = direction_t::down;
                        return result;
                    }
    
                    if (last_result.direction <= direction_t::up && row + 1 >= length && strcmp(&matrix[row * cols + col], word, -static_cast<long long>(cols))) {
                        result.direction = direction_t::up;
                        return result;
                    }
    
                    last_result.direction = direction_t::none;
                }
            }
        }
    
        return result;
    }
    
    auto main() -> int
    {
        auto const filename = "input.txt";
        std::ifstream is{ filename };
        if (!is.is_open()) {
            std::cerr << "Couldn't open \"" << filename << "\" for reading :(\n\n";
            return EXIT_FAILURE;
        }
    
        std::size_t rows, cols;
        if (!validate_input(is, rows, cols))
            return EXIT_FAILURE;
    
        std::cout << "Rows: " << rows << ", Cols: " << cols << '\n';
        
        auto matrix = std::make_unique<char[]>(rows * cols);
        read_input(is, matrix.get());
        print_matrix(matrix.get(), rows, cols);
    
        auto const max_word_length = rows > cols ? rows : cols;
        auto word = std::make_unique<char[]>(max_word_length + 1);
    
        for (std::size_t i = 0; i < 3; ++i) {
            std::cout << "Word to search for: ";
            std::cin.getline(word.get(), max_word_length + 1);
    
            for (find_result_t result; result = find_word(matrix.get(), rows, cols, word.get(), result);) {
                std::cout << "Found \"" << word << "\" at (" << result.row << ", " << result.col << "), direction: " << direction_names[result.direction] << '\n';
            }
        }
    }
    


  • @Swordfish Man kann das auch einfacher halten.
    So wie ich die Aufgabe verstehe ist nicht gefragt dass man variable Matrix-Grössen unterstützt.
    Und davon abgesehen machst du das auch viel komplizierter als nötig.

    ps: Und davon abgesehen erfüllt dein Code nicht die Vorgaben. Wenn ich das richtig verstanden habe sollen erst die drei Wörter eingelesen werden und danach erst die Ausgabe erfolgen.



  • Im Prinzip kann man einfach machen:

    for each X
        for each Y
            for each word
                for each direction
                    if word starts here
                        print out word, pos, direction
    

    Und "if word starts here" kann man implementieren als

    does word start here(word, pos, direction):
        for each char in word
            if pos out of bounds
                return false
            if char at pos != char in word
                return false
            pos += direction
        return true
    


  • @hustbaer sagte in C++ Wortsuche:

    Und davon abgesehen machst du das auch viel komplizierter als nötig.

    Etwas konkreter wäre schon hilfreich.

    Und davon abgesehen erfüllt dein Code nicht die Vorgaben. Wenn ich das richtig verstanden habe sollen erst die drei Wörter eingelesen werden und danach erst die Ausgabe erfolgen.

    Kosmetik.

    @hustbaer sagte in C++ Wortsuche:

    does word start here(word, pos, direction):
        for each char in word
            if pos out of bounds
                return false
            if char at pos != char in word
                return false
            pos += direction
        return true
    

    mein strcmp() macht im prinzip das selbe.



  • @hustbaer

    Ich würde noch eine Abfrage einbauen, ob sich die Suche überhaupt lohnt. Jetzt nicht um das zu optimieren, sondern weil ich das auch so "in echt" machen würde:

    "Gucke an jeder Position, ob das Zeichen an der Position gleich dem Anfangsbuchstaben ist. Falls ja, test alle Richtungen".
    Also bei dir:

    for each X
        for each Y
            for each word
                if char at pos = first char in word
                    for each direction
                        if word starts here
                            print out word, pos, direction
    
    


  • @Jockelx sagte in C++ Wortsuche:

    Ich würde noch eine Abfrage einbauen, ob sich die Suche überhaupt lohnt. Jetzt nicht um das zu optimieren, sondern weil ich das auch so "in echt" machen würde:

    Ja, und mein Code guckt auch nur weiter wenn überhaupt in der jeweiligen Richtung Platz für word ist.



  • @Jockelx sagte in C++ Wortsuche:

    Jetzt nicht um das zu optimieren, sondern weil ich das auch so "in echt" machen würde:

    Das ist aber eine Optimierung. Zu behaupten du würdest das nicht einbauen um es zu optimieren sondern weil du das auch "in echt" so machen würdest (um es zu optimieren!), macht irgendwie keinen Sinn.



  • @Swordfish sagte in C++ Wortsuche:

    @Jockelx sagte in C++ Wortsuche:

    Ich würde noch eine Abfrage einbauen, ob sich die Suche überhaupt lohnt. Jetzt nicht um das zu optimieren, sondern weil ich das auch so "in echt" machen würde:

    Ja, und mein Code guckt auch nur weiter wenn überhaupt in der jeweiligen Richtung Platz für word ist.

    Ja. Was eine nicht geforderte Optimierung ist, die den Code unnötig kompliziert macht. Genau so wie die "restartable" Suchfunktion nicht gefordert wurde und den Code unnötig kompliziert macht.



  • @hustbaer sagte in C++ Wortsuche:

    Das ist aber eine Optimierung

    Ja und? Darf ja auch eine sein. Die Optimierung ist aber nicht der Grund für die Änderung, sondern weil ich das anschaulicher finde. Ist das so schwer zu verstehen?



  • ps: Und die Optimierung ist nichtmal sinnvoll implementiert. Sinnvoller wäre es gleich die Start- und Endwerte der Schleifen anzupassen.


Log in to reply