advent2023

Advent of Code 2023 solutions
git clone git://bsandro.tech/advent2023
Log | Files | Refs | LICENSE

puzzle.c (6188B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <limits.h>
      4 #include <stdio.h>
      5 #include <stdlib.h>
      6 #include <errno.h>
      7 #include <string.h>
      8 #include <strings.h>
      9 #include <assert.h>
     10 #include <stdbool.h>
     11 #include <inttypes.h>
     12 #include <stdatomic.h>
     13 #include <threads.h>
     14 
     15 #define STR_LEN 2048
     16 
     17 bool is_digit(char b) {
     18 	return b>='0' && b<='9';
     19 }
     20 
     21 typedef struct Number {
     22 	uint64_t value;
     23 	struct Number *next;
     24 } Number;
     25 Number * make_number(uint64_t value) {
     26 	Number *n = malloc(sizeof(Number));
     27 	memset(n, 0, sizeof(Number));
     28 	n->value = value;
     29 	return n;
     30 }
     31 void print_numbers(Number *first) {
     32 	Number *n = first;
     33 	while (n!=NULL) {
     34 		printf("%" PRIu64 ", ", n->value);
     35 		n = n->next;
     36 	}
     37 	printf("\n");
     38 }
     39 
     40 typedef struct Range {
     41 	int id;
     42 	char *name;
     43 	uint64_t dst[2];
     44 	uint64_t src[2];
     45 	struct Range *next;
     46 } Range;
     47 // I really should make a macro for that
     48 Range * make_range() {
     49 	Range *r = malloc(sizeof(Range));
     50 	memset(r, 0, sizeof(Range));
     51 	return r;
     52 }
     53 void print_ranges(Range *first) {
     54 	Range *r = first;
     55 	while (r!=NULL) {
     56 		printf("range %d: [%" PRIu64 " -> %" PRIu64 ") -> [%" PRIu64 " -> %" PRIu64 ")\n", r->id, r->src[0], r->src[1], r->dst[0], r->dst[1]);
     57 		r = r->next;
     58 	}
     59 }
     60 
     61 uint64_t calc_loc(Range *ranges, uint64_t seed) {
     62 	Range *r = ranges;
     63 	int range_id = 1; // starting range
     64 	uint64_t needle = seed;
     65 	while (r!=NULL) {
     66 		if (r->id == range_id) {
     67 			//printf("(%d) checking range %d for %" PRIu64 "...\n", range_id, r->id, needle);
     68 			if (needle >= r->src[0] && needle < r->src[1]) {
     69 				uint64_t next = r->dst[0] + (needle - r->src[0]);
     70 				needle = next;
     71 				++range_id;
     72 			}
     73 		}
     74 		if (r->id <= range_id) {
     75 			r = r->next;
     76 		} else {
     77 			++range_id;
     78 			r = ranges; // rewind and repeat
     79 		}
     80 	}
     81 	return needle;
     82 }
     83 
     84 void fill_range(Range *r, uint64_t dst_start, uint64_t src_start, uint64_t len) {
     85 	r->src[0] = src_start;
     86 	r->src[1] = src_start + len; // <, top border not inclusive
     87 	r->dst[0] = dst_start;
     88 	r->dst[1] = dst_start + len;
     89 }
     90 
     91 typedef struct RunArgs {
     92 	Range *ranges;
     93 	uint64_t seed1;
     94 	uint64_t seed2;
     95 	mtx_t *mutex;
     96 	long long *result2;
     97 } RunArgs;
     98 
     99 int run_calc(void *a) {
    100 	RunArgs *ra = (RunArgs *)a;
    101 	uint64_t seed1 = ra->seed1;
    102 	uint64_t seed2 = ra->seed2;
    103 	Range *ranges = ra->ranges;
    104 	uint64_t res2 = 0;
    105 	//printf("seed from %" PRIu64 " of count %" PRIu64 "\n", seed1, seed2);
    106 
    107 	// brain damage
    108 	for (uint64_t i=seed1; i<seed1+seed2; ++i) {
    109 		uint64_t loc = calc_loc(ranges, i);
    110 		if (res2==0||loc<res2) res2 = loc;
    111 	}
    112 	//printf("res2: %" PRIu64 "\n", res2);
    113 	if (mtx_lock(ra->mutex)!=thrd_success) {
    114 		printf("mutex lock error\n");
    115 		//thrd_exit(EXIT_FAILURE);
    116 	}
    117 	if (*ra->result2==-1||res2<(uint64_t)*ra->result2) *ra->result2 = res2;
    118 	if (mtx_unlock(ra->mutex)!=thrd_success) {
    119 		printf("mutex unlock error\n");
    120 		//thrd_exit(EXIT_FAILURE);
    121 	}
    122 	return 0;
    123 }
    124 
    125 void puzzle(const char *filename, long long *result1, long long *result2) {
    126 	FILE *infile = fopen(filename, "r");
    127 	if (infile == NULL) {
    128 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
    129 		return;
    130 	}
    131 
    132 	char buf[STR_LEN] = {0};
    133 	unsigned int line_num = 0;
    134 
    135 	Number *seeds = NULL;
    136 	Number *seeds_last = NULL;
    137 
    138 	int range_id = 0;
    139 	Range *ranges = NULL;
    140 	Range *ranges_last = NULL;
    141 
    142 	while (fgets(buf, STR_LEN, infile) != NULL) {
    143 		int len = strlen(buf);
    144 		if (line_num==0) { // first line is always about seeds
    145 			uint64_t seed = 0;
    146 			for (int i=0; i<len; ++i) {
    147 				if (is_digit(buf[i])) {
    148 					seed = seed*10 + buf[i] - '0';
    149 				} else if ((buf[i]==' '||buf[i]=='\n')&&seed!=0) { //@todo not portable to windows and other crap
    150 					Number *s = make_number(seed);
    151 					if (seeds==NULL) seeds = s;
    152 					if (seeds_last!=NULL) seeds_last->next = s;
    153 					seeds_last = s;
    154 					seed = 0;
    155 				}
    156 			}
    157 			//printf("seeds: ");
    158 			//print_numbers(seeds);
    159 		} else if (len>1) { // to skip empty lines
    160 			if (is_digit(buf[0])) { // fill ranges
    161 				Range *r = make_range();
    162 				uint64_t dst_start, src_start, range_len;
    163 				int res = sscanf(buf, "%" PRIu64 " %" PRIu64 " %" PRIu64, &dst_start, &src_start, &range_len);
    164 				assert(res==3);
    165 				//printf("range %d, dst: %" PRIu64 ", src: %" PRIu64 ", len: %" PRIu64 "\n", range_id, dst_start, src_start, range_len);
    166 				fill_range(r, dst_start, src_start, range_len);
    167 				r->id = range_id;
    168 
    169 				// no seriously I should make a struct+functions or macro with that
    170 				if (ranges==NULL) ranges = r;
    171 				if (ranges_last!=NULL) ranges_last->next = r;
    172 				ranges_last = r;
    173 			} else { // create new range id
    174 				//printf("new range: %s", buf);
    175 				++range_id;
    176 			}
    177 		}
    178 		++line_num;
    179 		bzero(buf, STR_LEN);
    180 	}
    181 
    182 	//print_ranges(ranges);
    183 	Number *s1 = seeds;
    184 	while (s1!=NULL) {
    185 		uint64_t loc = calc_loc(ranges, s1->value);
    186 		if (*result1==-1||loc<(uint64_t)*result1) *result1 = loc;
    187 		//printf("seed %" PRIu64 " location: %" PRIu64 "\n", s1->value, loc);
    188 		s1 = s1->next;
    189 	}
    190 
    191 	Number *s2 = seeds;
    192 	thrd_t threads[10] = {0};
    193 	int thread_id = 0;
    194 	static mtx_t mutex;
    195 	if (mtx_init(&mutex, mtx_plain)!=thrd_success) {
    196 		printf("error initing mutex\n");
    197 		thrd_exit(EXIT_FAILURE);
    198 	}
    199 	while (s2!=NULL) {
    200 		uint64_t seed1 = s2->value;
    201 		uint64_t seed2 = 0;
    202 		if (s2->next!=NULL) {
    203 			seed2 = s2->next->value;
    204 			s2 = s2->next->next;
    205 		}
    206 		//printf("seed from %" PRIu64 " of count %" PRIu64 "\n", seed1, seed2);
    207 
    208 		// brain damage
    209 		/*for (uint64_t i=seed1; i<seed1+seed2; ++i) {
    210 			uint64_t loc = calc_loc(ranges, i);
    211 			if (*result2==-1||loc<(uint64_t)*result2) *result2 = loc;
    212 		}*/
    213 		RunArgs *a = malloc(sizeof(RunArgs));
    214 		a->ranges = ranges;
    215 		a->seed1 = seed1;
    216 		a->seed2 = seed2;
    217 		a->result2 = result2;
    218 		a->mutex = &mutex;
    219 		int t_res=thrd_create(&threads[thread_id], run_calc, (void *)a);
    220 		if (t_res!=thrd_success) {
    221 			printf("thrd_create %d error %d\n", thread_id, t_res);
    222 		}
    223 		++thread_id;
    224 	}
    225 
    226 	for (int i=0; i<thread_id; ++i) {
    227 		//printf("waiting for t %d\n", i);
    228 		int t_out = 0;
    229 		int t_res = thrd_join(threads[i], &t_out);
    230 		if (t_res!=thrd_success) {
    231 			printf("error joining thread %d: %d (out %d)\n", i, t_res, t_out);
    232 			//thrd_exit(EXIT_FAILURE);
    233 		}
    234 		//printf("end waiting for t %d\n", i);
    235 	}
    236 
    237 	// mutiny! ignoring feof/ferror.
    238 	fclose(infile);
    239 
    240 	//printf("res1: %lld\n", *result1);
    241 	//printf("res2: %lld\n", *result2);
    242 
    243 	//thrd_exit(EXIT_SUCCESS);
    244 }