/*Find the determinant of any matrix of any size
-Split every matrix to a lower-in-size ones and so on until reach the 2x2 matrices
then find the determinant of each 2x2 matrix, multiply them by the required elements from higher-in-size matrices,
add them according to a special algorithm that obeys the proper signs of each.

-pros: very smart and special way to develop programmatically, it may be used as a part of other analysis/hacking purposes for matrices components
-Two big cons: it consumes a lot of time and memory for matrices of size higher than 8x8.

Author: @Yahya Almardeny
21/06/2016
*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>





int COL; // the size of the matrix inserted by the user

void split_matrix(int *matrix[COL]);
void create_array(int dimension);
void free_array(int *input_matrix[COL]);
void remove_unwanted_elements(int number_of_elements);
void copy_container_to_input_matrix(int size_of_matrix );
void receive_input_for_first_time();
void number_of_matrices_to_split_fun();
void pick_up_required_elements();
void change_container_to_2in2_determinants();
void process_determinant();
void find_2in2_determinant(); // if the user chose 2in2 matrix from the beginning!
int receive_and_validate_input ();

int **input_matrix; // 2D Dynamic array which receives the user input then will be used for splitting
int *container; // dynamic array which will contain all results before it changes to determinants of 2in2 matrices
int *pick_up_array; // dynamic array to pick up required elements for calculating the determinant

int copy_variable; // to copy from container to input_matrix
int container_index; // index for the current position & size of the array "container"
int print_var; // for printing purpose , for the container
int number_of_matrices_to_split; // specifies how many matrices will be split
int COL_value; // because COL is changing , this is to be used as the original value of COL in later functions
int number_of_2in2_elements; // will be used to estimate the maximum size of the container to be created
int pick_up_index; // determines the index in the pick_up_array while picking up the required elements
int determinant; // the final answer: the determinant

typedef enum{// create boolean type
TRUE,
FALSE
}boolean;
boolean start_from_index_zero; // to inform that the splitter should copy itself into index zero in the destination container
boolean first_time_to_copy; // to start from index 0 when the copy_container_to_input_matrix() function executes
boolean first_split; // global boolean variable to control the first time of thee function number_of_matrices_to_split()
boolean first_pick_up; // global boolean variable to control first pick up

int main(){

//take the input
printf("Please Insert the Size of the Matrix (e.g insert 3 for 3x3 matrix) : "); COL = receive_and_validate_input(1); // passing 1 in the receive_and_validate_input() activates rejecting the negative values
/*if user wants to know the determinant of 2in2 matrix, no need for all of this hard work, it can be calculated easily!*/
if (COL ==2 ){find_2in2_determinant();
printf("**************************\n");
printf("The determinant is: %d\n" , determinant);
printf("**************************\n");
}

/*if user chose a matrix of size greater than 2 then do the hard work*/
else{

int x, y ,start_var = 3; //start from the 3*3 matrices
long elements =4; // the size of 2*2 matrices inside every 3*3 matrix
pick_up_index = 0;

/*estimate how many elements inside the entire-produced 2in2 matrices to be used to determine the size of the container*/
while (start_var<=COL){
    elements = elements * start_var;
    start_var++;
}
number_of_2in2_elements = elements-1; // we subtract 1 because container starts from index 0 and "number_of_2in2_elements" will be used in such calculations later
elements = elements + (elements*0.75); //to include the 2*2 matrices & the 3*3 matrices

container =  calloc((elements) , sizeof(int)); // create the array "container" of size elements
if (container == NULL || container == 0){printf("***Failure, Either you chose a high matrix size that your computer cannot provide\
                       enough memory for or There is no enough memory to execute****\n"); exit(0);}

COL_value =COL;// because COL is changing , this is to be used as the original value of COL in later functions
int move_to_next_dimenssion = (COL-3); // because there is no splitting from level 2 to 1 and from 1 to 0! thus subtract 3


first_split = TRUE; // for number_of_matrices_to_split_fun() , to inform that it is the first time/round
number_of_matrices_to_split_fun();
first_time_to_copy = TRUE;
receive_input_for_first_time();

/*the main work and flow in high level of details*/
for(x = 0 ; x < move_to_next_dimenssion; x++ ){

printf("***************\n");
printf ("%din%d Matrices:\n" , COL-1, COL-1);
printf("***************\n");

    for (y= 0 ; y < number_of_matrices_to_split; y++){
                create_array(COL);
                copy_container_to_input_matrix(COL);
                pick_up_required_elements();
                split_matrix(input_matrix);
                free_array(input_matrix);
                }

number_of_matrices_to_split_fun(); //function to determine how many matrices to be split then used in this loop (i.e. number_of_matrices_to_split)
COL--;
remove_unwanted_elements(copy_variable); // just to save memory, thus we do not need to create a bigger container in the beginning of this program

}

change_container_to_2in2_determinants();
process_determinant();
printf("**************************\n");
printf("The determinant is: %d\n" , determinant);
printf("**************************\n");

/*free arrays container and pick_up_array*/
free(container);
free(pick_up_array);
}

