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

#include "puzzle_input.h"
#include "day.h"
#include "queue.h"
#include "grid.h"

#define MAX_WIDTH 100
#define QUEUE_SIZE 500

typedef struct {
    int8_t map_data[MAX_WIDTH*MAX_WIDTH];
    uint8_t basin[MAX_WIDTH*MAX_WIDTH];
    uint8_t basin_count;
    int16_t line_width;
} map_data_t;

map_data_t map_data_g = {};

parse_ret_t parse_map_line(char * buffer, void * data, uint16_t index) {
    map_data_t * map_data = (map_data_t *)data;
    int8_t * map_line = map_data->map_data + index * MAX_WIDTH;

    int16_t line_ndx = 0;
    while (buffer[line_ndx] != '\0') {
        map_line[line_ndx] = buffer[line_ndx] - '0';
        line_ndx++;
    }

    map_data->line_width = line_ndx;

    return PARSER_OK;
}

uint8_t get_map_data(const uint8_t * data, int ii, int jj, uint16_t i_len, uint16_t j_len) {
    if ((ii >= i_len) || (ii < 0) || (jj >= j_len) || (jj < 0)) {
        return UINT8_MAX;
    }
    else {
        return *(data + jj + ii * MAX_WIDTH);
    }
}

void set_map_data(uint8_t * data, int ii, int jj, uint16_t i_len, uint16_t j_len, uint8_t val) {
    if ((ii >= i_len) || (ii < 0) || (jj >= j_len) || (jj < 0)) {
        return;
    }
    else {
        *(data + jj + ii * MAX_WIDTH) = val;
    }
}

int8_t is_min(uint8_t * data, int ii, int jj, uint16_t i_len, uint16_t j_len) {
    uint8_t middle = get_map_data(data, ii, jj, i_len, j_len);
    uint8_t up = get_map_data(data, ii-1, jj, i_len, j_len);
    uint8_t down = get_map_data(data, ii+1, jj, i_len, j_len);
    uint8_t left = get_map_data(data, ii, jj-1, i_len, j_len);
    uint8_t right = get_map_data(data, ii, jj+1, i_len, j_len);

    if ((middle < up) && (middle < down) && (middle < left) && (middle < right)) {
        return 1;
    }
    else {
        return 0;
    }
}

static void print_map(uint8_t * map, uint16_t max_i, uint16_t max_j) {
    for (int16_t ii = 0; (int16_t)ii < max_i; ii++) {
        for (int16_t jj = 0; (int16_t) jj < max_j; jj++) {
            printf("%u", get_map_data(map, ii, jj, max_i, max_j));
        }
        printf("\n");
    }
}

static void part_1(uint16_t len) {
    uint16_t risk_sum = 0;
    uint8_t basin_count = 1;
    for (int ii = 0; ii < len; ii++) {
        for (int jj = 0; jj < map_data_g.line_width; jj++) {
            if (is_min((uint8_t *)map_data_g.map_data, ii, jj, len, map_data_g.line_width)) {
                risk_sum += get_map_data((uint8_t *) map_data_g.map_data, ii, jj, len, map_data_g.line_width) + 1;
                set_map_data(map_data_g.basin, ii, jj, len, map_data_g.line_width, basin_count);
                basin_count++;
            }
        }
    }

    map_data_g.basin_count = basin_count;
    printf("PART 1: Low point risk sum is: %d\n", risk_sum);
}

#define WALL 9
static queue_ret_t queue_point(queue_t *queue, int pos_i, int pos_j, uint16_t max_i, uint16_t max_j) {
    point_t point = {0};

    if (get_map_data(map_data_g.basin, pos_i, pos_j, max_i, max_j) > 0) {
        return QUEUE_OK;
    }

    if (get_map_data((uint8_t *)map_data_g.map_data, pos_i, pos_j, max_i, max_j) == WALL) {
        return QUEUE_OK;
    }

    point.ii = pos_i;
    point.jj = pos_j;

    if (point.ii > max_i || point.jj > max_j) {
        printf("Invalid point attempted to be pushed onto queue\n");
        return QUEUE_DATA_INVALID;
    }

    return queue_push(queue, &point);
}

