#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define lines 100
#define columns 100
#define true 1
#define false 0
#define LAUNCH_AS_INDEPENDENT

typedef _Bool bool;

typedef struct result {
    char data[lines+1][columns+1];
    struct result* next;
} result;

void tilt(int dir_y, int dir_x, char data[lines+1][columns+1], int length, int width) {
    int line;
    int column;

    int _line;
    int _column;

    if ((dir_y == -1) || (dir_x == -1)) {

        for (line = 0; data[line][0]; line++) {

            for (column = 0; data[line][column]; column++) {

                if (data[line][column] != 'O') continue;

                _line = line;
                _column = column;

                while ((_line + dir_y >= 0) && (_column + dir_x >= 0) && (data[_line + dir_y][_column + dir_x] == '.')) {
                    data[_line][_column] = '.';
                    data[_line + dir_y][_column + dir_x] = 'O';
                    _line += dir_y;
                    _column += dir_x;
                }
            }
        }
    }
    else {

        for (line = length-1; line >= 0; line--) {

            for (column = width-1; column >= 0; column--) {

                if (data[line][column] != 'O') continue;

                _line = line;
                _column = column;

                while ((_line + dir_y < lines) && (_column + dir_x < columns) && (data[_line + dir_y][_column + dir_x] == '.')) {
                    data[_line][_column] = '.';
                    data[_line + dir_y][_column + dir_x] = 'O';
                    _line += dir_y;
                    _column += dir_x;
                }

            }
        }
    }
}

void cycle(char data[lines+1][columns+1], int length, int width) {
    tilt(-1, 0, data, length, width);
    tilt(0, -1, data, length, width);
    tilt(1, 0, data, length, width);
    tilt(0, 1, data, length, width);
}

int calc_load(char data[lines+1][columns+1], int length, int width) {
    int load = 0;

    int i;
    int j;
    for (i = 0; i < length+1; i++) {
        j = 0;
        for (j = 0; j < width+1; j++) {

            if (data[i][j] == 'O') load += length-i;
        }
    }

    return load;
}

void print_data(char data[lines+1][columns+1], int length, int width) {
    int i;
    int j;
    for (i = 0; i < length; i++) {
        j = 0;
        printf("\n");
        for (j = 0; j < width; j++) {
            printf("%c", data[i][j]);
        }
    }
}

void add_to_known_results(char data[lines+1][columns+1], result* results) {
    result* current = results;
    while (current->next) {
        current = current->next;
    }
    current->next = malloc(sizeof(result));
    current->next->next = NULL;
    int i;
    int j;
    for (i = 0; i < lines+1; i++) {
        for (j = 0; j < columns+1; j++) {
            current->data[i][j] = data[i][j];
        }
    }
}

int get_results_length(result* results) {
    int length = 0;
    result* current = results;
    while (current->next) {
        current = current->next;
        length++;
    }
    return length;
}

bool is_equal(char data_a[lines+1][columns+1], char data_b[lines+1][columns+1]) {
    int i;
    int j;
    for (i = 0; i < lines+1; i++) {
        for (j = 0; j < columns+1; j++) {
            if (data_a[i][j] != data_b[i][j]) return false;
        }
    }
    return true;
}

int get_index_of_result(char data[lines+1][columns+1], result* results) {

    result* current = results;
    int index = 0;

    bool equal = is_equal(data, current->data);
    while (current->next && !equal) {
        current = current->next;
        equal = is_equal(data, current->data);
        index++;
    }

    if (equal) {
        return index;
    }

    return -1;
}

void assign_result_at_index(char data[lines+1][columns+1], result* results, int index) {
    result* current = results;
    int i;
    int j;
    for (i = 0; i < index; i++) current = current->next;

    for (i = 0; i < lines+1; i++) {

        for (j = 0; j < columns+1; j++) {

            data[i][j] = current->data[i][j];
        }
    }
}

int main(void) {
    FILE* fptr;

    char* filename = "data";

    fptr = fopen(filename, "r");

    if (fptr == NULL) {
        printf("File '%s' not found. Program will now exit.\n", filename);
        exit(0);
    }
    else {
        printf("File opened successfully.\n");
    }

    char data[lines+1][columns+1];
    int i;
    int j;

    //Nullify the 2-dimensional array
    for (i = 0; i < lines+1; i++) {
        j = 0;
        for (j = 0; j < columns+1; j++) {
            data[i][j] = 0;
        }
    }

    //Read in the data
    i = 0;
    j = 0;
    char chr;
    int length = 0;
    int width = 0;
    while(chr = fgetc(fptr)) {
        if (chr == EOF) break;
        if (chr == '\n') {
            data[i][j] = '\0';
            if (!i) width = j;
            i++;
            j = 0;
            length++;
        }
        else {
            data[i][j] = chr;
            j++;
        };
    }

    //Copy the data into another 2D-Array for Part 2
    char data2[lines+1][columns+1];
    for (i = 0; i < lines+1; i++) {
        for (j = 0; j < columns+1; j++) {
            data2[i][j] = data[i][j];
        }
    }

    //printf("\nLength: %i\nWidth: %i\n", length, width);


    //Calculate Part 1
    clock_t start = clock();

    tilt(-1, 0, data, length, width);
    int load = calc_load(data, length, width);

    clock_t end = clock();

    double time_to_execute = (double)(end - start) / CLOCKS_PER_SEC;

    printf("\nPart 1:\n Time needed: %.3lfs\n Load: %i\n", time_to_execute, load);

    //Calculate Part 2
    start = clock();

    result* results = malloc(sizeof(result));
    results->next = NULL;
    int needed_iteration = 1e9;

    int loop_start = -1;
    while (true) {
        cycle(data2, length, width);
        loop_start = get_index_of_result(data2, results);
        if (loop_start != -1) break;
        add_to_known_results(data2, results);
    }
    int loop_end = get_results_length(results);
    int loop_length = loop_end - loop_start;
    int result_index_for_needed_iteration = loop_start + (needed_iteration - 1 - loop_start) % loop_length;
    assign_result_at_index(data2, results, result_index_for_needed_iteration);

    //printf("\nLoop: %i-%i, Length: %i\n", loop_start, loop_end, loop_length);

    load = calc_load(data2, length, width);

    end = clock();

    time_to_execute = (double)(end - start) / CLOCKS_PER_SEC;

    printf("\nPart 2:\n Time needed: %.3lfs\n Load: %i\n", time_to_execute, load);

    fclose(fptr);

    //To stop the program to exit after execution if it is supposed to start outside the terminal
#ifdef LAUNCH_AS_INDEPENDENT
    getchar();
#endif /*LAUNCH_AS_INDEPENDENT*/
}