AoC18/day18p1/main.c

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

struct size2d {
    unsigned w;
    unsigned h;
};

struct buffer {
    void *data;
    size_t len;
    size_t alloc;
    unsigned element;
};

void *xrealloc(void *ptr, size_t size)
{
    void *res = realloc(ptr, size);
    if (!res) {
        perror("realloc");
        exit(1);
    }
    return res;
}

struct buffer buffer_alloc(const unsigned element_size)
{
    struct buffer buffer;
    buffer.len = 0;
    buffer.alloc = 0x10;
    buffer.element = element_size;
    buffer.data = xrealloc(NULL, buffer.alloc * buffer.element);
    return buffer;
}

void buffer_append(struct buffer *buffer, void *data)
{
    if (buffer->alloc <= buffer->len) {
        buffer->alloc *= 2;
        buffer->data = xrealloc(buffer->data, buffer->alloc * buffer->element);
    }
    memcpy((char *)buffer->data + buffer->len++ * buffer->element, data, buffer->element);
}

char *parse_acres(const char *fname, struct size2d *size)
{
    FILE *f = fopen(fname, "r");
    if (!f) {
        perror(fname);
        return NULL;
    }

    struct buffer buffer = buffer_alloc(sizeof(char));
    size->w = 0;
    size->h = 0;

    unsigned width = 0;
    int c;

    flockfile(f);
    while ((c = getc_unlocked(f)) != EOF) {
        if (c == '\n') {
            if (!size->w) {
                size->w = width;
            } else {
                if (size->w != width) {
                    fprintf(stderr, "ERROR: Not each line has the same width\n");
                    goto error;
                }
            }
            width = 0;
            size->h++;
            continue;
        }

        if (c != '.' && c != '|' && c != '#') {
            fprintf(stderr, "ERROR: Unknown character: '%c'\n", c);
            goto error;
        }

        buffer_append(&buffer, &c);
        width++;
    }
    funlockfile(f);
    fclose(f);

    return realloc(buffer.data, buffer.len);

error:
    funlockfile(f);
    fclose(f);
    free(buffer.data);
    return NULL;
}

void advance_frame(char *acres, char *next, const struct size2d size)
{
    for (unsigned y = 0; y < size.h; y++) {
        for (unsigned x = 0; x < size.w; x++) {
            char *a = next + y * size.w + x;

            char surrounding[8] = {'\0'};
            if (y > 0) surrounding[0] = acres[(y - 1) * size.w + x];
            if (x > 0) surrounding[1] = acres[y * size.w + (x - 1)];
            if (y + 1 < size.h) surrounding[2] = acres[(y + 1) * size.w + x];
            if (x + 1 < size.w) surrounding[3] = acres[y * size.w + (x + 1)];
            if (y > 0 && x + 1 < size.w)
                surrounding[4] = acres[(y - 1) * size.w + (x + 1)];
            if (y > 0 && x > 0)
                surrounding[5] = acres[(y - 1) * size.w + (x - 1)];
            if (y + 1 < size.h && x > 0)
                surrounding[6] = acres[(y + 1) * size.w + (x - 1)];
            if (y + 1 < size.h && x + 1 < size.w)
                surrounding[7] = acres[(y + 1) * size.w + (x + 1)];

            unsigned tally = 0;
            unsigned tally2 = 0;
            char new = 0;

            switch (*a) {
            case '.':
            case '|':
                new = (*a == '.' ? '|' : '#');
                for (char *c = surrounding; c < surrounding + 8; c++) {
                    if (*c == new) tally++;
                }
                if (tally >= 3) *a = new;
                break;
            case '#':
                for (char *c = surrounding; c < surrounding + 8; c++) {
                    if (*c == '#') tally++;
                    if (*c == '|') tally2++;
                }
                if (!(tally >= 1 && tally2 >= 1)) *a = '.';
                break;
            }
        }
    }
}

