/**
 * @author Mehmet Yasin Şeremet
 *
 * Problem: You will have an orthogonal triangle input from a file and you need to find the maximum sum of the numbers according to given rules below;

1. You will start from the top and move downwards to an adjacent number as in below.
2. You are only allowed to walk downwards and diagonally.
3. You can only walk over NON PRIME NUMBERS.
4. You have to reach at the end of the pyramid as much as possible.
5. You have to treat your input as pyramid.
 */

/**
 * I take the input from a txt file in such a style:
 *
 * Ex: input.txt
 * 1
 * 2 3
 * 4 5 6
 * ...
 *
 * In my solution, I represent the triangle of numbers in a 2d vector.
 * My algorithm works from bottom to top of the triangle. Initially, all prime numbers are marked
 * and changed as -1. Then, the greatest bottom adjacent non-prime number is added to the upper number.
 * If the adjacent number is prime, since it is changed as -1, it is not added to the upper number.
 * So, no change happens. In this way, while going from bottom to the top of the pyramid, always the
 * greatest available number is added to the sum. And priority is always going to the deepest point.
 *
 * There is some edge cases this algorithm cannot solve in this form of implementation since I cannot
 * implement a priority hierarchy between going to the deepest point and getting the maximum sum just with
 * vector class. If this algorithm is implemented by using the concept of binary trees and nodes, this
 * problem could be solved, I believe. Even though to try to all possible cases and to find the result is a
 * definite solution by using brute force, it does not take reasonable time in large inputs because it is
 * a exponential time complexity algorithm in worst case. But with my type of algorithm, this problem
 * could be solved in polynomial time complexity. (Except the prime number detection part)
 *
 * I have not so much time in this period because I'm moving into a new house.
 * Therefore, after I realize that edge cases, I cannot convert my algorithm to the other version.
 * Sorry for that. :(
 *
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

vector <vector <int>> numbersTriangle(500,vector<int> (500,-1)); //2d vector to represent the given triangle of numbers
int lineNumb=0; //count of the total lines - size of the triangle
/**
 * Optimized 6k+-1 method to check whether the number is prime or not
 * Resource: https://en.wikipedia.org/wiki/Primality_test
 * @param n an integer to check primality
 * @return true if it is prime
 */
bool primeCheck(int n){
    if (n <= 3) {
        return n>1;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

/**
 * Reading input file and creating a 2d integer vector of the orthogonal triangle of the numbers to ease the operations on them
 */
void numberTriangleCreator(){
    fstream inputFile("/Users/mehme1/CLionProjects/untitled/input.txt");
    string line;

    int wordNumb=0;
    while(getline(inputFile,line)){
        string words;
        stringstream ss(line.c_str());
        while(getline(ss,words,' ')) {
            if(!primeCheck(stoi(words))) {
                numbersTriangle.at(lineNumb).at(wordNumb) = stoi(words);
            }
            else{
                numbersTriangle.at(lineNumb).at(wordNumb) = -1;
            }
            wordNumb++;
        }
        wordNumb=0;
        lineNumb++;
    }
}

/**
 * Applying the algorithm described above
 * @return -
 */
int main() {

    numberTriangleCreator();

    bool fullPrimeLine=true; //the condition that the line is full of prime numbers

    for(int i=lineNumb-2;i>=0;i--) {
        for(int j=0;j<lineNumb;j++) {

            int* root = &numbersTriangle.at(i).at(j);
            int* leftChild = &numbersTriangle.at(i+1).at(j);
            int* rightChild = &numbersTriangle.at(i+1).at(j+1);

            if(*root != -1){

                if(*leftChild>*rightChild){
                    *root = (*root)+(*leftChild);
                }
                else if (*rightChild>*leftChild){
                    *root = (*root)+(*rightChild);
                }
                else{
                    if(*rightChild != -1){
                        *root = (*root)+(*rightChild);
                    }
                    else{
                        for(int k=0;k<lineNumb; k++){
                            if(numbersTriangle.at(i).at(k)!=-1){
                                fullPrimeLine=false;
                                break;
                            }
                        }

                        if(fullPrimeLine==false) {
                            *root = -1;
                        }
                    }
                }
            }
        }
        fullPrimeLine=true;
    }

    cout<<"Max sum is: "<<numbersTriangle.at(0).at(0)<<endl;


    return 0;
}