getchar();

return 0;}



void split_matrix(int *matrix[COL]){ // this function to split the passed matrix into a lower one in size and print it out in like-look matrix appearance

int break_line = 1, newline_reference , newline_index =1;
int  row1, col1 , row , col , x  ,y, unwanted_col;
int ***splitter; // 3D array to be used in splitting the received matrix
splitter = calloc(COL , sizeof(int**)); // the first dimension will guide how to split the matrix
for (x=0 ; x <(COL); x++){splitter[x] = calloc((COL-1) , sizeof(int *)); // the second & third dimensions should be of the same size of the matrix will be produced
    for (y=0 ; y <(COL-1) ; y++){splitter[x][y] = calloc((COL-1) , sizeof(int));}} //this is why it's COL-1 , to be smaller in on level

if (splitter == NULL){printf("Failed To Split"); exit(0);} // inform failure to create the splitter
/*even it contains 3 for loops but it finishes a group of matrices in every big round*/
for (x =0, unwanted_col = 0 ; x < COL ; x++ , unwanted_col++){ // loop according to the first dimension of the splitter which is the same of the original(passed) matrix, with every loop there is unwanted column should be ignored( i.e. first loop is the first m second loop is the second and so on)
  for (row = 0 , row1=0; row1 < COL ; row1++ ){// will loop the matrix row /*here we finish all the columns in every row i.e. row row*/
    for (col=0, col1 =0; col1 < COL; col1++){ // will loop the matrix column /* here we move from column to another in every loop, once we finish them all , we move to the next row
        if (row1!=0 && col1 !=unwanted_col){  // we always don't want the first row of the passed matrix , but the column should follow the unwanted_col which changes in every big loop for the entire matrix
            splitter[x][row][col]= matrix[row1][col1]; // if it is not the first row and not the unwanted column then assign it to splitter
            col++; // after receiving the first col from the matrix, move to the next col in the splitter to receive the next column
            if (col == (COL-1)){row++;}// as we should move to next row in the splitter after we go through all the required column, we now this because the split matrix is of size (COL-1inCOL-1)

        }
        }
        }
}



// copy to the container
if (start_from_index_zero == TRUE) // this is true if the "receive_input_for_first_time()" function is executed
    {container_index =0; print_var = 0;
        newline_reference = COL-1; /*this will determine when to make a new line, it will be a reference to the newline_index*/
    }
for (x = 0 ; x <COL ; x++ ){
    for (row = 0 ; row <COL-1 ; row++ ){
        for (col = 0 ; col <COL-1 ; col++, container_index++){
            container[container_index] = splitter[x][row][col];// container_index will accumulate after this round i.e. when start_from_index_zero becomes false
            }
            }
}

newline_reference = COL-1; // because we moved to a lower dimension, the matrix to be printed is smaller now, this executes before the COL-- in the main function!
while (print_var != container_index){ // this while loop just for printing purpose , it will print out all non-printed elements, the reference is container_index
        printf("%d ", container[print_var]); //print the element
        print_var++; // then increment print_var to print the next element in the second round/loop
        if (newline_index == newline_reference){ // newline_reference is the column size of the matrix, it is fixed in every round but changes when the matrix changes its size in the main function
            printf("\n"); newline_index =0; // break the line and recount again
            }
        if(break_line == (newline_reference*newline_reference)) {printf("\n"); break_line=0;} // this determines when the the entire matrix has been printed start to start a new one
        break_line++; newline_index++; }



/*free the array "Splitter"*/
for (x=0 ; x <(COL); x++){
for (y=0 ; y <(COL-1) ; y++){free(splitter[x][y]);} free(splitter[x]);}
free(splitter);
}



void create_array(int dimension){ // create 2D dynamic array based on the dimension of the required input_matrix
int row_input, col_input;
input_matrix = (int**) calloc(dimension, sizeof(int*));
for(col_input = 0 ; col_input<dimension ; col_input++){input_matrix[col_input] = (int*)calloc(dimension, sizeof(int));}
if (input_matrix == NULL){printf("Failed To Create Input_Matrix\n");}
}




void free_array(int *input_matrix[COL]){//simply free the input_matrix after each use, that will be controlled by in the main function
int x;
for (x=0 ; x<(COL-1) ; x++){free(input_matrix[x]);}
free(input_matrix);
}




