Skip to content

Instantly share code, notes, and snippets.

@trendsetter37
Created January 2, 2015 19:28
Show Gist options
  • Save trendsetter37/a8a27554fe6740d735a1 to your computer and use it in GitHub Desktop.
Save trendsetter37/a8a27554fe6740d735a1 to your computer and use it in GitHub Desktop.
Pass Triangle on Codeeval
//Help came from Steven A. Dunn's code
#include <fstream>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
void sum_calc(string, vector<long>&);
int main(int argc, char* argv[])
{
ifstream file(argv[1]);
string line;
if (file)
{
stack<string> lineStack;
while (getline(file, line))
{
lineStack.push(line);
}
vector<long> sums; // used by calculate sums function
while (!lineStack.empty())
{
string line = lineStack.top();
sum_calc(line, sums); //line = input string and sums is self-explanatory
lineStack.pop();
}
cout << sums[0] << endl;
file.close();
}
return 0;
}
void sum_calc(string line, vector<long>& runningSums) // reference type vector<long>& should be faster
/* Begins from the base of triangle and works up to apex */
{
vector<long> numbers; // holds the line (string) as integers
istringstream iss(line);
long string; // takes the integer conversion
while (iss >> string) // converting input strings (line) to integers here
numbers.push_back(string);
if (runningSums.size() == 0)
{
/* This is the base of the triangle */
runningSums = numbers; // places numbers into sums vector in main
return; // break out of function for this line
}
vector<long> newSums; // create temp vector to hold progress before transference to runningSums
for (int i = 0; i < runningSums.size() - 1; ++i)
{
long maxNum = 0;
/* runningSums current is greater than the next value in line */
maxNum = (runningSums[i] > runningSums[i+1]) ? runningSums[i] : runningSums[i+1];
//DP adding previous result to new result
newSums.push_back(maxNum + numbers[i]);
}
runningSums = newSums;
return;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment