main.cpp

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <ctime>
#include <limits.h>

// Enumeration
int algorithm1(std::vector<int>, std::ofstream&, int&, int&);
// Better enumeration
int algorithm2(std::vector<int>, std::ofstream&, int&, int&);
// Divide and Conquer
struct maxSub {
 int sum;
 int start;
 int end;
};
int algorithm3(std::vector<int>, std::ofstream&, int&, int&);
maxSub findMaxSub(std::vector<int>, int, int);
maxSub maxCrossingSub(std::vector<int>, int, int, int);
// Linear Time
int algorithm4(std::vector<int>, std::ofstream&, int&, int&);
void printSubArray(std::vector<int>, std::ofstream&, int, int, int&, int&);
// functions to do the runtime analysis
void runtimeAnalysis(std::ofstream&);

int main() {
 std::ifstream input;
 input.open("MSS_TestProblems-1.txt");
 std::ofstream output;
 output.open("MSS_Results.txt", std::ofstream::out | std::ofstream::trunc);
 
 std::vector<std::vector<int> > numbers;
 std::vector<int> tempNumbers;
 std::vector<std::string> temp;
 std::string line;
 char *token;
 char *duplicate;
 int start = 0,
 end = 0;
 // random seed for later
 srand(unsigned(time(NULL)));
 
 // Check to make sure the input file is there
 if (!input.is_open()) {
 input.close();
 std::cout << "MSS_Problems.txt not found. Please try again" << std::endl;
 return 1;
 }
 
 // read the file and put each line into a string vector
 while (getline(input, line)) {
 temp.push_back(line);
 }
 
 // get rid of the commas [] and spaces
 for (int i = 0; i < temp.size(); i++) {
 // use strdup so that I can convert the string into a usable char array
 // for strtok
 duplicate = strdup(temp[i].c_str());
 token = strtok(duplicate, "[, ]");
 // use atoi to convert each token to an int and push onto first vector
 while (token != NULL) {
 int tempNumber = atoi(token);
 tempNumbers.push_back(tempNumber);
 token = strtok(NULL, "[, ]");
 }
 // random added 0s fix
 if (i != temp.size() - 1) {
 tempNumbers.pop_back();
 }
 // push the array to the number array
 numbers.push_back(tempNumbers);
 // delete stuff
 tempNumbers.clear();
 free(duplicate);
 }
 
 // Pass the vectors for the 1st alogorithm
 output << "-----Results for the 1st algorithm-----" << std::endl;
 for (int i = 0; i < numbers.size(); i++) {
 for (int j = 0; j < numbers[i].size(); j++) {
 tempNumbers.push_back(numbers[i][j]);
 }
 int maxSum = algorithm1(tempNumbers, output, start, end);
 printSubArray(tempNumbers, output, i, maxSum, start, end);
 // delete stuff
 tempNumbers.clear();
 }
 
 // On to the 2nd algorithm
 output << "-----Results for the 2nd algorithm-----" << std::endl;
 for (int i = 0; i < numbers.size(); i++) {
 for (int j = 0; j < numbers[i].size(); j++) {
 tempNumbers.push_back(numbers[i][j]);
 }
 int maxSum = algorithm2(tempNumbers, output, start, end);
 printSubArray(tempNumbers, output, i, maxSum, start, end);
 //delete stuff
 tempNumbers.clear();
 }
 
 // On to the 3rd algorithm
 output << "-----Results for the 3rd algorithm-----" << std::endl;
 for (int i = 0; i < numbers.size(); i++) {
 for (int j = 0; j < numbers[i].size(); j++) {
 tempNumbers.push_back(numbers[i][j]);
 }
 int maxSum = algorithm3(tempNumbers, output, start, end);
 printSubArray(tempNumbers, output, i, maxSum, start, end);
 //delete stuff
 tempNumbers.clear();
 }
 
 // On to the 4th algorithm
 output << "-----Results for the 4th algorithm-----" << std::endl;
 for (int i = 0; i < numbers.size(); i++) {
 for (int j = 0; j < numbers[i].size(); j++) {
 tempNumbers.push_back(numbers[i][j]);
 }
 int maxSum = algorithm4(tempNumbers, output, start, end);
 printSubArray(tempNumbers, output, i, maxSum, start, end);
 //delete stuff
 tempNumbers.clear();
 }
 
 // Runtime Analysis
 int choice;
 std::cout << "Enter 1 for Runtime Analysis (anything else to end): ";
 std::cin >> choice;
 if (choice == 1) {
 output << "-----Runtime Analysis-----" << std::endl;
 runtimeAnalysis(output);
 }
 
 input.close();
 output.close();
 
 return 0;
}

int algorithm1(std::vector<int> vec, std::ofstream &output, int &start, int &end) {
 int max = 0,
 newSum = 0;
 start = 0;
 end = 0;
 
 for (int i = 0; i < vec.size(); i++) {
 for (int j = i; j < vec.size(); j++) {
 newSum = 0;
 for (int k = i; k <= j; k++) {
 newSum += vec[k];
 }
 
 if (newSum > max) {
 max = newSum;
 start = i;
 end = j;
 }
 }
 }
 return max;
}

int algorithm2(std::vector<int> vec, std::ofstream &output, int &start, int &end) {
 int max = 0,
 newSum = 0;
 start = 0;
 end = 0;
 
 for (int i = 0; i < vec.size(); i++) {
 newSum = 0;
 for (int j = i; j < vec.size(); j++) {
 newSum += vec[j];
 if (newSum > max) {
 max = newSum;
 start = i;
 end = j;
 }
 }
 }
 return max;
}

int algorithm3(std::vector<int> vec, std::ofstream &output, int &start, int &end) {
 start = 0;
 end = vec.size() - 1;
 maxSub ms;
 ms = findMaxSub(vec, start, end);
 start = ms.start;
 end = ms.end;
 return ms.sum;
}

