advent-of-code-2023/day_5.c

//
// Created by lennart on 12/7/23.
//

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <ctype.h>
#include "input_handler.h"

//region types
#define LIST_NAME IntList
#define LIST_PREFIX ilist
#define ELEMENT_TYPE unsigned int
#include "list.h"

typedef struct {
    uint32_t source;
    uint32_t destination;
    uint32_t length;
} Range;

#define LIST_NAME RangeList
#define LIST_PREFIX rlist
#define ELEMENT_TYPE Range
#include "list.h"

typedef struct {
    IntList *seeds;
    RangeList *seed_to_soil;
    RangeList *soil_to_fertilizer;
    RangeList *fertilizer_to_water;
    RangeList *water_to_light;
    RangeList *light_to_temperature;
    RangeList *temperature_to_humidity;
    RangeList *humidity_to_location;
} Almanac;
//endregion types

// Functions
Almanac* load_almanac(FILE *f);
RangeList* load_map(FILE *f, const char *name);
void almanac_free(Almanac *almanac);
uint32_t nearest_location_in_range(RangeList **maps, int map_count, uint32_t range_start, uint32_t range_end);
static int compare_range(const Range *a, const Range *b);

// Global state (used to avoid having to allocate new memory on every iteration)
RangeList *range_list_buffer;

int main() {
    FILE *f = fopen("day_5.txt", "r");
    if(f == NULL) {
        fprintf(stderr, "Missing input file!\n");
        exit(1);
    }
    Almanac *almanac = load_almanac(f);
    range_list_buffer = rlist_create(16);

    // Part 1 - Iterate over each seed and transform number using first matching range for each map
    uint32_t min_location = UINT32_MAX;
    for(int i = 0; i < almanac->seeds->length; i++) {
        uint32_t source = almanac->seeds->data[i];

        for(int j = 0; j < 7; j++) {
            RangeList ranges = * ((RangeList**) almanac)[j + 1];
            for(int k = 0; k < ranges.length; k++) {
                Range range = ranges.data[k];
                if(source >= range.source && source < range.source + range.length) {
                    source = source - range.source + range.destination;
                    break;
                }
            }
        }

        if(source < min_location) {
            min_location = source;
        }
    }
    printf("Result #1: %u\n", min_location);

    // Part 2
    min_location = UINT32_MAX;
    for(int i = 0; i < almanac->seeds->length; i += 2) {
        uint32_t min = almanac->seeds->data[i];
        uint32_t max = min + almanac->seeds->data[i + 1];

        RangeList **maps = &((RangeList**) almanac)[1];
        min_location = MIN(min_location, nearest_location_in_range(maps, 7, min, max));
    }
    printf("Result #2: %u\n", min_location);

    rlist_free(range_list_buffer);
    almanac_free(almanac);
    fclose(f);
    return 0;
}

uint32_t nearest_location_in_range(RangeList **maps, int map_count, uint32_t range_start, uint32_t range_end) {
    RangeList *map = maps[0];
    if(__glibc_unlikely(map->length == 0)) return range_start;

    RangeList *temp_ranges = range_list_buffer;
    rlist_clear(temp_ranges);

    uint32_t cursor = range_start;
    for(int i = 0; i < map->length; i++) {
        Range input_range = map->data[i];
        if(input_range.source + input_range.length <= range_start) {
            continue; // input range before current range - skip
        }
        if(input_range.source >= range_end) {
            break; // input range after current range - finish
        }

        // Add unmapped range
        if(cursor < input_range.source) {
            Range new_range;
            new_range.source = cursor;
            new_range.destination = cursor;
            new_range.length = new_range.source - cursor;
            rlist_add(temp_ranges, new_range);
            cursor = input_range.source;
        }

        // Add mapped range
        uint32_t mapped_end = MIN(input_range.source + input_range.length, range_end);
        Range mapped_range;
        mapped_range.length = mapped_end - cursor;
        mapped_range.source = cursor;
        mapped_range.destination = input_range.destination + cursor - input_range.source;
        rlist_add(temp_ranges, mapped_range);
        cursor = MAX(cursor, mapped_range.source + mapped_range.length);
    }
    // Add final unmapped range
    if(cursor < range_end) {
        Range new_range;
        new_range.source = cursor;
        new_range.destination = cursor;
        new_range.length = range_end - cursor;
        rlist_add(temp_ranges, new_range);
    }

    // Copy new ranges
    uint num_ranges = temp_ranges->length;
    Range ranges[num_ranges];
    memcpy(&ranges[0], temp_ranges->data, num_ranges * sizeof(Range));

    // Find nearest
    uint32_t nearest = UINT32_MAX;
    if(map_count > 1) {
        for(int i = 0; i < num_ranges; i++) {
            Range range = ranges[i];
            uint32_t next_nearest = nearest_location_in_range(
                    &maps[1], map_count - 1,
                    range.destination, range.destination + range.length);
            nearest = MIN(nearest, next_nearest);
        }
    } else {
        for(int i = 0; i < num_ranges; i++) {
            Range range = ranges[i];
            nearest = MIN(nearest, range.destination);
        }
    }

    return nearest;
}

Almanac* load_almanac(FILE *f) {
    Almanac *almanac = malloc(sizeof (Almanac));
    char *buffer = NULL;
    int bufferLen;

    // Load the seeds
    read_line(f, &buffer, &bufferLen);
    assert(strlen(buffer) > 7 && strncmp(buffer, "seeds: ", 7) == 0); // expect name prefix line
    almanac->seeds = ilist_create(16);
    char *cursor = &buffer[7];
    while(*cursor != 0) {
        if(!isdigit(*cursor) && cursor++) continue;
        uint32_t seed = (uint32_t) strtoul(cursor, &cursor, 10);
        ilist_add(almanac->seeds, seed);
    }
    read_line(f, &buffer, &bufferLen);
    assert(strcmp(buffer, "") == 0); // expect empty line at end

    almanac->seed_to_soil = load_map(f, "seed-to-soil");
    almanac->soil_to_fertilizer = load_map(f, "soil-to-fertilizer");
    almanac->fertilizer_to_water = load_map(f, "fertilizer-to-water");
    almanac->water_to_light = load_map(f, "water-to-light");
    almanac->light_to_temperature = load_map(f, "light-to-temperature");
    almanac->temperature_to_humidity = load_map(f, "temperature-to-humidity");
    almanac->humidity_to_location = load_map(f, "humidity-to-location");

    free(buffer);
    return almanac;
}

static int compare_range(const Range *a, const Range *b) {
    return a->source > b->source;
}

RangeList* load_map(FILE *f, const char *name) {
    RangeList *list = rlist_create(16);
    char *buffer = NULL;
    int bufferLen;

    read_line(f, &buffer, &bufferLen);
    assert(strncmp(buffer, name, strlen(name)) == 0);
    while(!feof(f) && strcmp(read_line(f, &buffer, &bufferLen), "") != 0) {
        Range range;
        sscanf(buffer, "%u %u %u", &range.destination, &range.source, &range.length);
        rlist_add(list, range);
    }

    qsort(list->data, list->length, sizeof(Range), (__compar_fn_t) compare_range);
    free(buffer);
    return list;
}

void almanac_free(Almanac *almanac) {
    ilist_free(almanac->seeds);
    rlist_free(almanac->seed_to_soil);
    rlist_free(almanac->soil_to_fertilizer);
    rlist_free(almanac->fertilizer_to_water);
    rlist_free(almanac->water_to_light);
    rlist_free(almanac->light_to_temperature);
    rlist_free(almanac->temperature_to_humidity);
    rlist_free(almanac->humidity_to_location);
    free(almanac);
}