#include <stdio.h>
#include <stdint.h>

///////////////
// CONSTANTS //
///////////////

#define TRUE 	1
#define FALSE 	0

#define MIN_HEIGHT 4
#define MAX_HEIGHT 6

#define MIN_WIDTH 10
#define MAX_WIDTH 40

#define FORWARD_KEY 'd'
#define JUMP_KEY 'w'
#define PLAYER_CHAR 'P'
#define EXIT_KEY 'q'

#define EMPTY 0
#define BLOCK 1
#define SPIKE 2
#define TOTAL_TILES 3

#define EMPTY_WEIGHT 45
#define BLOCK_WEIGHT 4
#define SPIKE_WEIGHT 2

#define SIZE_OF_CELL 12

struct Player {
    int x;
    int y;
    int vy;
    int on_block;
};

struct Cell {
    char possible[TOTAL_TILES];
    int collapsed;
    int tile;
};

///////////////
/// GLOBALS ///
///////////////

struct Cell grid[MAX_HEIGHT][MAX_WIDTH];

char tile_chars[] = {' ', '#', '^'};

int weighted[TOTAL_TILES * 100];

int game_in_action;

int height;
int width;

int rand_seed;

int best_x;
int best_y;

///////////////
// FUNCTIONS //
///////////////

// Subset 0
void print_welcome();
int main();

// Subset 1
void game_loop();
void get_input();
int calculate_weighted_probability(int best_x, int best_y);
int test_above_cells(int y, int x, int t);

// Subset 2
int test_cell(struct Cell *test);
void init_game();
int check_possible(int best_y, int best_x, int t);
void collapse();
void init_grid();

// Subset 3
void get_lowest_entropy_tile(int *best_x, int *best_y);
int is_valid(int y, int x, int t);
void calculate_player_move(struct Player *player, char input);

// Supplied
void propagate();
void print_board_with_player(struct Player *player);
unsigned int rand_value(unsigned int n);

//////////////
// SUBSET 0 //
//////////////
void print_welcome() {
    printf("Welcome to 1521 geometry dash!\n");
    printf("To move forwards, press %c\n", FORWARD_KEY);
    printf("To jump, press %c\n", JUMP_KEY);
    printf("To exit, press %c\n", EXIT_KEY);
    printf("Jump onto platforms and around spikes to avoid them\n");
    printf("If you jump onto a spike you lose :(\n");
    printf("Try make it to the end of the map!\n");
}

int main(void) {
    print_welcome();

    get_input();

    init_grid();

    init_game();

    game_loop();

    return 0;
}

//////////////
// SUBSET 1 //
//////////////
void game_loop() {
    struct Player player = {
        0,
        height - 2,
        0,
        0
    };
    
    char input;
    while (game_in_action) {
        print_board_with_player(&player);
        printf("Action: ");
        scanf(" %c", &input);
        calculate_player_move(&player, input);
    }
}

void get_input() {
    printf("Please select a width (10-40): ");
    scanf("%d", &width);

    while (width < MIN_WIDTH || width > MAX_WIDTH) {
        printf("Invalid width.");
        printf("Please select a width (10-40): ");
        scanf("%d", &width);
    }

    printf("Please select a height (4-6): ");
    scanf("%d", &height);

    while (height < MIN_HEIGHT || height > MAX_HEIGHT) {
        printf("Invalid height.");
        printf("Please select a height (4-6): ");
        scanf("%d", &height);
    }

    printf("Please enter a random seed: ");
    scanf("%d", &rand_seed);

    rand_value(rand_seed);
}

int calculate_weighted_probability(int x, int y) {
    int weighted_count = 0;

    for (int t = 0; t < TOTAL_TILES; t++) {
        if (!check_possible(y, x, t)) {
            continue;
        }
        
        int weight = 0;
        if (t == EMPTY)  {
            weight = EMPTY_WEIGHT;
            // 45
        } else if (t == BLOCK) {
            weight = BLOCK_WEIGHT;
            //4
        } else if (t == SPIKE) {
            weight = SPIKE_WEIGHT;
            // 2
        }
        
        for (int w = 0; w < weight; w++) {
            weighted[weighted_count] = t;
            weighted_count++;
        }
    }

    return weighted_count;
}

int test_above_cells(int y, int x, int t) {
    struct Cell *above = &grid[y - 1][x];

    if (t == SPIKE) {
        if (test_cell(above)) {
            return 0;
        }
        if (x > 0 && test_cell(&grid[y - 1][x - 1])) {
            return 0;
        }
        if (x < width - 1 && test_cell(&grid[y - 1][x + 1])) {
            return 0;
        }
    }

    if (t == BLOCK) {
        if (test_cell(above)) {
            return 0;
        }
    }

    return 1;
}

