Technical Questionnaire for P.I. Works

mail@pastecode.io avatar
unknown
plain_text
3 years ago
2.3 kB
4
Indexable
Never
#include <iostream>
#include <fstream> 

using namespace std;

//CHECKS IF GIVEN NUMBER IS PRIME, RETURNS TRUE IF IT IS
bool isPrime(int n) {
   int i, flag = 0;
   if (n == 1 || n==0)
   return false;
   for(i=2; i<=n/2; ++i) {
      if(n%i==0) {
         flag=1;
         break;
      }
   }
   if (flag==0)
   return true;
   else
   return false;
}

//ALGORITHM TO CALCULATE THE MAXIMUM SUM OF THE ROAD WITHOUT PRIMES
//@param row = row index of the pyramid
//@param column = column index of the pyramid
//@param pyramid = pyramid structure as 2 dimensional array
//@param height = height of the pyramid
int algorithm(int row, int column, int** pyramid, int height)
{
    if (row == height) return 0; //if you can not go further, return 0
    if (pyramid[row][column] == -1) return 0; //if prime, return 0 you can't go further 


    int left = algorithm(row+1, column,  pyramid, height); //get the max sum of left road
    int right = algorithm(row+1, column+1, pyramid, height);//get the max sum of right road

    //return the larger one recursively
    if (left > right)
    {
        return left+pyramid[row][column];
    } 
    else return right+pyramid[row][column];
}

int main()
{
    //file read
    ifstream fp("file.txt");
    string line;
    if(!fp.is_open())
    {
        cout << "File could not be opened." << endl;
    }

    //calculate the height of the pyramide
    int height = 0;
    while(fp.good())
    {
        getline(fp, line);
        if (line.length() == 0) break;
        height++;
    }
    
    //go at the beginning of the file
    fp.clear();
    fp.seekg(0);

    //write numbers according to pyramid structure
    int* pyramid[height];
    int temp;
    for (int i = 0; i < height; i++)
    {
        pyramid[i] = new int[i+1];
        for (int j = 0; j < i+1; j++)
        {
            fp >> temp;
            if (isPrime(temp))
            {
                pyramid[i][j] = -1; //write -1 if prime
            }else
            {
                pyramid[i][j] = temp;
            }
        }        
    }
    
    //run the algorithm and print
    int sum = algorithm(0,0,pyramid,height);
    cout << sum << endl;

    //give back dynamically allocated memory
    for (int i = 0; i < height; i++)
    {
        delete pyramid[i];
    }
    
}