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

std::vector<std::vector<int>> floors;
std::vector<int> sums;

int isPrime(int number) {
    if (number == 0 || number == 1) {
        return 0;
    }
    int x = 2;
    while (x <= number / 2) {
        if (number % x == 0) {
            return 0;
        }
        x++;
    }
    return 1;
}
int input(std::string filename) { // Taking input from a txt file.
    std::vector<std::string> lines;
    try {
        std::fstream file;
        file.open(filename, std::ios::in);
        if (file) {
            std::string templine;
            while (std::getline(file, templine)) {
                lines.push_back(templine);
            }
            file.close();
            // Parsing the lines
            for (int i = 0; i < lines.size(); i++) {
                std::vector<int> tempfloor;
                for (int j = 0; j < lines.at(i).length(); j++) {
                    if (lines.at(i)[j] != ' ') {
                        std::string tempstr;
                        while (lines.at(i).length() > j && lines.at(i)[j] != ' '){
                            tempstr.push_back(lines.at(i)[j++]);
                        }
                        tempfloor.push_back(std::stoi(tempstr));
                    }
                    else {
                        continue;
                    }
                }
                floors.push_back(tempfloor);
            }
            return lines.size();
        }
        else {
            std::cerr << "File input error!" << std::endl;
            return -1;
        }
    }
    catch (std::exception ex) {
        std::cerr << "Error : " << ex.what() << std::endl;
        return -1;
    } 
}
void sumFinder(int floorIndex, int lineIndex, int pathSum) {
    // The most efficient way to solve this problem is to use a recursive call paths on triangle.
    if (isPrime(floors.at(floorIndex).at(lineIndex))) {
        return;
    }
    // Adding value for every recursive call.
    pathSum = pathSum + floors.at(floorIndex).at(lineIndex);
    // If it's the lowest level then we will push the path sum to sums vector and return.
    if (floorIndex == floors.size() - 1) {
        sums.push_back(pathSum);
        return;
    }
    // According to this rule : "You are only allowed to walk downwards and diagonally." We can only walk to lineIndex and lineIndex + 1.
    sumFinder(floorIndex + 1, lineIndex, pathSum);
    sumFinder(floorIndex + 1, lineIndex + 1, pathSum);
}
int main(){
    int numberofFloors = input("input2.txt");
    std::cout << "Given floor input : " << std::endl;
    for (int i = 0; i < floors.size(); i++) {
        for (int j = 0; j < floors.at(i).size(); j++) {
            std::cout << floors.at(i).at(j) << " ";
        }
        std::cout << std::endl;
    }
    // Start of recursive call
    sumFinder(0, 0, 0);
    // After getting all the possible path sums, I just pick the biggest sum.
    int max = 0;
    for (int i = 0; i < sums.size(); i++) {
        if (max < sums.at(i)) {
            max = sums.at(i);
        }
    }
    std::cout << "The maximum possible sum is " << max << std::endl;
    return 0;
}