maxSub findMaxSub(std::vector<int> vec, int start, int end) {
 maxSub temp;
 
 if (start == end) {
 temp.start = start;
 temp.end = end;
 temp.sum = vec[start];
 return temp;
 }
 
 int mid = (start + end) / 2;
 
 maxSub leftSub;
 leftSub = findMaxSub(vec, start, mid);
 maxSub rightSub;
 rightSub = findMaxSub(vec, mid + 1, end);
 maxSub crossSub;
 crossSub = maxCrossingSub(vec, start, end, mid);
 
 if (leftSub.sum >= rightSub.sum && leftSub.sum >= crossSub.sum) {
 return leftSub;
 }
 else if (rightSub.sum >= leftSub.sum && rightSub.sum >= crossSub.sum) {
 return rightSub;
 }
 else {
 return crossSub;
 }
}

maxSub maxCrossingSub(std::vector<int> vec, int crossStart, int crossEnd, int mid) {
 maxSub temp;
 int leftMax = INT_MIN;
 int leftStart, rightEnd;
 int sum = 0;
 
 for (int i = mid; i >= crossStart; i--) {
 sum += vec[i];
 if (sum > leftMax) {
 leftMax = sum;
 leftStart = i;
 }
 }
 
 int rightMax = INT_MIN;
 sum = 0;
 for (int j = mid + 1; j <= crossEnd; j++) {
 sum += vec[j];
 if (sum > rightMax) {
 rightMax = sum;
 rightEnd = j;
 }
 }
 
 temp.sum = leftMax + rightMax;
 temp.start = leftStart;
 temp.end = rightEnd;
 
 return temp;
}

int algorithm4(std::vector<int> vec, std::ofstream &output, int &start, int &end) {
 int max = 0,
 newSum = 0,
 tempStart = 0,
 tempEnd = 0;
 start = 0;
 end = 0;
 
 for (int i = 0; i < vec.size(); i++) {
 tempEnd = i;
 if (newSum > 0) {
 newSum = newSum + vec[i];
 }
 else {
 tempStart = i;
 newSum = vec[i];
 }
 if (newSum > max) {
 max = newSum;
 start = tempStart;
 end = tempEnd;
 }
 }
 
 return max;
}

void printSubArray(std::vector<int> vec, std::ofstream &output, int count, int max, int &start, int &end) {
 // print out the results to file
 output << "Array #" << count + 1 << std::endl;
 output << "Max Sum: " << max << std::endl;
 output << "Array: [";
 for (int i = start; i < end; i++) {
 output << vec[i] << ", ";
 }
 output << vec[end] << "]\n" << std::endl;
}

void runtimeAnalysis(std::ofstream &output) {
 std::vector<int> testSubject;
 int size;
 int a = 0;
 int b = 0;
 clock_t begin,
 end;
 double elapsed_secs;
 
 // Run the 1st algorithm
 std::cout << "Running enumeration analysis" << std::endl;
 output << "Enumeration Run Times" << std::endl;
 size = 0;
 for (int i = 0; i < 10; i++) {
 size = size + 125;
 std::cout << "Running Group #" << i + 1 << std::endl;
 for (int j = 0; j < 10; j++) {
 // fill up the testSubject
 for (int x = 0; x < size; x++) {
 testSubject.push_back(rand() % 100);
 }
 begin = clock();
 algorithm1(testSubject, output, a, b);
 end = clock();
 elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
 output << "n = " << size << ": " << elapsed_secs << "s" << std::endl;
 testSubject.clear();
 }
 }

 // Run the 2nd algorithm
 std::cout << "Running better enumeration analysis" << std::endl;
 output << "Better Enumeration Run Times" << std::endl;
 size = 50;
 for (int i = 0; i < 10; i++) {
 size = size * 2;
 std::cout << "Running Group #" << i + 1 << std::endl;
 for (int j = 0; j < 10; j++) {
 // fill up the testSubject
 for (int x = 0; x < size; x++) {
 testSubject.push_back(rand() % 100);
 }
 begin = clock();
 algorithm2(testSubject, output, a, b);
 end = clock();
 elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
 output << "n = " << size << ": " << elapsed_secs << "s" << std::endl;
 testSubject.clear();
 }
 }
 
 // Run the 3rd algorithm
 std::cout << "Running Didive and Conquer analysis" << std::endl;
 output << "Divide and Conquer Run Times" << std::endl;
 size = 200;
 for (int i = 0; i < 10; i++) {
 size = size * 2;
 std::cout << "Running Group #" << i + 1 << std::endl;
 for (int j = 0; j < 10; j++) {
 // fill up the testSubject
 for (int x = 0; x < size; x++) {
 testSubject.push_back(rand() % 100);
 }
 begin = clock();
 algorithm3(testSubject, output, a, b);
 end = clock();
 elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
 output << "n = " << size << ": " << elapsed_secs << "s" << std::endl;
 testSubject.clear();
 }
 }
 
 // Run the 4th algorithm
 std::cout << "Running Linear Time analysis" << std::endl;
 output << "Linear Time Run Times" << std::endl;
 size = 100000;
 for (int i = 0; i < 10; i++) {
 size = size * 2;
 std::cout << "Running Group #" << i + 1 << std::endl;
 for (int j = 0; j < 10; j++) {
 // fill up the testSubject
 for (int x = 0; x < size; x++) {
 testSubject.push_back(rand() % 100);
 }
 begin = clock();
 algorithm4(testSubject, output, a, b);
 end = clock();
 elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
 output << "n = " << size << ": " << elapsed_secs << "s" << std::endl;
 testSubject.clear();
 }
 }
}