package Question;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scan = new Scanner(new FileReader("src/pyramid.txt"));
        String whl = "";
        // taking input from txt file
        while (scan.hasNextLine()){
            whl += scan.nextLine() + "\n";
        }
        String []pyramid_row = whl.split("\n");
        int size = pyramid_row.length; // size of pyramid
        int [][]matrix = new int[size][pyramid_row[size-1].length()];
        int k = 0;
        for (int i=0; i<size; i++){
            String []pyramid_column = pyramid_row[i].split(" ");
            for(int j =0; j<pyramid_column.length; j++){
                if(!pyramid_column[j].equals(" ") && !pyramid_column[j].equals("")) // take numbers
                    matrix[i][k++] = Integer.parseInt(String.valueOf(pyramid_column[j]));
            }
            k = 0;
        }
        /* matrix:      exp input:
            1               1
            8 4            8 4
            2 6 9         2 6 9
            8 5 9 3      8 5 9 3
        */
        System.out.println(findMaxSum(matrix, size));

    }
    public static boolean isPrime(int num){
        if(num <= 1)
            return false;
        else if(num <= 3)
            return true;
        else if (num % 2 == 0 || num % 3 == 0)
            return false;
        else {
            for (int i = 5; i * i <= num; i = i + 6)
                if (num % i == 0 || num % (i + 2) == 0)
                    return false;
            return true;
        }

    }

    public static int findMaxSum(int [][]matrix, int size){
        int sum= isPrime(matrix[0][0]) ? 0: matrix[0][0];
        int ind=0;
        for(int i=0; i<size-1; i++){  // don't need to look last row
            if(isPrime(matrix[i][ind])); // if root is prime do nothing
            else{ // root is not prime
                if(isPrime(matrix[i+1][ind])&& isPrime(matrix[i+1][ind+1])); // if both children are prime do nothing
                else if(!isPrime(matrix[i+1][ind])&& isPrime(matrix[i+1][ind+1])) // right child is not prime
                    sum += matrix[i + 1][ind]; // add to sum

                else if(!isPrime(matrix[i+1][ind+1])&& isPrime(matrix[i+1][ind])) // left child is not prime
                    sum += matrix[i + 1][++ind]; // add to sum then increment index

                else{   // both children are not prime, find max
                        // if right child is greater, increment index after assignment
                    int max = matrix[i+1][ind] > matrix[i+1][ind+1] ? matrix[i+1][ind] : matrix[i+1][++ind];
                    sum+=max;
                }
            }
        }
        return sum;
    }
}