Created
December 15, 2022 10:55
-
-
Save weirddan455/8ac09a00ec291b46a50291953676a099 to your computer and use it in GitHub Desktop.
Advent of Code Day 15 Part 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment