adventofcode2023/day5/c/day5.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <omp.h>

#define LINE_MAX_LENGTH 512
#define MAX_RANGE_PER_MAPPING 64
#define MAX_MAPPINGS 64
#define MAX_SEEDS 128
#define NUM_0_CHARCODE 48
#define NUM_9_CHARCODE NUM_0_CHARCODE + 9

const char* resources[] = {
    "seed",
    "soil",
    "fertilizer",
    "water",
    "light",
    "temperature",
    "humidity",
    "location"
};

#define RESOURCES_LEN (sizeof(resources) / sizeof(resources[0]))

struct mapping {
    unsigned long source;
    unsigned long destination;
    unsigned long mappings[MAX_RANGE_PER_MAPPING][3];
    int mapping_num;
};

struct mapping* create_mapping(unsigned long src, unsigned long dst);

int main() {
    char *p, *buf, c;
    int firstline = 1, seed_num = 0;
    unsigned long seeds[MAX_SEEDS];

    struct mapping **mappings;
    int mappings_num = 0;

    mappings = (struct mapping**)malloc(MAX_MAPPINGS * sizeof(struct mapping*));

    buf = (char *)malloc(LINE_MAX_LENGTH);
    memset(buf, 0, LINE_MAX_LENGTH);
    p = buf;

    int src = 0, dst = 0;
    struct mapping *curr;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c == '\n') {
            if (firstline) {
                if (buf[0] == '\n') {
                    firstline = 0;
                    memset(buf, 0, LINE_MAX_LENGTH);
                    p = buf;
                    continue;
                }

                p = buf;
                while (*p < NUM_0_CHARCODE || *p > NUM_9_CHARCODE) p++;
                while (*p != '\0') {
                    sscanf(p, "%lu", &seeds[seed_num]);
                    seed_num++;

                    while (*p != ' ' && *p != '\n') p++;
                    p++;
                }
                memset(buf, 0, LINE_MAX_LENGTH);
                p = buf;
                continue;
            }

            if (src == dst) {
                char tmp1[64], tmp2[64];
                memset(tmp1, 0 , 64);
                memset(tmp2, 0 , 64);
                sscanf(buf, "%[^-]-to-%s map", tmp1, tmp2);

                for (unsigned long i = 0; i < RESOURCES_LEN; i++) {
                    if (strcmp(tmp1, resources[i]) == 0) {
                        src = i;
                    }
                    if (strcmp(tmp2, resources[i]) == 0) {
                        dst = i;
                    }
                }
                curr = create_mapping(src, dst);
            } else if (buf[0] == '\n') {
                mappings[mappings_num] = curr;
                mappings_num++;
                src = dst = 0;
            } else {
                unsigned long src_start, dst_start, range;
                sscanf(buf, "%lu %lu %lu", &dst_start, &src_start, &range); 
                curr->mappings[curr->mapping_num][0] = dst_start;
                curr->mappings[curr->mapping_num][1] = src_start;
                curr->mappings[curr->mapping_num][2] = range;
                curr->mapping_num++;
            }

            memset(buf, 0, LINE_MAX_LENGTH);
            p = buf;
        }
    }
    mappings[mappings_num] = curr;
    mappings_num++;

    // Part 1

    unsigned long part1 = ULONG_MAX;
    int location_idx = 7;
    
    for (int i = 0; i < seed_num; i++) {
        int cur_resource = 0;
        unsigned long cur_value = seeds[i];
        while (cur_resource != location_idx) {
            for (int j = 0; j < mappings_num; j++) {
                if (cur_resource != mappings[j]->source) {
                    continue;
                }

                for (int k = 0; k < mappings[j]->mapping_num; k++) {
                    if (cur_value >= mappings[j]->mappings[k][1] && cur_value < mappings[j]->mappings[k][1] + mappings[j]->mappings[k][2]) {
                        cur_value = mappings[j]->mappings[k][0] + (cur_value - mappings[j]->mappings[k][1]);
                        break;
                    }
                }

                cur_resource = mappings[j]->destination;
            }
        }

        if (part1 > cur_value) {
            part1 = cur_value;
        }
    }

    printf("%lu\n", part1);

    // Part 2

    unsigned long part2 = ULONG_MAX;

    // I know it could be done more efficiently than checking every single number but it only runs
    // for about an hour an a single core so if I use all 12 threads in my machine it only takes 5 mins
    for (int i = 0; i < seed_num; i+=2) {
#pragma omp parallel for
        for (unsigned long s = seeds[i]; s < seeds[i] + seeds[i+1]; s++) {
            int cur_resource = 0;
            unsigned long cur_value = s;
            while (cur_resource != location_idx) {
                for (int j = 0; j < mappings_num; j++) {
                    if (cur_resource != mappings[j]->source) {
                        continue;
                    }

                    for (int k = 0; k < mappings[j]->mapping_num; k++) {
                        if (cur_value >= mappings[j]->mappings[k][1] && cur_value < mappings[j]->mappings[k][1] + mappings[j]->mappings[k][2]) {
                            cur_value = mappings[j]->mappings[k][0] + (cur_value - mappings[j]->mappings[k][1]);
                            break;
                        }
                    }

                    cur_resource = mappings[j]->destination;
                }
            }

#pragma omp critical
            if (part2 > cur_value) {
                part2 = cur_value;
            }
        }
    }

    printf("%lu\n", part2);

    free(buf);
    for (int i = 0; i < mappings_num; i++) {
        free(mappings[i]);
    }
    free(mappings);
}

struct mapping* create_mapping(unsigned long src, unsigned long dst) {
    struct mapping *mapping;
    mapping = (struct mapping*)malloc(sizeof(struct mapping));
    memset(mapping, 0, sizeof(struct mapping));
    mapping->source = src;
    mapping->destination = dst;
    return mapping;
}