Besten Weg durch Pyramide finden



  • edit: sorry, nene. Wieder zu kurz gedacht.



  • Mach mal direct nach

    cout << "Input received.";
    

    ein "return 0;", dann kommt der erwartete Text.
    In dem Teil danach fliegt eine Exception. Meine Vermuting ist dass der Text asynchron ausgegeben wird, und durch die Exception wird das abgebrochen, d.h. nur die eine Zeile ausgegeben.



  • @Schlangenmensch Ich nimm die zweite Option.



  • Der Input ist tatsächlich ein Problem, früher wäre es gegangen, jetzt hat sich die Implementierung von SoloLearn geändert.
    Aber ich habe auch gesehen, dass nach erfolgreichem Input in Visual C++ in Zeile 855 von der Datei xmemory() eine Ausnahme ausgelöst wird (Schreibzugriffsverletzung).
    Ich fix jetzt erstmal den Input und guck mir dann das mit dem Schreibzugriff an. Falls jemand vor mir eine Lösung hat, gerne rein schreiben.
    Ich geh jetzt erstmal pennen.



  • Habe doch nochmal kurz geguckt, es liegt wohl an

    if (!(it->used))
        good.erase(it);
    

    Also zeigt it wahrscheinlich auf ein ungültiges Element.
    Bin zu müde, erkenne nicht, wieso.
    Ich geh jetzt wohl mal wirklich ins Bett.



  • @Darkshadow44 Habe deinen Post erst jetzt gesehen, aber du hattest wohl recht. Ich hätte es schneller gemerkt, wenn ich mir angewöhnt hätte, mit endl den Buffer zu leeren.



  • Neben dem goto stören in dem Programm noch die vielen "-1" und "++" bzw. "--"-Operatoren.

    Bei sowas hier:

    const auto last = pyramid.size() - 1;
    

    schrillen schon die Alarmglocken. Ist sichergestellt, dass pyramid.size > 0 ist?

    Die folgende for-Loop beginnt dann noch bei last - 1 . Bei solchem Code muss man viel zu genau aufpassen, dass man kein off-by-one-Bug hat oder Cornercases nicht korrekt berücksichtigt.

    Dann kommen wir zu den Zeilen 82-84:

    for (auto it = good.begin(); it != --good.end(); ++it) 
            { 
                auto right_it = (it->value > ((++it)--)->value) ? it : (++it)--;
    

    Warum "--good.end()"? Mit dem -- löst du bei mir aus, dass ich denke, dass irgendwo etwas dauerhaft verändert werden soll. Hier ist das aber nur der Iterator. Ich würde hier end() - 1 nutzen bzw. warum muss man überhaupt ein Feld zu kurz iterieren? (und ist wieder sichergestellt, dass good.size() > 0 ist?

    Und die Zuweisung an right_it ist unlesbar. Was soll den ((++it)--)->value tun? Dasselbe wie (it + 1)->value ?

    Also: überprüfe die Schleifen und Grenzen und vereinfache den Code und mach das ganze mit kleineren Funktionen.



  • Der Kurs muss ja richtig gut sein, wenn man da goto lernt ...



  • Ich habe mal gelesen, dass goto nicht so schlimm ist, wie alle sagen, wenn man damit aus einer verschachtelten Schleife herausgeht. War nicht bei SoloLearn, aber der Kurs dort ist wirklich nicht gut, ich mach ihn gar nicht. Ich lese Bücher und die Referenz und manchmal Web-Einträge von schlauen Menschen.
    (it - 1) hat bei mir einen Kompilierfehler ausgelöst von wegen bidirektionale Iteratoren unterstützen kein Minus. Minus ist hier auch nicht aufgeführt:
    http://www.cplusplus.com/reference/iterator/BidirectionalIterator/
    Wenn Herr Stroustrup meint, Minus wäre grundsätzlich zu teuer, um implementiert zu werden, kann ich da nichts für. 🙂
    Bei Random-Access ist die big O-Notation fürs Löschen viel höher.
    Also, wie sollte ich irgendeine Zeile anders schreiben? Ich ärger mich da ja selber drüber. Eine Klasse, die von list erbt mit einer Klasse, die von list::iterator erbt mit Minus-Operation würde es ja auch komplizierter machen.



  • Hab ne Idee:

    template <typename Bi_It>
    Bi_It mns1(Bi_It it)
    { // returns it - 1
        Bi_It returnme = ++it;
        --it;
        return returnme;
    }
    


  • Ich habe mal gelesen,

    Man kann auch lesen, dass die Erde flach ist.

    dass goto nicht so schlimm ist, wie alle sagen, wenn man damit aus einer verschachtelten Schleife herausgeht

    Das heißt aber nicht, dass Anfänger damit rumspielen sollten.



  • Irgendeiner Lektüre muss man ja vertrauen, wenn man sich selber noch kein genaues Bild machen kann. Das goto-Statement war ja auch gar nicht der Fehler, auch, wenn es unnötig war und ich es tatsächlich nicht hätte machen sollen.



  • Stimmt, -1 und +1 gehen nicht bei Bidi-Iteratoren. Aber std::next und std::prev funktionieren. Ich nutze nur praktisch nie std::list .

    Hier mal eine schnelle Lösung basierend auf deinem Code. Ich habe 2 Varianten gebaut. Die eine ermittelt wirklich nur das Maximum, aber nicht den Weg. Die zweite speichert auch alle Wege und macht eine Tiefensuche.

    #include <algorithm>
    #include <iostream> 
    #include <sstream>
    #include <vector> 
    
    using namespace std; 
    
    struct path { 
        int value; 
        vector<int> data; 
        void print(ostream &os, const vector<vector<int>> &pyramid) const;
    };
    
    void path::print(ostream& os, const vector<vector<int> >& pyramid) const {
        os << value << ": ";
        for (size_t idx = 0; idx < data.size(); ++idx) {
            os << pyramid[idx][data[idx]] << " -> ";
        }
        os << "end.";
    }
    
    vector<vector<int>> read_pyramid(istream &is) {
        vector<vector<int>> result;
        while (1) {
            vector<int> line;
            for (size_t i = 0; i <= result.size(); ++i) {
                int n;
                if (is >> n)
                    line.push_back(n);
            }
            if (!is) {
                if (!line.empty()) 
                    cout << "unvollständige letzte Zeile ignoriert\n";
                break;
            }
            result.push_back(move(line));
        }
        cout << "Pyramid contains " << result.size() << " lines.\n";
        return result;
    }
    
    void dfs_internal(const vector<vector<int>> pyramid, path &p, vector<path> &best_paths) {
        if (p.data.size() < pyramid.size()) {
            int left = p.data.empty() ? 0 : p.data.back();
            auto line = p.data.size();
            p.data.push_back(left);
            p.value += pyramid[line][left];
            dfs_internal(pyramid, p, best_paths);
            ++p.data.back();
            p.value += pyramid[line][left + 1] - pyramid[line][left];
            dfs_internal(pyramid, p, best_paths);
            p.value -= pyramid[line][left + 1];
            p.data.pop_back();
        } else if (best_paths.empty() || p.value >= best_paths.front().value) {
            if (!best_paths.empty() && p.value > best_paths.front().value) {
                best_paths.clear();
            }
            best_paths.push_back(p);
        }
    }
    
    vector<path> dfs(const vector<vector<int>> &pyramid) {
        vector<path> best_paths;
        if (!pyramid.empty()) {
            path p = {pyramid[0][0], {0}};
            dfs_internal(pyramid, p, best_paths);
        }
        return best_paths;
    }
    
    int max_path_value(vector<vector<int>> pyramid) {
        // call by value, d.h. wir können pyramid modifizieren.
        if (pyramid.empty()) return 0;
        for (size_t line = 1; line < pyramid.size(); ++line) {
            pyramid[line].front() += pyramid[line - 1].front();
            for (size_t col = 1; col < pyramid[line].size() - 1; ++col) {
                pyramid[line][col] += max(pyramid[line - 1][col - 1], pyramid[line - 1][col]);
            }
            pyramid[line].back() += pyramid[line - 1].back();
        }
        auto &last_line = pyramid.back();
        return *max_element(last_line.begin(), last_line.end());
    }
    
    int main() {
        stringstream testinput(
            "    1    "
            "   1 3   "
            "  3 9 2  "
            " 9 1 1 1 "
            );
        stringstream testinput2(
            "     7     "
            "    3 8    "
            "   8 1 0   "
            "  2 7 4 4  "
            " 4 5 2 6 5 "
            );
        auto pyramid = read_pyramid(testinput);
        // alternativ einfach read_pyramid(cin); machen, um Eingabe von stdin zu lesen
    
        cout << "max_path_value = " << max_path_value(pyramid) << '\n';
    
        auto best_paths = dfs(pyramid);
        for (const auto &path : best_paths) { 
            path.print(cout, pyramid);
            cout << '\n'; 
        }   
    }
    

    Beide Lösungen können noch optimiert werden.

    Bei max_path_value braucht man eigentlich nicht alles zu kopieren, bei der Tiefensuche kann man z.B. die hohen Zahlen zuerst nehmen, um dann schlechtere Äste früher abzuschneiden. Wie auch immer, so funktioniert es jedenfalls 🙂



  • Erstmal vielen Dank, dass du dir die Zeit genommen hast, den Code vollständig zu überarbeiten.
    Ich hab ne Frage: In Zeile 37 geht line ja eigentlich out of scope. Verlängert move() die Lebenszeit oder müsste line static sein?
    Und bei vector<vector<int>> wird >> ohne Leerzeichen glaube ich als Operator gelesen, kann mich aber auch täuschen.
    Zumindest wird in "Accelerated C++" gesagt, man soll vector< vector<int> > schreiben, das Buch ist aber von 2000.



  • Timon Paßlick schrieb:

    Ich hab ne Frage: In Zeile 37 geht line ja eigentlich out of scope. Verlängert move() die Lebenszeit oder müsste line static sein?

    line geht in Zeile 38 (eine nach 37) out of scope, nämlich mit der } . Move verlängert keine Lebenszeit und da muss auch nichts static sein.

    Ich möchte mit dem move nur eine Kopie des Line-Vectors sparen. Nach dem move(line) darf ich mit dem line-Objekt praktisch außer löschen (und neu zuweisen) nichts mehr machen. Und in Zeile 38 wird gelöscht. Also alles gut.



  • Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?



  • Timon Paßlick schrieb:

    Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?

    Hä? Verstehe die Frage nicht.



  • Hat sich erledigt, habe die Referenz zu move() durchgelesen.
    War tatsächlich alles in Ordnung.



  • Habe max_path_value() ein wenig optimiert:

    int max_path_value(vector< vector<int> > pyramid)
    { // call by value to modify pyramid
    
    	for (size_t line = pyramid.size() - 2; line <= pyramid.size() - 1; --line)
    		for (size_t col = 0; col != pyramid[line].size(); ++col)
    			pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]);
    
    	return pyramid[0][0];
    }
    

    Ich geh einfach von unten nach oben und spar damit Rechenaufwand. Cool, oder?



  • Habe jetzt den SoloLearn Eintrag geändert und euch Credits gegeben:
    https://code.sololearn.com/cllzC9Lc4Evg/?ref=app#cpp


Anmelden zum Antworten