Created
January 2, 2015 19:28
-
-
Save trendsetter37/a8a27554fe6740d735a1 to your computer and use it in GitHub Desktop.
Pass Triangle on Codeeval
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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