#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* !!!!!!!!!!!!! THIS PROGRAM ASSUMES THAT YOUR PYRAMID ENDS WITH '\n' (new line character)!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 *  if it ends with EOF it will not read last line */


//Linked list for recursion, pyramid will be fully mapped to linked list there will be 3 ways to proceed from one node to another
struct node {
    int key;
    struct node *leftDiagonal;
    struct node *downward;
    struct node *rightDiagonal;
};
typedef struct node node;

// Globals for max total
int dim1 = 0; // dimensions of the pyramid
int maxMoves = 0;//How far we gone down
int maxTotal = 0;//Total
char *maxWay;//Which way we gone
int *maxIntWay;
node *head;//Head of linked list (tip of the pyramid)


//Function for checking if  the is prime
int isPrime(int n) {
    if (n == 1)
        return 0;
    int i, m = 0, flag = 0;
    m = n / 2;
    for (i = 2; i <= m; i++) {
        if (n % i == 0) {

            flag = 1;
            return 0;
        }
    }
    if (flag == 0) {
        return 1;
    }
}

void arrCpy(int arr1[dim1], const int arr2[dim1]){
    for (int i = 0; i < dim1; ++i) {
        arr1[i] = arr2[i];
    }
}
//Function for finding the height of the pyramid
//Opens the file and counts the lines
int learnArrDim() {
    char in;
    FILE *s;

    int n = 0;
    if ((s = fopen("input2.txt", "r")) == NULL) {
        printf("Error! opening file");
        // Program exits if file pointer returns NULL.
        exit(1);
    }
    char temp;
    while ((in = fgetc(s)) != EOF) {
        printf("%c", in);
        if (in == '\n'){
            temp = in;
            n++;
        }

    }
    fclose(s);

    printf("%d", n);
    dim1 = n;
    return n;
}

//Creating node for linked list
node *createNode(int key) {
    node *newNode = (node *) malloc(sizeof(node));
    newNode->key = key;
    newNode->leftDiagonal = NULL;
    newNode->downward = NULL;
    newNode->rightDiagonal = NULL;
    return newNode;

}

//Creating linked list starting from right side using recursion
void fill(int arr[dim1][dim1], int k, int l, node **node, int dim) {

    *node = createNode(arr[k][l]);

    if (k == dim - 1)
        return;

    if ((*node)->rightDiagonal == NULL) {
        //node->rightDiagonal = createNode(arr[k + 1][l + 1]);
        fill(arr, k + 1, l + 1, &(*node)->rightDiagonal, dim);

    }

    if ((*node)->downward == NULL) {
        fill(arr, k + 1, l, &(*node)->downward, dim);
    }

    if ((*node)->leftDiagonal == NULL) {
        if (l == 0)
            return;
        fill(arr, k + 1, l - 1, &(*node)->leftDiagonal, dim);
    }


}

//Finding the max total using recursion while minding rules
void traverse(node *node, int total, char way[dim1], int numberOfMoves, int intWay[dim1]) {

    //ıf null it is end of the pyramid, if "-1" it is prime


    if (node == NULL) {
        if (numberOfMoves > maxMoves) {
            maxTotal = total;
            maxMoves = numberOfMoves;
            strcpy(maxWay, way);
            arrCpy(maxIntWay, intWay);
            return;
        }
        if (numberOfMoves == maxMoves && total > maxTotal) {
            maxTotal = total;
            maxMoves = numberOfMoves;
            strcpy(maxWay, way);
            arrCpy(maxIntWay, intWay);
            return;
        }
        return;
    }
    if (node->key == -11) {
        return;
    }
    //Traversing starting from left side and saving which way we went
    way[numberOfMoves] = 'r';
    intWay[numberOfMoves] = node->key;
    traverse(node->rightDiagonal, total + node->key, way, numberOfMoves + 1, intWay);

    way[numberOfMoves] = 'd';
    intWay[numberOfMoves] = node->key;
    traverse(node->downward, total + node->key, way, numberOfMoves + 1, intWay);

//   way[numberOfMoves] = 'l';
//   intWay[numberOfMoves] = node->key;
//   traverse(node->leftDiagonal, total + node->key, way, numberOfMoves + 1, intWay);

}


int main() {
    char in;
    FILE *s;
    int i;

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

    fp = fopen("input2.txt", "w");
    fprintf(fp,"%s", l);
    fclose(fp);

    int dim = learnArrDim();
    int triangle[dim][dim];
    if ((s = fopen("input2.txt", "r")) == NULL) {
        printf("Error! opening file");
        // Program exits if file pointer returns NULL.
        exit(1);
    }


    for (int k = 1; k < dim + 1; k++) {
        for (int l = 0; l < k; l++) {
            fscanf(s, "%d", &i);
            //printf("%d ", i);
            if (isPrime(i))
                i = -11;
            triangle[k - 1][l] = i;
        }
    }
    fclose(s);
    printf("\n");
    for (int k = 1; k < dim + 1; k++) {
        for (int l = 0; l < k; l++) {
            printf("%d ", triangle[k - 1][l]);
        }
        printf("\n");
    }
    fill(triangle, 0, 0, &head, dim);
    node *a = head;
    char way[dim];
    int intWay[dim];
    maxWay = malloc(sizeof(way));
    maxIntWay = malloc(sizeof (intWay));
    traverse(a, 0, way, 0, intWay);
    printf("\n");
    printf("way -> %s, total -> %d, number of moves-> %d", maxWay, maxTotal, maxMoves);
    fflush(stdout);
    printf("\n");
    for (int j = 0; j < dim; ++j) {
        printf("%d -> ", maxIntWay[j]);

    }
    return 0;
}