Advent of Code Day 15 Part 2

part2.c

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

#define SCAN_BOUNDS 4000000

typedef struct Position
{
    long x;
    long y;
} Position;

typedef struct Sensor
{
    Position sensor;
    Position beacon;
} Sensor;

typedef struct SensorArray
{
    size_t size;
    size_t capacity;
    Sensor *data;
} SensorArray;

typedef struct ThreadData
{
    long lower;
    long upper;
    SensorArray *arr;
} ThreadData;

static bool is_num(char c)
{
    if (c == '-') {
        return true;
    }
    return c >= '0' && c <= '9';
}

static long read_next(char **ptr)
{
    while (!is_num(**ptr)) {
        *ptr += 1;
    }
    return strtol(*ptr, ptr, 10);
}

static void add_sensor(SensorArray *arr, Sensor *s)
{
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2;
        arr->data = realloc(arr->data, arr->capacity * sizeof(Sensor));
        if (arr->data == NULL) {
            fprintf(stderr, "realloc failed\n");
            exit(-1);
        }
    }
    arr->data[arr->size] = *s;
    arr->size += 1;
}

static void parse_input(SensorArray *arr)
{
    FILE *file = fopen("input", "r");
    if (file == NULL) {
        perror("fopen");
        exit(-1);
    }
    char buffer[256];
    while (fgets(buffer, 256, file)) {
        char *ptr = buffer;
        Sensor s;
        s.sensor.x = read_next(&ptr);
        s.sensor.y = read_next(&ptr);
        s.beacon.x = read_next(&ptr);
        s.beacon.y = read_next(&ptr);
        add_sensor(arr, &s);
    }
    fclose(file);
}

static void *find_answer(void *arg)
{
    ThreadData *thread = arg;
    SensorArray arr = *thread->arr;
    long lower = thread->lower;
    long upper = thread->upper;
    uint8_t *test = calloc(SCAN_BOUNDS + 1, 1);
    if (test == NULL) {
        fprintf(stderr, "calloc failed\n");
        exit(-1);
    }
    for (long y = lower; y < upper; y++) {
        for (size_t i = 0; i < arr.size; i++) {
            Sensor *s = arr.data + i;
            long beacon_distance = labs(s->sensor.x - s->beacon.x) + labs(s->sensor.y - s->beacon.y);
            long target_distance = labs(s->sensor.y - y);
            if (beacon_distance >= target_distance) {
                long remaining = beacon_distance - target_distance;
                for (long x = s->sensor.x - remaining; x <= s->sensor.x + remaining; x++) {
                    if (x >= 0 && x <= SCAN_BOUNDS) {
                        test[x] = 1;
                    }
                }
            }
            if (s->beacon.y == y) {
                test[s->beacon.x] = 1;
            }
        }
        for (long x = 0; x <= SCAN_BOUNDS; x++) {
            if (test[x] == 0) {
                long answer = (x * 4000000) + y;
                printf("Answer: %ld\n", answer);
                exit(0);
            }
        }
        memset(test, 0, SCAN_BOUNDS + 1);
    }
    return NULL;
}

int main(void)
{
    SensorArray arr;
    arr.size = 0;
    arr.capacity = 16;
    arr.data = malloc(arr.capacity * sizeof(Sensor));
    if (arr.data == NULL) {
        fprintf(stderr, "malloc failed\n");
        return -1;
    }
    parse_input(&arr);
    ThreadData thread_data[4];
    pthread_t thread[4];
    long slice = SCAN_BOUNDS / 4;
    for (int i = 0; i < 4; i++) {
        thread_data[i].arr = &arr;
        thread_data[i].lower = slice * i;
        thread_data[i].upper = slice * (i + 1);
    }
    thread_data[3].upper += 1;
    for (int i = 0; i < 4; i++) {
        if (pthread_create(&thread[i], NULL, find_answer, &thread_data[i]) != 0) {
            fprintf(stderr, "pthread_create failed\n");
            return -1;
        }
    }
    for (int i = 0 ; i < 4; i++) {
        pthread_join(thread[i], NULL);
    }
    return 0;
}