C++ Wortsuche



  • 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.



  • @hustbaer sagte in C++ Wortsuche:

    Genau so wie die "restartable" Suchfunktion nicht gefordert wurde und den Code unnötig kompliziert macht.

    Wie vermeidest Du doppelt und dreifach dasselbe zu finden?



  • @hustbaer sagte in C++ Wortsuche:

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

    ???



  • @Jockelx sagte in C++ Wortsuche:

    @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?

    Ja 🙂
    Also auf die Idee dass man das anschaulicher finden könnte wäre ich nicht gekommen. Und es sollte mMn. kein Grund sein es einzubauen. Wenn man es als Optimierung haben möchte, OK. Aber wenn einem die Optimierung egal ist, dann ist es ein Stück Code das genau keinen Sinn macht. Und Code der Teile enthält die keinen Sinn machen, finde ich persönlich nicht anschaulicher.



  • @Swordfish sagte in C++ Wortsuche:

    @hustbaer sagte in C++ Wortsuche:

    Genau so wie die "restartable" Suchfunktion nicht gefordert wurde und den Code unnötig kompliziert macht.

    Wie vermeidest Du doppelt und dreifach dasselbe zu finden?

    So:

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

    Wie soll da was doppelt oder dreifach gefunden werden?



  • @hustbaer Ok. 1:0. Darf mir meine Lösung trotzdem gefallen?


Anmelden zum Antworten