Besten Weg durch Pyramide finden



  • Das hier ist mein Code:

    /*
    Challenge: 'The Golden Mountain'
    
    At one international Olympiad in Informatics, the following task was given.
    Let's solve it!
    
        7
       3 8
      8 1 0
     2 7 4 4
    4 5 2 6 5
    
    The figure shows an example of a triangle of numbers. 
    Write a program that calculates the largest sum of numbers through which the path starts,
    starting at the top and ending somewhere on the bottom.
    Each step can go diagonally down to the right or diagonally to the left.
    
    In the example - this is the path 7 -> 3 -> 8 -> 7 -> 5,
    given a max amount of 30.
    */
    
    // Input a pyramid like in the example.
    
    #include <vector>
    #include <list>
    #include <iostream>
    using namespace std;
    
    struct path
    {
    	bool used;
    	int value;
    	vector<int> data;
    };
    
    vector< vector<int> > pyramid;
    list<path> good;
    
    int main() {
    	// handle input
    	for (short line = 1; ; ++line)
    	{
    		vector<int> content; // of line
    		for (short i = 0; i != line; ++i)
    		{
    			int x;
    
    			if (!(cin >> x))
    			{
    			    cout << "Input stopped at line " << line << " number " << i + 1 << '.' << endl;
    				goto input_end;
    			}
    
    			content.push_back(x);
    		}
    		pyramid.push_back(content);
    	}
    input_end:
        cout << "Input received.";
    
    	// prevent undefined behaviour
    	if (pyramid.empty())
    		return 0;
    
    	// fill good path vector with lowest pyramid level
    	const auto last = pyramid.size() - 1;
    	for (short i = 0; i != pyramid.size(); ++i)
    	{
    		good.push_back(
    			path{
    			false,
    			pyramid[last][i],
    			{ pyramid[last][i] }
    		}
    		);
    	}
    
    	// search best path (takes the most left, from bottom to top)
    	for (short line = last - 1; line >= 0; --line)
    	{
    		short i = 0;
    		for (auto it = good.begin(); it != --good.end(); ++it)
    		{
    			auto right_it = (it->value > ((++it)--)->value) ? it : (++it)--;
    
    			right_it->used = true;
    			right_it->value += pyramid[line][i];
    			right_it->data.push_back(pyramid[line][i]);
    
    			if (!(it->used))
    				good.erase(it);
    
    			++i;
    		}
    	}
    
    	// output
    	for (short i = last; i != 0; --i)
    	{
    		cout << good.begin()->data[i] << " -> ";
    	}
    
    	cout << good.begin()->data[0] << endl << good.begin()->value;
    }
    

    Und als Output kommt:

    Input stopped at line 6 number 1.
    

    Der erwartete Output ist aber (wenn ich einfach das Beispiel eingebe):

    Input stopped at line 6 number 1.
    Input received.
    7 -> 3 -> 8 -> 7 -> 5
    30
    

    Jetzt steht "Input received." ja direkt nach der Sprungmarke. Aber bis dahin scheint das Programm gar nicht zu kommen. Obwohl direkt vor dem Jump-Statement "Input stopped at line 6 number 1." ausgegeben wird.

    Der Compiler ist GNU GCC/G++ für C++11.
    Um zu verstehen, wie der Input funktioniert, ist vielleicht noch wichtig, dass dieses Programm auf SoloLearn erstellt wurde: https://code.sololearn.com/cllzC9Lc4Evg/#cpp
    Die Konsole ist dort nicht interaktiv, man muss am Anfang alles eingeben.



  • Ich habe GoTo seit meinen QBasic Anfängen nicht mehr verwendet und möchte dir dringend raten dein Programm ohne goto zu schreiben. Was würde zum Beispiel dagegen sprechen, den Part nach dem goto in eine Funktion zu packen?



  • Werde ich tun und gucken, ob es dann klappt. Interessiert mich trotzdem, wo der Fehler herkommt.



  • Am goto-Statement lags wohl nicht. Kommt immer noch nur die Meldung mit der Zeile und der Nummer.



  • Das Problem scheint die Eingabe Verarbeitung auf der Seite zu sein. Unterschiedliche Zeilen werden als unterschiedliche Eingaben verarbeitet.
    Versuch das mal auf einem lokalen Compiler oder implementiere Testweise deine Eingabe fest im source code.



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


Log in to reply