void receive_input_for_first_time(){

start_from_index_zero = TRUE; // to make the splitter start copying itself to the container into the index zero
create_array(COL); // create an array of size "COL" (i.e. column specified by the user)
printf("\nNow Please Insert the Elements of the Matrix , Row by Row\n");
int row_input, col_input; // variables to loop through while receiving the matrix
for (row_input = 0; row_input<COL ; row_input++){
        for (col_input=0; col_input<COL; col_input++){
                printf("Row %d Column %d: ",row_input+1 ,col_input+1);
                input_matrix[row_input][col_input]=receive_and_validate_input (2);// this function receive input and validate it then return the validated integer/input
                // passing two activates accepting negative values/integers
                printf("-------------------\n");
                }
        }
printf("\n***************\n");
printf ("%din%d Matrices:\n" , COL-1, COL-1);
printf("***************\n");
split_matrix(input_matrix);//split the matrix already received for the first time
first_pick_up = TRUE; // change it to true to activate the first option of pick_up_required_elements();
pick_up_required_elements(); // to collect the first row of the original matrix/input
free_array(input_matrix); // free it to use it again in later functions
COL--; // decrement the col because we move now to the next-lower dimension/size of the matrix
start_from_index_zero = FALSE; //inform the container to accumulate the container_index , it won't start from zero again.
first_time_to_copy = FALSE; // to inform copy_container_to_input_matrix() in the main function to accumulate the copy_variable, it won't start from zero again.

}





void copy_container_to_input_matrix(int size_of_matrix ){ //determined by the size of the matrix according to the column size

if ((first_time_to_copy == TRUE)){copy_variable =0;} // if it is first time to copy , it should start form index zero
// otherwise it will continue to accumulate copy_variable
int row_input , col_input;
   for (row_input = 0; row_input<size_of_matrix ; row_input++){
                    for (col_input=0; col_input<size_of_matrix; col_input++, copy_variable++ ){
                            input_matrix[row_input][col_input] = container[copy_variable]; // copy the container to the input_matrix every time based on the size

        }
                }

}




void number_of_matrices_to_split_fun(){// determines number of matrices to split
if (first_split == TRUE){
number_of_matrices_to_split = COL; // first time it is the column size for sure , it is controlled by a boolean variable to execute only once
first_split = FALSE;
}
else{number_of_matrices_to_split = number_of_matrices_to_split * COL;} //then it increments according to the new Column value (i.e. new matrix size)
// e.g 5in5 matrix has 5 4in4 matrices and then each 4in4 has 4 3in3 matrices , totally: 5*4 = 20 3in3 matrices
}




void remove_unwanted_elements(int number_of_elements){
int x, y=0 ;
x = number_of_elements;
while (x!=container_index){// index represent the current size of the array "container"
    container[y]=container[x]; // this way only copies the required elements over th unwanted elements
    x++;
    y++;
}

container_index = (container_index - copy_variable); //subtract the current size of the container from the current index value of the copy_container_to_input_matrix represented by copy_variable
// the container_index will have a value of the real-current size of the new container
copy_variable = 0;// make it zero because it will start over form the index zero while copying from container to input_matrix
print_var = container_index;//just for printing purpose, change print_var to size of container as it represents the upper limit for printing out the container content

}


void pick_up_required_elements(){
int i = 3 ,x , no_of_elements_to_save = 1, change_sign = 1;// change_sign variable to control the sings of the elements, it always starts as positive

if (first_pick_up == TRUE){ // boolean variable to create dynamic array for the first time only, it will be activated in receive_input_for_first_time();
if (COL_value ==3){no_of_elements_to_save=3;}
            else {
            while (i<COL_value){// a way to know how many elements will be saved in the pick_up_array
                if (i==3){no_of_elements_to_save = (no_of_elements_to_save * (i * (i+1)));}

                else{no_of_elements_to_save = (no_of_elements_to_save * (i+1));}

                no_of_elements_to_save = no_of_elements_to_save + (i+1);
                i++;
            }
            }

pick_up_array = (int*) calloc(no_of_elements_to_save , sizeof(int));
if (pick_up_array == NULL) {printf("fail"); exit(0);}

first_pick_up = FALSE;}


for (x = 0 ; x < COL ; x++, pick_up_index++ ){ // we need to pick up only the first row of every matrix, that can be controlled by the COL value which changes in the main function loop
    pick_up_array[pick_up_index] = (input_matrix[0][x] * change_sign); // pick up required elements and change the signs properly, first row only
    change_sign = change_sign * (-1);
}
}





