#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "mpi/mpi.h"

#define SIZE_X 10
#define SIZE_Y 15
#define MAX_ITERATIONS 10

void print_state(int *matrix) {
    for (int i = 0; i < SIZE_X; i++) {
        for (int j = 0; j < SIZE_Y; j++) {
            printf("%d ", matrix[i * SIZE_X + j]);
        }
        printf("\n");
    }
    printf("\n");
}

void generate_glider(int *cur_state) {//Making first state called "Glider"
    for (int i = 0; i < SIZE_X * SIZE_Y; i++) {
        cur_state[i] = 0;
    }

    cur_state[0 * SIZE_X + 1] = true;
    cur_state[1 * SIZE_X + 2] = true;
    cur_state[2 * SIZE_X + 0] = true;
    cur_state[2 * SIZE_X + 1] = true;
    cur_state[2 * SIZE_X + 2] = true;
}

int count_neighbors(const int *board, int row, int col) {
    int count = 0;

    // Iterate through all the neighbors
    for (int i = row-1; i <= row+1; i++) {
        for (int j = col-1; j <= col+1; j++) {
            // Calculate the row and column indices of the current neighbor,
            // taking into account the toroidal nature of the grid
            int neighbor_row = (i + SIZE_X) % SIZE_X;
            int neighbor_col = (j + SIZE_Y) % SIZE_Y;

            // Check if the current neighbor is not the same as the given cell
            if (!(neighbor_row == row && neighbor_col == col)) {
                // If the neighbor is alive, increment the count
                if (board[neighbor_row * SIZE_X + neighbor_col] == 1) {
                    count++;
                }
            }
        }
    }

    return count;
}

int count_top_neighbors(const int *board, const int *top, int row, int col) {
    int count = 0;
    int top_row = (row - 1 + SIZE_X) % SIZE_X;

    // Iterate through all the neighbors
    for (int i = top_row; i <= row+1; i++) {
        for (int j = col-1; j <= col+1; j++) {
            // Calculate the row and column indices of the current neighbor,
            // taking into account the toroidal nature of the grid
            int neighbor_row = (i + SIZE_X) % SIZE_X;
            int neighbor_col = (j + SIZE_Y) % SIZE_Y;

            // Check if the current neighbor is not the same as the given cell
            if (!(neighbor_row == row && neighbor_col == col)) {
                // If the neighbor is alive, increment the count
                if (i == top_row) {
                    if (top[neighbor_col] == 1) {
                        count++;
                    }
                } else if (board[neighbor_row * SIZE_X + neighbor_col] == 1) {
                    count++;
                }
            }
        }
    }

    return count;
}

int count_bottom_neighbors(const int *board, const int *bottom, int row, int col) {
    int count = 0;
    int bottom_row = (row + 1) % SIZE_X;

    // Iterate through all the neighbors
    for (int i = row-1; i <= bottom_row; i++) {
        for (int j = col-1; j <= col+1; j++) {
            // Calculate the row and column indices of the current neighbor,
            // taking into account the toroidal nature of the grid
            int neighbor_row = (i + SIZE_X) % SIZE_X;
            int neighbor_col = (j + SIZE_Y) % SIZE_Y;

            // Check if the current neighbor is not the same as the given cell
            if (!(neighbor_row == row && neighbor_col == col)) {
                // If the neighbor is alive, increment the count
                if (i == bottom_row) {
                    if (bottom[neighbor_col] == 1) {
                        count++;
                    }
                } else if (board[neighbor_row * SIZE_X + neighbor_col] == 1) {
                    count++;
                }
            }
        }
    }

    return count;
}

