/* 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 #include #include #include using namespace std; struct path { int value; vector 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 > read_pyramid(istream &is) { vector< vector > result; while (true) { vector 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 > &pyramid) { if (pyramid.empty()) return path{ 0,{} }; if (pyramid.size() == 1) return path{ pyramid[0][0],{ pyramid[0][0] } }; vector 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 > &pyramid) { if (pyramid.empty()) return 0; if (pyramid.size() == 1) return pyramid[0][0]; vector 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); }

pyramid challenge