Challenge Question : Summing pathways

[mrnutty]

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

[sfuo]

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

[mrnutty]

Sorry thats not the correct answer.

[Anyzen]

7273?

[mrnutty]

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

[Andreas5]

This is driving me mad! Explanation please :P

[VernonDozier]

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[1]);

    if (!inputFile) {
        cout << "Could not open file " << argv[1] << 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[0].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[0][0].peakVal << ".\n";
        delete rows[0];
        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[0][0].triangleVal << endl;

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

[mrnutty]

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

>>This is driving me mad! Explanation please

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

[Aranarth]

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()[0];
  for (int i=1;i<triangle.back().size();i++)maxPathTotal=max(maxPathTotal,triangle.back()[i]);
  cout << "Best path sums up to " << maxPathTotal << '.' << endl;
}

[kerp]

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

[mrnutty]

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[0][0];
}
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[0][0];

	ans = bottomUpSumTriangle(triangle);

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

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

[edit]
Guess not.
http://www.tushar-mehta.com/misc_tutorials/project_euler/euler018.html