void change_container_to_2in2_determinants(){
 int x, y;
 for (x=0 ,y =0; x<=number_of_2in2_elements; x=x+4 , y++){// jump over every 4 elements in every loop because the 2in2 matrix size 4 elements(i.e. to move to next 2in2 matrix)
 container[y] = ((container[x]*container[x+3])-(container[x+1]*container[x+2])); // y controls the index of the container to make them followed right after each other
 }
number_of_2in2_elements = y; // change the number_of_2in2_elements to the real new one because it has become smaller
}



 void process_determinant(){ // a way to multiply the elements in each level by the elements in the next lower level
 int z =0, x , i=COL_value , y=0 , j =0, limit, col_size = (COL_value-1); // limit starts with the size of the first row of the main matrix
 for (y = 0 ,limit = COL_value; y <(COL_value-3) ; y++){
        while (j!=limit){
                for(x =0 ; x <col_size  ; x++ , i++){
                    pick_up_array[i] = pick_up_array[i] * pick_up_array[z]; //multiply the first row in the main matrix with the first row in the next lower level

                }
         j++;// j here to stop while loop when it equals to the limit
         z++;
        }

limit = limit * col_size ; // then limit increases according to the size of the new matrix e.g. 4in4 matrix has 4 3in3 matrices (12 elements to cycle through)
col_size--; // decrement the size of the col for the next-lower level
j=0;//start while loop again from zero to count how many loop to do
}

i--; // decrement i because the array in general start with index 0 , and i here should represent the final index

for (x =(number_of_2in2_elements-1); x >=0 ; x-- , i--){
    container[x] =  (container[x]) * (pick_up_array[i]); //multiply the 2in2_determinants in the container by the pick_up_elements
    }


for (x =0  ; x <number_of_2in2_elements ; x++ ){
    determinant =  determinant + container[x]; // add all the elements to find the determinant
    }
}


int receive_and_validate_input (int x){ // function that receives and validates the user input and returns the validated user input to pass it to the input_matrix


int validated_input; // the value to be returned
int y=0; //loop variable
while (y<5){
boolean reject_input= FALSE; // to determine if the user inserted a negative value to be a size of the matrix
int returned_value =-1;
char line[256];
char *line_pointer = &line[0];
char *p_new = &line[0];
char *p_old = &line[0];
   if (fgets(line, sizeof(line), stdin)){//return 0 if not execute
                /*first remove spaces from the entire string*/
                while (*p_old != '\0'){// loop as long as has not reached the end of string
               *p_new = *p_old; // assign the current value the *line is pointing at to p
                    if (*p_new != ' '){p_new++;} // check if it is not a space , if so , increment p
                p_old++;// increment p_old in every loop
                }
                *p_new = '\0'; // add terminator

                /* check if the first char is (-) or (+) sign to point to next place*/
                if (x==1){
                    if (*line_pointer== '+'){line_pointer++;}
                    if (*line_pointer == '-'){reject_input = TRUE; returned_value = 2;} // because it is a negative number and the size of matrix must be positive
                }
                if (x==2){
                    if (*line_pointer== '+' || *line_pointer == '-'){line_pointer++;}
                }

while (*line_pointer != '\n' && reject_input == FALSE){
    if (!(isdigit(*line_pointer))) {returned_value = 0; break;} // Illegal char found , will return 0 and stop because isdigit() returns 0 if the it finds non-digit
    else if (isdigit(*line_pointer)){line_pointer++; returned_value=1;}//check next place and increment returned_value for the final result and judgment next.
     /*it will return -1 if there is no input at all because while loop has not executed, will return >0 if successful, 0 if invalid input , 2 if negative number inserted*/
     }



     if (returned_value==1){ // check if the string contains only numbers
                     validated_input =strtol(line, NULL, 10); // change the authentic string to long and assign it
                      if (x==1){
                          if (validated_input == 0 || validated_input ==1){printf("Invalid Input, Insert 2 or greater!\n");}
                          else {break;}
                      }
                      else if (x==2){
                      {break;}
                      }
            }
            else if (returned_value==0){printf("Invalid Input, Insert Integers Only!\n");}
            else if (returned_value==2){printf("Insert Positive Integers Only!\n");}
            else if  (returned_value==-1){printf("Empty Input!\n ");}

   }

y++;
if (y==5){printf("****Failure to receive any valid input, No More Retries****\n"); getchar(); exit(0);}
}
return validated_input;


}



void find_2in2_determinant(){
create_array(COL); // create an array of size "COL" (i.e. column specified by the user)
printf("\nNow Please Insert the Elements of the Matrix , Row by Row\n");
int row_input, col_input; // variables to loop through while receiving the matrix
for (row_input = 0; row_input<COL ; row_input++){
        for (col_input=0; col_input<COL; col_input++){
                printf("Row %d Column %d: ",row_input+1 ,col_input+1);
                input_matrix[row_input][col_input]=receive_and_validate_input (2);// this function receive input and validate it then return the validated integer/input
                // passing two activates accepting negative values/integers
                printf("-------------------\n");
                }
        }
determinant = ((input_matrix[0][0]*input_matrix[1][1]) - (input_matrix[0][1]*input_matrix[1][0]));
free_array(input_matrix);
}