From project euler :

``````By starting at the top of the triangle below and moving to adjacent numbers
on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.``````

Find the maximum total from top to bottom in triangle.txt, a 15K text file containing a triangle with one-hundred rows

Are we supposed to post the answer we get to double check? I got 6580.

Sorry thats not the correct answer.

7273?

Yes the answer is 7273, and posting solutions are welcome.

Here's mine. Haven't tested it with anything but the posted file, but got the right answer.

``````#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct Triangle {
int peakVal, triangleVal;
};

void usage() {
cout << "Usage : ./Triangles filename";
}

int max(int num1, int num2) {
if (num1 > num2)
return num1;
return num2;
}

int main(int argc, char** argv) {
if (argc != 2) {
usage();
return EXIT_FAILURE;
}

ifstream inputFile;
inputFile.open(argv);

if (!inputFile) {
cout << "Could not open file " << argv << endl;
return EXIT_FAILURE;
}

vector <Triangle*> rows;
Triangle* row;
int numRows = 0;
int value;

// assumes well-formed file.  No error checking done.  Not the best memory management efficiency,
// but what the hell, small file and memory's cheap. :)
inputFile >> value;
while (inputFile) {
numRows++;
row = new Triangle[numRows];
row.peakVal = value;
for (int i = 1; i < numRows; i++) {
inputFile >> row[i].peakVal;
}

rows.push_back(row);
inputFile >> value;
}

inputFile.close();

if (numRows == 0) {
// trivial.
cout << "There are no triangles.  Best path = 0.\n";
return EXIT_SUCCESS;
}

if (numRows == 1) {
// trivial.
cout << "There is 1 entry.  Best path = " << rows.peakVal << ".\n";
delete rows;
return EXIT_SUCCESS;
}

// bottom row are triangles of 1.  Triangle value = cell value.
for (int i = 0; i < numRows; i++) {
rows[numRows - 1][i].triangleVal = rows[numRows - 1][i].peakVal;
}

// now do bottom to top.  Pick the larger of lower triangles and add yourself
for (int i = numRows - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
rows[i][j].triangleVal = rows[i][j].peakVal
+ max(rows[i + 1][j].triangleVal, rows[i + 1][j + 1].triangleVal);
}
}

cout << "Best path is " << rows.triangleVal << endl;

for (int i = 0; i < numRows; i++) {
delete rows[i];
}
return EXIT_SUCCESS;
}``````

Lol, I was wondering where you went Vernon, was starting to miss your post lol.

Here is a small hint, start from bottom-up, instead of top-down.

A top-down solution, although not much different:

``````#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int clamp(int val,int max)
{
if (val<0)return 0;
if (val>max)return max;
return val;
}

int main()
{
ifstream file("triangle.txt");
vector<vector<int> > triangle;
while (file.good())
{
triangle.push_back(vector<int>(triangle.size()+1));
for (int i=0;i<triangle.back().size();i++)file >> triangle.back()[i];
}

for (int r=1;r<triangle.size();r++)
{
vector<int>& row=triangle[r],&prevRow=triangle[r-1];
for (int x=0;x<row.size();x++)row[x]+=max(prevRow[clamp(x-1,row.size()-2)],prevRow[clamp(x,row.size()-2)]);
}
int maxPathTotal=triangle.back();
for (int i=1;i<triangle.back().size();i++)maxPathTotal=max(maxPathTotal,triangle.back()[i]);
cout << "Best path sums up to " << maxPathTotal << '.' << endl;
}``````

I made my program to do top-down and got 7048, at least i tried :)

Ok, since its been a couple of days since this thread started, i'll post my solution.
Its not very strict but gets the job done enough.

``````#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

typedef std::vector<int> IntVector;
typedef std::vector<IntVector> TriangleType;

long bottomUpSumTriangle(const TriangleType& tri){
TriangleType triangle(tri);
for(int row = triangle.size() - 2; row >= 0 ; --row){
for(int col = 0; col < triangle[row].size(); ++col){
int leftChild =  triangle[row+1][col];
int rightChild = triangle[row+1][col+1];
triangle[row][col] += std::max(leftChild,rightChild);
}
}
return triangle;
}
IntVector toIntVec(const std::string& str){
stringstream ss(str);
IntVector column;
int val = 0;
while(ss >> val){
column.push_back( val );
}
return column;
}
int main(){
ifstream fileIn = ifstream("triangle.txt");
if(!fileIn){ return -1; }
TriangleType triangle;
string str;
while(getline(fileIn,str)){
triangle.push_back( toIntVec(str) );
}

unsigned long ans = 0;

if(triangle.empty())
ans = 0;
else if(triangle.size() == 1)
ans =  triangle;

ans = bottomUpSumTriangle(triangle);

cout << "Max sum = " << ans << endl;

}``````

I was wondering. Is this problem not an NP-hard problem?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.