int main() {
    int rank, size;
    MPI_Init(NULL, NULL);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int** all_states = (int**)malloc(MAX_ITERATIONS * sizeof(int*));
    int* flags = (int*)malloc(MAX_ITERATIONS * sizeof(int));
    int* initial_state = (int*)malloc(SIZE_X * SIZE_Y * sizeof(int));


    int rows_per_proc = SIZE_X / size;
    int remaining_rows = SIZE_X % size;
    int* send_counts = (int*)malloc(size * sizeof(int));
    int* displs = (int*)malloc(size * sizeof(int));

    int offset = 0;
    for (int i = 0; i < size; i++) {
        send_counts[i] = rows_per_proc * SIZE_Y;
        if (remaining_rows > 0) {
            send_counts[i] += SIZE_Y; // add an extra row to the first few processes
            remaining_rows--;
        }
        displs[i] = offset;
        offset += send_counts[i];
    }

    int *curr_state = malloc(send_counts[rank] * sizeof(int));

    MPI_Scatterv(initial_state, send_counts, displs, MPI_INT, curr_state, send_counts[rank], MPI_INT, 0, MPI_COMM_WORLD);
    int* top_line = (int*)malloc(SIZE_Y * sizeof(int));
    int* bottom_line = (int*)malloc(SIZE_Y * sizeof(int));
    int height = send_counts[rank] / SIZE_X;

    for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
        all_states[iter] = curr_state;
        all_states[iter+1] = (int *) malloc(SIZE_X * SIZE_Y * sizeof(int));

        MPI_Request send_top, receive_bottom, send_bottom, receive_top;

        MPI_Isend(&all_states[iter][0], SIZE_Y, MPI_INT, (rank + size - 1) % size, 1, MPI_COMM_WORLD, &send_top);
        MPI_Isend(&all_states[iter][SIZE_Y * (SIZE_X - 1)], SIZE_Y, MPI_INT, (rank + 1) % size, 2, MPI_COMM_WORLD, &send_bottom);
        MPI_Irecv(bottom_line, SIZE_Y, MPI_INT, (rank + 1 ) % size, 1, MPI_COMM_WORLD, &receive_bottom);
        MPI_Irecv(top_line, SIZE_Y, MPI_INT, (rank - 1 + size) % size, 2, MPI_COMM_WORLD, &receive_top);
        for (int i = 1; i < height - 1; i++) {
            for (int j = 0; j < SIZE_Y; j++) {
                int neighbors = count_neighbors(all_states[iter], i, j);

                if (all_states[iter][i* SIZE_X + j] == 1 && (neighbors < 2 || neighbors > 3)) {
                    all_states[iter+1][i * SIZE_X + j] = false;
                }
                else if (all_states[iter][i * SIZE_X + j] == 0 && neighbors == 3) {
                    all_states[iter+1][i * SIZE_X + j] = true;
                }
                else {
                    all_states[iter+1][i * SIZE_X + j] = all_states[iter][i * SIZE_X + j];
                }
            }
        }

        MPI_Wait(&send_top, MPI_STATUS_IGNORE);
        MPI_Wait(&receive_top, MPI_STATUS_IGNORE);
        for(size_t i = 0; i < SIZE_Y; i++){
            int neighbors = count_top_neighbors(all_states[iter], top_line, 0, (int)i);

            if (all_states[iter][0* SIZE_X + i] == 1 && (neighbors < 2 || neighbors > 3)) {
                all_states[iter+1][0 * SIZE_X + i] = false;
            }
            else if (all_states[iter][0 * SIZE_X + i] == 0 && neighbors == 3) {
                all_states[iter+1][0 * SIZE_X + i] = true;
            }
            else {
                all_states[iter+1][0 * SIZE_X + i] = all_states[iter][0 * SIZE_X + i];
            }
        }

        MPI_Wait(&send_bottom, MPI_STATUS_IGNORE);
        MPI_Wait(&receive_bottom, MPI_STATUS_IGNORE);

        for(size_t i = 0; i < SIZE_Y; i++){
            int neighbors = count_bottom_neighbors(all_states[iter], bottom_line, SIZE_Y-1, (int)i);

            if (all_states[iter][(SIZE_Y-1)* SIZE_X + i] == 1 && (neighbors < 2 || neighbors > 3)) {
                all_states[iter+1][(SIZE_Y-1) * SIZE_X + i] = false;
            }
            else if (all_states[iter][(SIZE_Y-1) * SIZE_X + i] == 0 && neighbors == 3) {
                all_states[iter+1][(SIZE_Y-1) * SIZE_X + i] = true;
            }
            else {
                all_states[iter+1][(SIZE_Y-1) * SIZE_X + i] = all_states[iter][(SIZE_Y-1) * SIZE_X + i];
            }
        }

        for (int back_step = iter; back_step >= 0; back_step--)
        {
            flags[back_step] = 1;
            for (int i = 0; i < SIZE_X; i++)
            {
                for (int j = 0; j < SIZE_Y; j++)
                {
                    if (curr_state[i * SIZE_X + j] != all_states[back_step][i * SIZE_X + j])
                    {
                        flags[back_step] = 0;
                        break;
                    }
                }
                if (flags[back_step] == 0)
                    break;
            }
        }

        MPI_Allreduce(MPI_IN_PLACE, flags, MAX_ITERATIONS, MPI_INT, MPI_LAND, MPI_COMM_WORLD);

        int check = 0;
        for (int i = 0; i < iter; i++){
            if (flags[i] == 1){
                check = 1;
                break;
            }
        }

        if (check == 1){
            printf("SOLVED %d \n", iter);
            break;
        }

        curr_state = all_states[iter+1];
    }


    if(rank == 0){
        for(size_t i = 0; i < size; i++){
            printf("%zu %d %d\n", i, displs[i], send_counts[i]);
        }

    }

    free(all_states);
    free(curr_state);
    
    MPI_Finalize();
}