advent2023

puzzle.c (6188B)

---

 #define _DEFAULT_SOURCE
 
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <assert.h>
 #include <stdbool.h>
 #include <inttypes.h>
 #include <stdatomic.h>
 #include <threads.h>
 
 #define STR_LEN 2048
 
 bool is_digit(char b) {
 	return b>='0' && b<='9';
 }
 
 typedef struct Number {
 	uint64_t value;
 	struct Number *next;
 } Number;
 Number * make_number(uint64_t value) {
 	Number *n = malloc(sizeof(Number));
 	memset(n, 0, sizeof(Number));
 	n->value = value;
 	return n;
 }
 void print_numbers(Number *first) {
 	Number *n = first;
 	while (n!=NULL) {
 		printf("%" PRIu64 ", ", n->value);
 		n = n->next;
 	}
 	printf("\n");
 }
 
 typedef struct Range {
 	int id;
 	char *name;
 	uint64_t dst[2];
 	uint64_t src[2];
 	struct Range *next;
 } Range;
 // I really should make a macro for that
 Range * make_range() {
 	Range *r = malloc(sizeof(Range));
 	memset(r, 0, sizeof(Range));
 	return r;
 }
 void print_ranges(Range *first) {
 	Range *r = first;
 	while (r!=NULL) {
 		printf("range %d: [%" PRIu64 " -> %" PRIu64 ") -> [%" PRIu64 " -> %" PRIu64 ")\n", r->id, r->src[0], r->src[1], r->dst[0], r->dst[1]);
 		r = r->next;
 	}
 }
 
 uint64_t calc_loc(Range *ranges, uint64_t seed) {
 	Range *r = ranges;
 	int range_id = 1; // starting range
 	uint64_t needle = seed;
 	while (r!=NULL) {
 		if (r->id == range_id) {
 			//printf("(%d) checking range %d for %" PRIu64 "...\n", range_id, r->id, needle);
 			if (needle >= r->src[0] && needle < r->src[1]) {
 				uint64_t next = r->dst[0] + (needle - r->src[0]);
 				needle = next;
 				++range_id;
 			}
 		}
 		if (r->id <= range_id) {
 			r = r->next;
 		} else {
 			++range_id;
 			r = ranges; // rewind and repeat
 		}
 	}
 	return needle;
 }
 
 void fill_range(Range *r, uint64_t dst_start, uint64_t src_start, uint64_t len) {
 	r->src[0] = src_start;
 	r->src[1] = src_start + len; // <, top border not inclusive
 	r->dst[0] = dst_start;
 	r->dst[1] = dst_start + len;
 }
 
 typedef struct RunArgs {
 	Range *ranges;
 	uint64_t seed1;
 	uint64_t seed2;
 	mtx_t *mutex;
 	long long *result2;
 } RunArgs;
 
 int run_calc(void *a) {
 	RunArgs *ra = (RunArgs *)a;
 	uint64_t seed1 = ra->seed1;
 	uint64_t seed2 = ra->seed2;
 	Range *ranges = ra->ranges;
 	uint64_t res2 = 0;
 	//printf("seed from %" PRIu64 " of count %" PRIu64 "\n", seed1, seed2);
 
 	// brain damage
 	for (uint64_t i=seed1; i<seed1+seed2; ++i) {
 		uint64_t loc = calc_loc(ranges, i);
 		if (res2==0||loc<res2) res2 = loc;
 	}
 	//printf("res2: %" PRIu64 "\n", res2);
 	if (mtx_lock(ra->mutex)!=thrd_success) {
 		printf("mutex lock error\n");
 		//thrd_exit(EXIT_FAILURE);
 	}
 	if (*ra->result2==-1||res2<(uint64_t)*ra->result2) *ra->result2 = res2;
 	if (mtx_unlock(ra->mutex)!=thrd_success) {
 		printf("mutex unlock error\n");
 		//thrd_exit(EXIT_FAILURE);
 	}
 	return 0;
 }
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
 	if (infile == NULL) {
 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
 		return;
 	}
 
 	char buf[STR_LEN] = {0};
 	unsigned int line_num = 0;
 
 	Number *seeds = NULL;
 	Number *seeds_last = NULL;
 
 	int range_id = 0;
 	Range *ranges = NULL;
 	Range *ranges_last = NULL;
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
 		int len = strlen(buf);
 		if (line_num==0) { // first line is always about seeds
 			uint64_t seed = 0;
 			for (int i=0; i<len; ++i) {
 				if (is_digit(buf[i])) {
 					seed = seed*10 + buf[i] - '0';
 				} else if ((buf[i]==' '||buf[i]=='\n')&&seed!=0) { //@todo not portable to windows and other crap
 					Number *s = make_number(seed);
 					if (seeds==NULL) seeds = s;
 					if (seeds_last!=NULL) seeds_last->next = s;
 					seeds_last = s;
 					seed = 0;
 				}
 			}
 			//printf("seeds: ");
 			//print_numbers(seeds);
 		} else if (len>1) { // to skip empty lines
 			if (is_digit(buf[0])) { // fill ranges
 				Range *r = make_range();
 				uint64_t dst_start, src_start, range_len;
 				int res = sscanf(buf, "%" PRIu64 " %" PRIu64 " %" PRIu64, &dst_start, &src_start, &range_len);
 				assert(res==3);
 				//printf("range %d, dst: %" PRIu64 ", src: %" PRIu64 ", len: %" PRIu64 "\n", range_id, dst_start, src_start, range_len);
 				fill_range(r, dst_start, src_start, range_len);
 				r->id = range_id;
 
 				// no seriously I should make a struct+functions or macro with that
 				if (ranges==NULL) ranges = r;
 				if (ranges_last!=NULL) ranges_last->next = r;
 				ranges_last = r;
 			} else { // create new range id
 				//printf("new range: %s", buf);
 				++range_id;
 			}
 		}
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
 	//print_ranges(ranges);
 	Number *s1 = seeds;
 	while (s1!=NULL) {
 		uint64_t loc = calc_loc(ranges, s1->value);
 		if (*result1==-1||loc<(uint64_t)*result1) *result1 = loc;
 		//printf("seed %" PRIu64 " location: %" PRIu64 "\n", s1->value, loc);
 		s1 = s1->next;
 	}
 
 	Number *s2 = seeds;
 	thrd_t threads[10] = {0};
 	int thread_id = 0;
 	static mtx_t mutex;
 	if (mtx_init(&mutex, mtx_plain)!=thrd_success) {
 		printf("error initing mutex\n");
 		thrd_exit(EXIT_FAILURE);
 	}
 	while (s2!=NULL) {
 		uint64_t seed1 = s2->value;
 		uint64_t seed2 = 0;
 		if (s2->next!=NULL) {
 			seed2 = s2->next->value;
 			s2 = s2->next->next;
 		}
 		//printf("seed from %" PRIu64 " of count %" PRIu64 "\n", seed1, seed2);
 
 		// brain damage
 		/*for (uint64_t i=seed1; i<seed1+seed2; ++i) {
 			uint64_t loc = calc_loc(ranges, i);
 			if (*result2==-1||loc<(uint64_t)*result2) *result2 = loc;
 		}*/
 		RunArgs *a = malloc(sizeof(RunArgs));
 		a->ranges = ranges;
 		a->seed1 = seed1;
 		a->seed2 = seed2;
 		a->result2 = result2;
 		a->mutex = &mutex;
 		int t_res=thrd_create(&threads[thread_id], run_calc, (void *)a);
 		if (t_res!=thrd_success) {
 			printf("thrd_create %d error %d\n", thread_id, t_res);
 		}
 		++thread_id;
 	}
 
 	for (int i=0; i<thread_id; ++i) {
 		//printf("waiting for t %d\n", i);
 		int t_out = 0;
 		int t_res = thrd_join(threads[i], &t_out);
 		if (t_res!=thrd_success) {
 			printf("error joining thread %d: %d (out %d)\n", i, t_res, t_out);
 			//thrd_exit(EXIT_FAILURE);
 		}
 		//printf("end waiting for t %d\n", i);
 	}
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 
 	//printf("res1: %lld\n", *result1);
 	//printf("res2: %lld\n", *result2);
 
 	//thrd_exit(EXIT_SUCCESS);
 }