Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.6 kB
0
Indexable
Never
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <iomanip>
using namespace std;
//C++
//Yigit Karamanli
//Solution to P.I. Works SW Dev. Intern Technical Questionnaire
//Written on VS2012 on a Windows operating system.

/*Algorithm:
- keep the input in a matrix, create a secondary matrix to keep the sums 
- iterate over the rows of the 
- for each element of the row
	- check if it is prime, if it is, place -1 in its place on the secondary matrix
	- check the values in the secondary matrix reaching to the element, choose the max., 
		add the element and place it in its respective place on the secondary matrix.
		if all values reaching to it are -1, that means theres no path to it. place -1 in its place
- After loops end, get the max element of the last row of the secondary matrix.
*/

bool isPrime(const int & x){  //checking if a number is prime 
	bool is_prime = true;
	if (x == 0 || x == 1){
		is_prime = false;
	}

	for( int i = 2; i <= x/2; i++){
		if(x%i == 0){
			is_prime = false;
			break;
		}
	}
	return is_prime;
}

void print(const vector<vector<int>> & mat) //For control purposes
{
	for (int j = 0; j < mat.size(); j++)
	{
		for (int k = 0; k < mat[j].size(); k++)
		{
			cout << setw(6) << mat[j][k];
		}
		cout << endl;
	}
	cout << endl;
}

int findMax( const vector < int > & vec ){
	int max = vec[0];
	for( int i = 0 ; i < vec.size() ; i++){
		if ( vec[i] > max){
			max = vec[i];
		}
	}
	return max;
}

int process( const vector < vector < int > > & mainvec , vector < vector < int > > & processed){
	for(int r = 0 ; r < mainvec.size() ; r++){ //iterate over rows of the matrix
		if (r == 0){               //first row processed differently
			vector < int > line;
			line.push_back(mainvec[0][0]);
			processed.push_back(line);
			continue;
		}
		vector <int> lin;
		for( int i = 0; i < mainvec[r].size() ; i++) //iterate over the columns of the matrix
		{
			if( isPrime(mainvec[r][i])){
				lin.push_back(-1);
				continue;
			}
			if( i == 0){  //first and last element of the row processed differently (might be improved)
				if(processed[r-1][0]== -1){
					lin.push_back(-1);
					continue;
				}
				lin.push_back(processed[r-1][0]+ mainvec[r][i]);
			}
			else if( i == mainvec[r].size()-1){
				if(processed[r-1][i-1]==-1){
					lin.push_back(-1);
					continue;
				}
				lin.push_back(mainvec[r][i] + processed[r-1][i-1]);
			}
			else{
				vector < int > pathsums;
				for( int j = i-1 ; j < mainvec[r-1].size() && j <= i; j++){
					if(processed[r-1][j]==-1){
						continue;
					}
					pathsums.push_back(processed[r-1][j]+ mainvec[r][i]);
				}
				if(pathsums.size() == 0){
					lin.push_back(-1);
					continue;
				}
				lin.push_back(findMax(pathsums));
			}
		}
		processed.push_back(lin);
		//print(processed);
	}
	return findMax(processed[processed.size()-1]);
}

int main(){
	string fileName;
	vector < vector < int > > mainvec;
	vector < vector < int > > sumvec;

	cout << "Enter file name: ";
	cin >> fileName;
	cout << "\n";
	ifstream File;
	File.open(fileName.c_str());

	if( File.fail()){
		cout << "Could not open file.\n";
		exit(1);
	}
	string line;
	int rows = 0, num;
	while (getline(File,line))
	{
		rows++;
		vector < int > linevec;
		istringstream stream(line);
		while(stream >> num){
			linevec.push_back(num);
		}
		mainvec.push_back(linevec);
	}
	//print(mainvec);
	int answer = process(mainvec,sumvec);
	//print(sumvec);

	cout << answer << "\n";
	return 0;
}