int render_bitmap(const char *fname, const char *acres, const struct size2d size)
{
    FILE *f = fopen(fname, "w");
    if (!f) {
        perror(fname);
        return 1;
    }

    flockfile(f);
    fprintf(f, "P6\n%u %u\n255\n", size.w, size.h);

    for (unsigned y = 0; y < size.h; y++) {
        for (unsigned x = 0; x < size.w; x++) {
            char color[3] = {255};

            switch (acres[y * size.w + x]) {
            case '.':
                // Yellow
                color[0] = 205;
                color[1] = 255;
                color[2] = 110;
                break;
            case '|':
                // Green
                color[0] = 0;
                color[1] = 255;
                color[2] = 0;
                break;
            case '#':
                // Brown
                color[0] = 192;
                color[1] = 125;
                color[2] = 0;
                break;
            }

            fwrite_unlocked(color, 3, 1, f);
        }
    }

    funlockfile(f);
    fclose(f);
    return 0;
}

uint32_t adler32(const unsigned char *data, const size_t len)
{
    // Shamelessly copied from wikipedia...
    uint32_t a = 1, b = 0;

    for (size_t index = 0; index < len; index++) {
        a = (a + data[index]) % 65521;
        b = (b + a) % 65521;
    }

    return (b << 16) | a;
}

int main(int argc, char *argv[])
{
    struct size2d size;
    char *acres = parse_acres("input", &size);
    if (!acres) return 1;

    unsigned minutes = 10;
    int render = 0;
    if (argc > 1) minutes = strtol(argv[1], NULL, 0);
    if (argc > 2 && strcmp(argv[2], "-render") == 0) render = 1;

    char *next = xrealloc(NULL, size.w * size.h);
    memcpy(next, acres, size.w * size.h);

    struct buffer hashes = buffer_alloc(sizeof(uint32_t));
    unsigned loop_found = 0;
    unsigned loop_iterlen = 0;

    char *fname = NULL;
    clock_t start = clock();
    for (unsigned i = 0; i <= minutes; i++) {
        if (i != 0) {
            advance_frame(acres, next, size);
            memcpy(acres, next, size.w * size.h);

            if (!loop_found) {
                uint32_t hash = adler32((unsigned char *)acres, size.w * size.h);
                for (unsigned i = 0; i < hashes.len; i++) {
                    uint32_t check = ((uint32_t *)hashes.data)[i];
                    if (check == hash) {
                        loop_found = i + 1;
                        break;
                    }
                }

                if (loop_found) {
                    loop_iterlen = (i - loop_found);
                    minutes = (minutes - i) % loop_iterlen + i;
                } else {
                    buffer_append(&hashes, &hash);
                }
            }

            if (i % 10000 == 0) {
                double framespers = 10000 / ((double)(clock() - start) / CLOCKS_PER_SEC);
                unsigned eta = (double)(minutes - i) / framespers;
                fprintf(stderr, "Progress: %.2f%% (speed: %.2f frames/s, ETA: %u:%u:%u)\n",
                        (double)i / minutes * 100, framespers,
                        eta / 60 / 60, (eta / 60) % 60, eta % 60);
                start = clock();
            }
        }

        if (render) {
            if (asprintf(&fname, "out/frame%04u.ppm", i) == -1) {
                perror("asprintf");
                break;
            }
            if (render_bitmap(fname, acres, size)) break;
            free(fname);
        }
    }

    unsigned wood = 0;
    unsigned lumber = 0;
    for (unsigned y = 0; y < size.h; y++) {
        for (unsigned x = 0; x < size.w; x++) {
            char c = acres[y * size.w + x];
            if (c == '|') wood++;
            if (c == '#') lumber++;
        }
    }

    if (loop_found) printf("Loop starting frame: %u (length %u)\n", loop_found, loop_iterlen);
    printf("Resource value: %u\n", wood * lumber);

    free(hashes.data);
    free(next);
    free(acres);
    return 0;
}