AoC18/day6p1/main.c

#include <stdio.h>

#include <glib.h>

struct coord {
    int x;
    int y;
};

struct rect {
    int x;
    int y;
    int w;
    int h;
};

struct coord *parse_coords(const char *fname, unsigned *len)
{
    FILE *f = fopen(fname, "r");
    if (!f) {
        perror(fname);
        return NULL;
    }

    GArray *array = g_array_new(FALSE, FALSE, sizeof(struct coord));
    *len = 0;

    char *line = NULL;
    size_t line_len = 0;
    while (getline(&line, &line_len, f) != -1) {
        struct coord coord = {0};
        if (sscanf(line, "%d, %d", &coord.x, &coord.y) != 2) continue;
        g_array_append_val(array, coord);
        (*len)++;
    }

    free(line);
    fclose(f);
    struct coord *res = (struct coord *)g_array_free(array, FALSE);
    return res;
}

struct rect find_limit(struct coord *coords, unsigned len)
{
    struct rect rect = {0};
    if (!len) return rect;

    int xmax = rect.x = coords->x;
    int ymax = rect.y = coords->y;

    for (struct coord *coord = coords + 1; coord < coords + len; coord++) {
        if (coord->x < rect.x) rect.x = coord->x;
        if (coord->y < rect.y) rect.y = coord->y;
        if (coord->x > xmax) xmax = coord->x;
        if (coord->y > ymax) ymax = coord->y;
    }

    rect.w = xmax - rect.x + 1;
    rect.h = ymax - rect.y + 1;

    return rect;
}

unsigned *count_influence(struct coord *coords, unsigned coords_len, struct rect area)
{
    unsigned *tally = g_new0(unsigned, coords_len);

    for (int y = area.y; y < area.y + area.h; y++) {
        for (int x = area.x; x < area.x + area.w; x++) {
            unsigned tile = 0;
            unsigned shortest = area.h * area.w;

            // Find the point with the shortest distance
            for (unsigned i = 0; i < coords_len && shortest; i++) {
                unsigned dist = abs(coords[i].x - x) + abs(coords[i].y - y);
                if (dist < shortest) {
                    shortest = dist;
                    tile = i + 1;
                }
            }

            if (!tile) continue;

            // Look for another point with the same distance
            for (unsigned i = 0; i < coords_len && shortest; i++) {
                unsigned dist = abs(coords[i].x - x) + abs(coords[i].y - y);
                if (tile - 1 == i) continue;
                if (dist == shortest) {
                    tile = 0;
                    break;
                }
            }

            //printf("%c", tile ? 'a' + tile - 1 : '.');
            if (!tile) continue;
            if (tally[tile - 1] < UINT_MAX) tally[tile - 1]++;
        }
        //printf("\n");
    }

    return tally;
}

int main()
{
    unsigned coords_len;
    struct coord *coords = parse_coords("input", &coords_len);
    if (!coords) return 1;

    /*
     * NOTE: This method I'm using to figure our the biggest non-infinite
     *   influence range for a coordinate is suboptimal and won't work for all inputs.
     * I could try to figure out how to calcluate it properly or a better algorithm
     *   than checking literally each tile in a defined area, but I'm too lazy.
     * If it works for my input it's fine ;)
     */

    struct rect limit = find_limit(coords, coords_len);
    printf("%d,%d\n%d,%d\n",
            limit.x, limit.y,
            limit.x + limit.w - 1, limit.y + limit.h - 1);

    unsigned *tally = count_influence(coords, coords_len, limit);

    // Disqualify any coords that don't compete with anything.
    for (unsigned a = 0; a < coords_len; a++) {
        int north = 0;
        int south = 0;
        int east = 0;
        int west = 0;
        for (unsigned b = 0; b < coords_len; b++) {
            if (coords[b].y < coords[a].y) north = 1;
            if (coords[b].y > coords[a].y) south = 1;
            if (coords[b].x > coords[a].x) east = 1;
            if (coords[b].x < coords[a].x) west = 1;
        }
        if (!north || !south || !east || !west) tally[a] = 0;
    }

    // Find the largest
    unsigned largest = 0;
    for (unsigned *i = tally; i < tally + coords_len; i++) {
        if (*i > largest) largest = *i;
    }

    printf("Largest: %u\n", largest);

    g_free(tally);
    g_free(coords);
    return 0;
}