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 }