//////////////
// SUBSET 2 //
//////////////

int test_cell(struct Cell *test) {
    if ((test->collapsed && test->tile == EMPTY) || (!test->collapsed && test->possible[EMPTY])) {
        return 0;
    }
    return 1;
}

void init_game() {
    game_in_action = 1;

    for (int i = 0; i < height * width; i ++) {
        propagate();
        collapse();
    }
}

int check_possible(int y, int x, int t) {
    return grid[y][x].possible[t];
}

void collapse() {
    best_x = -1;
    best_y = -1;
    
    get_lowest_entropy_tile(&best_x, &best_y);

    if (best_y == -1) {
        return;
    }
    
    int weighted_count = calculate_weighted_probability(best_x, best_y);
    
    grid[best_y][best_x].tile = weighted[rand_value(weighted_count)];
    grid[best_y][best_x].collapsed = 1;
}

void init_grid() {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            grid[y][x].collapsed = 0;
            for (int t = 0; t < TOTAL_TILES; t ++) {
                grid[y][x].possible[t] = 1;
            }
        }
    }

    for (int x = 0; x < width; x ++) {
        grid[height - 1][x].tile = BLOCK;
        grid[height - 1][x].collapsed = 1;
    }
}

void get_lowest_entropy_tile(int *bx, int *by) {
    int min_entropy = TOTAL_TILES + 1;
    *bx = -1;
    *by = -1;

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (grid[y][x].collapsed) {
                continue;
            }

            int entropy = 0;
            for (int t = 0; t < TOTAL_TILES; t++) {
                if (grid[y][x].possible[t]) {
                    entropy++;
                }
            }

            if (entropy < min_entropy) {
                min_entropy = entropy;
                *by = y;
                *bx = x;
            }
        }
    }
}

//////////////
// SUBSET 3 //
//////////////

int is_valid(int y, int x, int t) {
    if (y < height - 1) {
        struct Cell *below = &grid[y + 1][x];

        if (t != EMPTY) {
            if (below->collapsed && below->tile == SPIKE) {
                return 0;
            }
        }
    }

    if (y > 0) {
        if (test_above_cells(y, x, t) == 0) {
            return 0;
        }
    }

    if (t == SPIKE) {
        if (x > 0 && grid[y][x - 1].collapsed && grid[y][x - 1].tile == SPIKE) {
            return 0;
        }
        if (x < width - 1 && grid[y][x + 1].collapsed && grid[y][x + 1].tile == SPIKE) {
            return 0;
        }
    }

    return 1;
}


void calculate_player_move(struct Player *player, char input) {
    if (input == EXIT_KEY) {
        game_in_action = 0;
        return;
    }

    if (player->x >= width - 1) {
        printf("You win!\n");
        game_in_action = 0;
        return;
    }

    player->vy++;
        
    if (input == JUMP_KEY && player->on_block) {
        player->vy = -1;
    }

    if (input == FORWARD_KEY && grid[player->y][player->x + 1].tile != BLOCK) {
        player->x++;
    }
        
    player->y += player->vy;
        
    player->on_block = 0;

    if (player->y >= height - 1) {
        player->y = height - 1;
        player->vy = 0;
        player->on_block = 1;
    }

    if (grid[player->y][player->x].tile == BLOCK) {
        player->y--;
        player->vy = 0;
        player->on_block = 1;
    }

    if (player->y + 1 < height && player->x < width) {
        if (grid[player->y + 1][player->x].tile == BLOCK) {
            player->vy = 0;
            player->on_block = 1;
        }
    }

    if (grid[player->y][player->x].tile == SPIKE) {
        printf("You died!\n");
        game_in_action = 0;
        return;
    }

    return;
}

//////////////
// PROVIDED //
//////////////

void print_board_with_player(struct Player *player) {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (x == player->x && y == player->y) {
                printf("%c", PLAYER_CHAR);
            } else {
                printf("%c", tile_chars[grid[y][x].tile]);
            }
        }
        printf("\n");
    }
}


void propagate() {
    int changed;
    do {
        changed = 0;
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (grid[y][x].collapsed) {
                    continue;
                }

                for (int t = 0; t < TOTAL_TILES; t ++) {
                    if (grid[y][x].possible[t]) {
                        if (!is_valid(y, x, t)) {
                            grid[y][x].possible[t] = 0;
                            changed = 1;
                        }
                    }
                }
            }
        }
    } while (changed);
}

unsigned int rand_value(unsigned int n) {
	rand_seed = (rand_seed * 1103515245u + 12345u) & 0x7FFFFFFF;
	return rand_seed % n;
}

