Besten Weg durch Pyramide finden



  • 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



  • So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung:

    /*
    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.
    */
    
    /*
    This code was created together with some friendly people of the German C++ forum (particularly a user called wob):
    https://www.c-plusplus.net/forum/345800-full
    */
    
    #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
    	{
    		os << value << ": ";
    
    		for (int i = data.size() - 1; i > 0; ++i)
    			os << pyramid[i][data[i]] << " -> ";
    
    		os << pyramid[0][data[0]] << endl;
    		/*
    		os << value << ": ";
    
    		const auto last_elem_idx = data.size() - 1;
    
    		for (int i = 0; i < last_elem_idx; ++i)
    			os << pyramid[i][data[i]] << " -> ";
    
    		os << pyramid[last_elem_idx][data[last_elem_idx]] << endl;
    		*/
    	}
    };
    
    vector< vector<int> > read_pyramid(istream &is)
    {
    	vector< vector<int> > result;
    	while (true)
    	{
    		vector<int> line;
    		for (int i = 0; i <= result.size(); ++i)
    		{
    			int n;
    			if (!(is >> n))
    			{
    				if (!line.empty())
    					cout << "The last line is not complete and therefore ignored." << endl;
    				return result;
    			}
    			line.push_back(n);
    		}
    		result.push_back(move(line));
    	}
    }
    
    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)
    		best_paths.push_back(p);
    
    	else if (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;
    }
    
    path best_path(const vector< vector<int> > &pyramid)
    {
    	vector<path> good;
    
    	for (int i = 0; i != pyramid.back().size(); ++i)
    		good.push_back(path{ pyramid.back()[i],{ i } });
    
    	for (int line = pyramid.size() - 2; line >= 0; --line)
    	{
    		vector<path> newgood;
    
    		for (int col = 0; col != pyramid[line].size(); ++col)
    		{
    			auto right_path = (good[col].value > good[col + 1].value) ? good[col] : good[col + 1];
    
    			right_path.value += pyramid[line][col];
    			right_path.data.push_back(col);
    
    			newgood.push_back(right_path);
    		}
    
    		good = newgood;
    	}
    
    	return good[0];
    }
    
    int max_path_value(vector< vector<int> > pyramid)
    { // call by value to modify pyramid
    
    	for (int line = pyramid.size() - 2; line >= 0; --line)
    		for (int col = 0; col != pyramid[line].size(); ++col)
    			pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]);
    
    	return pyramid[0][0];
    }
    
    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);
    	// change to "read_pyramid(cin)" for custom input
    
    	cout << "max_path_value = " << max_path_value(pyramid) << '\n';
    
    	auto best = best_path(pyramid);
    	best.print(cout, pyramid);
    
    	/*auto best_paths = dfs(pyramid);
    	for (const auto &path : best_paths)
    		path.print(cout, pyramid);*/
    }
    


  • Stimmt, von unten nach oben ist es deutlich kürzer, aber praktisch nicht schneller.

    Um schneller zu werden, muss man die Kopie vermeiden. Zum Beispiel so:

    int max_path_value_no_copy(const vector<vector<int>> &pyramid) {
        vector<int> workline(pyramid.back());
        for (size_t line = pyramid.size() - 2; line != (size_t) -1; --line)
            for (size_t col = 0; col != pyramid[line].size(); ++col)
                workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]);
    
        return workline[0];
    }
    

    Ich habe es mal gebenchmarkt:

    -----------------------------------------------------------
    Benchmark                    Time           CPU Iterations
    -----------------------------------------------------------
    BM_MPV/8                   581 ns        581 ns    1223745
    BM_MPV/64                 5938 ns       5937 ns     117898
    BM_MPV/512              221748 ns     221722 ns       3200
    BM_MPV/1024            1135833 ns    1135691 ns        617
    BM_MPV2/8                  552 ns        552 ns    1273185
    BM_MPV2/64                5911 ns       5910 ns     119182
    BM_MPV2/512             220894 ns     220866 ns       3180
    BM_MPV2/1024           1201114 ns    1200935 ns        582
    BM_MPV_NO_COPY/8            90 ns         90 ns    7887087
    BM_MPV_NO_COPY/64         1224 ns       1224 ns     582609
    BM_MPV_NO_COPY/512       54624 ns      54618 ns      12835
    BM_MPV_NO_COPY/1024     264116 ns     264087 ns       2591
    

    MPV ist mein Original, MPV2 deine Modifizierung von unten nach oben und NO_COPY spricht für sich 🙂



  • Timon Paßlick schrieb:

    So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung

    Vielleicht solltest du mal einen Debugger nutzen?

    Deine Loop im Print sieht falsch aus:

    for (int i = data.size() - 1; i > 0; ++i)
    

    Im 2. Durchlauf ist i gleich der size und dann kracht es.



  • NO_COPY ist ja wirklich extrem kürzer.



  • Habe noch die Pfadsuche mit der workline implementiert, bin mir aber nicht sicher, wie effektiv das ist:

    /*
    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.
    */
    
    /*
    This code was created together with some friendly people of the German C++ forum (particularly a user called wob):
    https://www.c-plusplus.net/forum/345800-full
    */
    
    #include <algorithm>
    #include <iostream>
    #include <sstream>
    #include <vector>
    
    using namespace std;
    
    struct path
    {
    	int value;
    	vector<int> data;
    	void print(ostream &os) const
    	{
    		if (data.empty())
    		{
    			os << "0: empty" << endl;
    			return;
    		}
    
    		os << value << ": ";
    
    		for (size_t i = data.size() - 1; i != 0; --i)
    			os << data[i] << " -> ";
    
    		os << data[0] << endl;
    	}
    };
    
    vector< vector<int> > read_pyramid(istream &is)
    {
    	vector< vector<int> > result;
    	while (true)
    	{
    		vector<int> line;
    		for (int i = 0; i <= result.size(); ++i)
    		{
    			int n;
    			if (!(is >> n))
    			{
    				if (!line.empty())
    					cout << "The last line is not complete and therefore ignored." << endl;
    				return result;
    			}
    			line.push_back(n);
    		}
    		result.push_back(move(line));
    	}
    }
    
    // returns the top most left best path
    path best_path(const vector< vector<int> > &pyramid)
    {
    	if (pyramid.empty())
    		return path{ 0,{} };
    
    	if (pyramid.size() == 1)
    		return path{ pyramid[0][0],{ pyramid[0][0] } };
    
    	vector<path> workline(pyramid.back().size());
    
    	for (int i = 0; i != workline.size(); ++i)
    		workline[i] = path{ pyramid.back()[i],{} };
    
    	for (size_t line = pyramid.size() - 2; line != size_t(-1); --line)
    		for (int col = 0; col != line + 1; ++col)
    		{
    			auto right_col = (workline[col].value >= workline[col + 1].value) ? col : col + 1;
    
    			workline[col].value = pyramid[line][col] + workline[right_col].value;
    
    			workline[col].data = workline[right_col].data;
    			workline[col].data.push_back(pyramid[line + 1][right_col]);
    		}
    
    	workline[0].data.push_back(pyramid[0][0]);
    	return workline[0];
    }
    
    int max_path_value(const vector< vector<int> > &pyramid)
    {
    	if (pyramid.empty())
    		return 0;
    
    	if (pyramid.size() == 1)
    		return pyramid[0][0];
    
    	vector<int> workline(pyramid.back());
    	for (size_t line = pyramid.size() - 2; line != size_t(-1); --line)
    		for (size_t col = 0; col != pyramid[line].size(); ++col)
    			workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]);
    
    	return workline[0];
    }
    
    int main()
    {
    	stringstream testinput1(
    		"    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(testinput1);
    	// change to "read_pyramid(cin)" for custom input
    
    	cout << "max_path_value = " << max_path_value(pyramid) << '\n';
    
    	auto best = best_path(pyramid);
    	best.print(cout);
    }
    

Anmelden zum Antworten