public class Assignment {

    public static class Path {
        public int length;
        public int sum;
        public Path() {
            length = -1;
            sum = Integer.MIN_VALUE;
        }
        public Path(int sum, int length) {
            this.length = length;
            this.sum = sum;
        }
    }

    public static boolean isPrime(int num){
        if (num == 1) return false;
        if ( num > 2 && num%2 == 0 ) {
            return false;
        }
        int top = (int)Math.sqrt(num) + 1;
        for(int i = 3; i < top; i+=2){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
    public static  Path pyramid(int [][] arr) {
        return pyramidRecursive(arr, 0, 0);
    }

	//Memoization could be used to eliminate calculating the result for same number more than once should the input be larger.
	//In this case with the input I have the algorithm runs efficient enough.

    public static Path pyramidRecursive(int[][] arr, int row, int column) {

        if (row == arr.length)  return new Path(Integer.MIN_VALUE, 0);
        if (isPrime(arr[row][column])) return new Path(Integer.MIN_VALUE, 0);

        Path leftDiagonal = pyramidRecursive(arr, row+1, column);

        Path rightDiagonal = pyramidRecursive(arr, row+1, column+1);

        if (leftDiagonal.length > rightDiagonal.length) {
            return new Path(leftDiagonal.sum + arr[row][column], leftDiagonal.length+1);
        }
        else if (rightDiagonal.length > leftDiagonal.length) {
            return new Path(rightDiagonal.sum + arr[row][column], rightDiagonal.length+1);
        }
        else {
            return new Path(Math.max(0, Math.max(leftDiagonal.sum, rightDiagonal.sum)) + arr[row][column], leftDiagonal.length+1);
        }

    }



    public static void main(String[] args) {

        int[][] input = new int[][]{
                {1},
                {8,4},
                {2, 6, 9},
                {8, 5, 9, 3}
        };

        int[][] largeInput = new int[][] {
                                                     {215},
                                                  {193, 124},
                                               {117, 237, 442},
                                            {218, 935, 347, 235},
                                         {320, 804, 522, 417, 345},
                                      {229, 601, 723, 835, 133, 124},
                                   {248, 202, 277, 433, 207, 263, 257},
                                {359, 464, 504, 528, 516, 716, 871, 182},
                             {461, 441, 426, 656, 863, 560, 380, 171, 923},
                          {381, 348, 573, 533, 447, 632, 387, 176, 975, 449},
                       {223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444},
                    {330, 131, 333, 928, 377, 733, 17,  778, 839, 168, 197, 197},
                  {131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928},
               {223, 626, 34,  683, 839, 53,  627, 310, 713, 999, 629, 817, 410, 121},
            {924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233},
        };



        Path path = pyramid(largeInput);
        System.out.println("Sum: " + path.sum);



    }
}