point_t q_data_g[QUEUE_SIZE] = {0};
static int flood_fill( int pos_i, int pos_j, uint16_t max_i, uint16_t max_j, uint8_t basin_count, uint8_t * basin_counts)
{
    queue_t queue = {0};
    point_t point = {0};
    queue_ret_t res;

    queue_init(&queue, q_data_g, QUEUE_SIZE, sizeof(point_t));

    point.ii = pos_i;
    point.jj = pos_j;

    res = queue_push(&queue, &point);

    basin_counts[basin_count - 1] = 1;

    if (res != QUEUE_OK) {
        printf("Unable to insert element: %d", res);
        return -1;
    }

    while (queue.queued_elements > 0) {
        res = queue_pop(&queue, &point);

        if (res != QUEUE_OK) {
            printf("Unable to queue_pop element: %d", res);
            return -1;
        }

        if (point.ii > max_i || point.jj > max_j) {
            printf("Invalid point popped from queue\n");
            return -1;
        }

        uint8_t val = get_map_data(map_data_g.basin, point.ii, point.jj, max_i, max_j);
        if (val == 0) {
            set_map_data(map_data_g.basin, point.ii, point.jj, max_i, max_j, basin_count);
            basin_counts[basin_count - 1]++;
        }

        res = queue_point(&queue, point.ii + 1, point.jj, max_i, max_j);

        if (res != QUEUE_OK) {
            printf("Unable to queue_push element: %d\n", res);
            return -1;
        }

        res = queue_point(&queue, point.ii, point.jj + 1, max_i, max_j);

        if (res != QUEUE_OK) {
            printf("Unable to queue_push element: %d\n", res);
            return -1;
        }

        res = queue_point(&queue, point.ii -1, point.jj, max_i, max_j);

        if (res != QUEUE_OK) {
            printf("Unable to queue_push element: %d\n", res);
            return -1;
        }

        res = queue_point(&queue, point.ii, point.jj - 1, max_i, max_j);

        if (res != QUEUE_OK) {
            printf("Unable to queue_push element: %d\n", res);
            return -1;
        }

        //printf("%d: (%d, %d)\n", basin_count, point.ii, point.jj);
        //print_map(map_data_g.basin, max_i, max_j);
        //printf("\n");
    }

    return 0;
}

static int find_basin(uint8_t basin, uint16_t max_i, uint16_t max_j, int16_t *ret_ii, int16_t *ret_jj) {
    int found = 0;
    int16_t ii;
    int16_t jj;

    for (ii = 0; (int16_t)ii < max_i; ii++) {
        for (jj= 0; (int16_t)jj < max_j; jj++) {
          if (get_map_data(map_data_g.basin, ii, jj, max_i, max_j) == basin) {
              found = 1;
              break;
          }
        }

        if (found) {
            break;
        }
    }

    if (found) {
        *ret_ii = ii;
        *ret_jj = jj;
        return 1;
    }
    else {
        return 0;
    }
}




static int uin8t_cmp(const void * a, const void * b) {
    return ( *(uint8_t *)a - *(uint8_t *)b );
}

#define BASIN_COUNTS 250
uint8_t basin_counts[BASIN_COUNTS] = {0};
static void part_2(uint16_t len) {
    uint16_t max_i = len;
    uint16_t max_j = map_data_g.line_width;
    uint32_t basin_size_multiplied;
    uint8_t basin_count = map_data_g.basin_count;
    int16_t basin_ii = 0;
    int16_t basin_jj = 0;

    if (basin_count - 1 >  BASIN_COUNTS) {
        printf("Too many basin counts! Need: %u\n", basin_count);
        return;
    }

    for (uint8_t basin_ndx = 1; basin_ndx < map_data_g.basin_count; basin_ndx++) {

        if (find_basin(basin_ndx, max_i, max_j, &basin_ii, &basin_jj)) {
            if (flood_fill(basin_ii, basin_jj, max_i, max_j, basin_ndx, basin_counts) < 0) {
                printf("Unable to process basin: %d\n", basin_ndx);
                return;
            }
        }
        else {
            printf("Basin %u, not found!\n", basin_ndx);
            return;
        }
    }


    qsort(basin_counts, basin_count-1, sizeof(uint8_t), uin8t_cmp);

    basin_size_multiplied = basin_counts[basin_count-2] * basin_counts[basin_count - 3] * basin_counts[basin_count - 4];

    printf("PART 2: Multiplying the size of the 3 largest basins gives: %d\n", basin_size_multiplied);
}

int day_9() {
    parse_ret_t res;
    uint16_t len;

    res = read_input_single_line("../inputs/day_9.txt", (void *)&map_data_g, MAX_WIDTH, parse_map_line, &len);

    if (res != PARSER_OK) {
        printf("Failed to parse input: %d\n", res);
        return -1;
    }

    part_1(len);
    part_2(len);


    return 0;

}