#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

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;
    }


}

//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("input.txt", "r")) == NULL) {
        printf("Error! opening file");
        // Program exits if file pointer returns NULL.
        exit(1);
    }

    while ((in = fgetc(s)) != EOF) {
        printf("%c", in);
        if (in == '\n')
            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) {

    //ıf null it is end of the pyramid, if "-1" it is prime
    if (node == NULL || node->key == -1) {
        if (numberOfMoves > maxMoves) {
            maxTotal = total;
            maxMoves = numberOfMoves;
            strcpy(maxWay, way);
            return;
        }
        if (numberOfMoves == maxMoves && total > maxTotal) {
            maxTotal = total;
            maxMoves = numberOfMoves;
            strcpy(maxWay, way);
            return;
        }
        return;
    }
    //Traversing starting from left side and saving which way we went
    way[numberOfMoves] = 'l';
    traverse(node->leftDiagonal, total + node->key, way, numberOfMoves + 1);

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

    way[numberOfMoves] = 'r';
    traverse(node->rightDiagonal, total + node->key, way, numberOfMoves + 1);
}


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

    int dim = learnArrDim();
    int triangle[dim][dim];
    if ((s = fopen("input.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 = -1;
            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];
    maxWay = malloc(sizeof(way));
    traverse(a, 0, way, 0);
    printf("\n");
    printf("way -> %s, total -> %d, number of moves-> %d", maxWay, maxTotal, maxMoves);
    return 0;
}