puzzle.c (10370B)
1 #define _DEFAULT_SOURCE 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <errno.h> 6 #include <string.h> 7 #include <strings.h> 8 #include <assert.h> 9 #include <ctype.h> 10 #include <stdbool.h> 11 #include <math.h> 12 #include <unistd.h> 13 14 #include "util.h" 15 16 #define STR_LEN 1024 17 #define BEACONS_VARIANTS 24 18 19 struct beacon_t { 20 int x, y, z; 21 }; 22 23 struct scanner_t { 24 int id; 25 struct beacon_t *beacons[BEACONS_VARIANTS]; 26 int beacons_count; 27 bool processed; 28 int x, y, z; 29 }; 30 31 struct scanner_t parse_scanner(const char *str); 32 void parse_beacon(struct scanner_t *scanner, const char *str); 33 void rotate_beacon(struct beacon_t *orig, struct beacon_t *beacon, int variant); 34 int compare_scanners2(struct scanner_t *scanner1, struct scanner_t *scanner2); 35 bool compare_beacons2(struct beacon_t *b1, struct beacon_t *b2); 36 int calc_distance(struct scanner_t *s1, struct scanner_t *s2); 37 struct scanner_t shift_scanner(struct scanner_t *scanner, int beacon_index); 38 void copy_beacons(struct scanner_t *scanner1, struct scanner_t *scanner2, int variant, int origin_index); 39 void clear_scanner(struct scanner_t *scanner); 40 bool scanner_has_beacon(struct scanner_t *scanner, struct beacon_t *beacon); 41 int get_zero_beacon(struct scanner_t *scanner, int variant); 42 43 void puzzle(const char *filename, long long *result1, long long *result2) { 44 FILE *infile = fopen(filename, "r"); 45 if (infile == NULL) { 46 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 47 return; 48 } 49 50 char buf[STR_LEN] = {0}; 51 unsigned int line_num = 0; 52 53 struct array_t scanners = { .data = NULL }; 54 array_init(&scanners, sizeof(struct scanner_t), 10); 55 56 while (fgets(buf, STR_LEN, infile) != NULL) { 57 char *scan = NULL; 58 if ((scan = strstr(buf, "scanner")) != NULL) { 59 if (scanners.count >= scanners.cap) array_expand(&scanners); 60 struct scanner_t *scanners_data = scanners.data; 61 scanners_data[scanners.count++] = parse_scanner(scan); 62 } else if (strlen(buf) > 2) { 63 struct scanner_t *scanner = &((struct scanner_t *)scanners.data)[scanners.count-1]; 64 parse_beacon(scanner, buf); 65 } 66 ++line_num; 67 bzero(buf, STR_LEN); 68 } 69 70 int beacons_count = 0; 71 struct scanner_t *scanners_data = scanners.data; 72 73 for (size_t i = 0; i < scanners.count; ++i) { 74 beacons_count += scanners_data[i].beacons_count; 75 for (int j = 1; j < BEACONS_VARIANTS; ++j) { 76 scanners_data[i].beacons[j] = calloc(scanners_data[i].beacons_count, sizeof(struct beacon_t)); 77 } 78 for (int k = 0; k < scanners_data[i].beacons_count; ++k) { 79 for (int j = 0; j < BEACONS_VARIANTS; ++j) { 80 rotate_beacon(&scanners_data[i].beacons[0][k], &scanners_data[i].beacons[j][k], j); 81 } 82 } 83 } 84 85 struct scanner_t *first_scanner = &scanners_data[0]; 86 first_scanner->processed = true; 87 size_t processed = 1; 88 89 while (processed < scanners.count) { 90 for (size_t j = 1; j < scanners.count; ++j) { 91 if (scanners_data[j].processed) continue; 92 for (int b1 = 0; b1 < first_scanner->beacons_count; ++b1) { 93 struct scanner_t scanner1_dup = shift_scanner(first_scanner, b1); 94 95 for (int b2 = 0; b2 < scanners_data[j].beacons_count; ++b2) { 96 struct scanner_t scanner2_dup = shift_scanner(&scanners_data[j], b2); 97 int v = compare_scanners2(&scanner1_dup, &scanner2_dup); 98 if (v != -1) { 99 copy_beacons(first_scanner, &scanner2_dup, v, b1); 100 processed++; 101 scanners_data[j].processed = true; 102 int zi = get_zero_beacon(&scanner2_dup, v); 103 assert(zi != -1); 104 scanners_data[j].x = first_scanner->beacons[0][b1].x - scanners_data[j].beacons[v][zi].x; 105 scanners_data[j].y = first_scanner->beacons[0][b1].y - scanners_data[j].beacons[v][zi].y; 106 scanners_data[j].z = first_scanner->beacons[0][b1].z - scanners_data[j].beacons[v][zi].z; 107 goto out; 108 } 109 clear_scanner(&scanner2_dup); 110 } 111 clear_scanner(&scanner1_dup); 112 } 113 out:; 114 // some memory leak here, i'm too tired of this puzzle to fix that 115 } 116 } 117 118 *result1 = first_scanner->beacons_count; 119 120 int max_dist = 0; 121 for (size_t i = 0; i < scanners.count - 1; ++i) { 122 for (size_t j = i+1; j < scanners.count; ++j) { 123 struct scanner_t *s1 = &scanners_data[i]; 124 struct scanner_t *s2 = &scanners_data[j]; 125 int dist = calc_distance(s1, s2); 126 if (dist > max_dist) { 127 max_dist = dist; 128 } 129 } 130 } 131 132 *result2 = max_dist; 133 134 // mutiny! ignoring feof/ferror. 135 fclose(infile); 136 } 137 138 int get_zero_beacon(struct scanner_t *scanner, int variant) { 139 for (int i = 0; i < scanner->beacons_count; ++i) { 140 struct beacon_t *b = &scanner->beacons[variant][i]; 141 if (b->x == 0 && b->y == 0 && b->z == 0) { 142 return i; 143 } 144 } 145 return -1; 146 } 147 148 bool scanner_has_beacon(struct scanner_t *scanner, struct beacon_t *beacon) { 149 for (int i = 0; i < scanner->beacons_count; ++i) { 150 if (compare_beacons2(&scanner->beacons[0][i], beacon)) { 151 return true; 152 } 153 } 154 return false; 155 } 156 157 void clear_scanner(struct scanner_t *scanner) { 158 for (int i = 0; i < 24; ++i) { 159 free(scanner->beacons[i]); 160 } 161 scanner->beacons_count = 0; 162 } 163 164 void copy_beacons(struct scanner_t *scanner1, struct scanner_t *scanner2, int variant, int origin_index) { 165 int orig_count = scanner1->beacons_count; 166 int new_count = orig_count + scanner2->beacons_count; 167 scanner1->beacons[0] = realloc(scanner1->beacons[0], new_count * sizeof(struct beacon_t)); 168 struct beacon_t *origin = &scanner1->beacons[0][origin_index]; 169 for (int i = 0; i < scanner2->beacons_count; ++i) { 170 struct beacon_t beacon = scanner2->beacons[variant][i]; 171 beacon.x += origin->x; 172 beacon.y += origin->y; 173 beacon.z += origin->z; 174 if (!scanner_has_beacon(scanner1, &beacon)) { 175 scanner1->beacons[0][scanner1->beacons_count++] = beacon; 176 } 177 } 178 } 179 180 struct scanner_t shift_scanner(struct scanner_t *scanner, int index) { 181 struct scanner_t copy = {0}; 182 copy.beacons_count = scanner->beacons_count; 183 copy.id = scanner->id; 184 for (int v = 0; v < 24; ++v) { 185 struct beacon_t *zeropoint = &scanner->beacons[v][index]; 186 copy.beacons[v] = calloc(scanner->beacons_count, sizeof(struct beacon_t)); 187 for (int i = 0; i < scanner->beacons_count; ++i) { 188 struct beacon_t *bcopy = ©.beacons[v][i]; 189 struct beacon_t *orig = &scanner->beacons[v][i]; 190 bcopy->x = orig->x - zeropoint->x; 191 bcopy->y = orig->y - zeropoint->y; 192 bcopy->z = orig->z - zeropoint->z; 193 } 194 } 195 return copy; 196 } 197 198 int compare_scanners2(struct scanner_t *scanner1, struct scanner_t *scanner2) { 199 assert(scanner1 != NULL); 200 assert(scanner2 != NULL); 201 202 int overlapping; 203 for (int v = 0; v < 24; ++v) { 204 overlapping = 0; 205 for (int i = 0; i < scanner1->beacons_count; ++i) { 206 for (int j = 0; j < scanner2->beacons_count; ++j) { 207 if (compare_beacons2(&scanner1->beacons[0][i], &scanner2->beacons[v][j])) { 208 overlapping++; 209 } 210 if (overlapping >= 11) { 211 return v; 212 } 213 } 214 } 215 } 216 217 return -1; 218 } 219 220 bool compare_beacons2(struct beacon_t *b1, struct beacon_t *b2) { 221 assert(b1 != NULL); 222 assert(b2 != NULL); 223 224 return b1->x == b2->x && b1->y == b2->y && b1->z == b2->z; 225 } 226 227 int calc_distance(struct scanner_t *s1, struct scanner_t *s2) { 228 return abs(s2->x - s1->x) + abs(s2->y - s1->y) + abs(s2->z - s1->z); 229 } 230 231 void rotate_beacon(struct beacon_t *orig, struct beacon_t *beacon, int variant) { 232 assert(orig != NULL); 233 assert(beacon != NULL); 234 assert(variant >= 0 && variant < BEACONS_VARIANTS); 235 switch (variant) { 236 // case 0: beacon->x = orig->x; beacon->y = orig->y; beacon->z = orig->z; return; 237 case 1: beacon->x = orig->x; beacon->y = -orig->z; beacon->z = orig->y; return; 238 case 2: beacon->x = orig->x; beacon->y = -orig->y; beacon->z = -orig->z; return; 239 case 3: beacon->x = orig->x; beacon->y = orig->z; beacon->z = -orig->y; return; 240 241 case 4: beacon->x = -orig->y; beacon->y = orig->x; beacon->z = orig->z; return; 242 case 5: beacon->x = orig->z; beacon->y = orig->x; beacon->z = orig->y; return; 243 case 6: beacon->x = orig->y; beacon->y = orig->x; beacon->z = -orig->z; return; 244 case 7: beacon->x = -orig->z; beacon->y = orig->x; beacon->z = -orig->y; return; 245 246 case 8: beacon->x = -orig->x; beacon->y = -orig->y; beacon->z = orig->z; return; 247 case 9: beacon->x = -orig->x; beacon->y = -orig->z; beacon->z = -orig->y; return; 248 case 10: beacon->x = -orig->x; beacon->y = orig->y; beacon->z = -orig->z; return; 249 case 11: beacon->x = -orig->x; beacon->y = orig->z; beacon->z = orig->y; return; 250 251 case 12: beacon->x = orig->y; beacon->y = -orig->x; beacon->z = orig->z; return; 252 case 13: beacon->x = orig->z; beacon->y = -orig->x; beacon->z = -orig->y; return; 253 case 14: beacon->x = -orig->y; beacon->y = -orig->x; beacon->z = -orig->z; return; 254 case 15: beacon->x = -orig->z; beacon->y = -orig->x; beacon->z = orig->y; return; 255 256 case 16: beacon->x = -orig->z; beacon->y = orig->y; beacon->z = orig->x; return; 257 case 17: beacon->x = orig->y; beacon->y = orig->z; beacon->z = orig->x; return; 258 case 18: beacon->x = orig->z; beacon->y = -orig->y; beacon->z = orig->x; return; 259 case 19: beacon->x = -orig->y; beacon->y = -orig->z; beacon->z = orig->x; return; 260 261 case 20: beacon->x = -orig->z; beacon->y = -orig->y; beacon->z = -orig->x; return; 262 case 21: beacon->x = -orig->y; beacon->y = orig->z; beacon->z = -orig->x; return; 263 case 22: beacon->x = orig->z; beacon->y = orig->y; beacon->z = -orig->x; return; 264 case 23: beacon->x = orig->y; beacon->y = -orig->z; beacon->z = -orig->x; return; 265 } 266 } 267 268 void parse_beacon(struct scanner_t *scanner, const char *str) { 269 assert(scanner != NULL); 270 assert(str != NULL); 271 struct array_t coordinates = { .data=NULL }; 272 array_init(&coordinates, sizeof(int), 3); 273 parse_numbers_array(&coordinates, str, ","); 274 assert(coordinates.count == 3); 275 int *coordinates_data = coordinates.data; 276 scanner->beacons_count++; 277 scanner->beacons[0] = realloc(scanner->beacons[0], scanner->beacons_count * sizeof(struct beacon_t)); 278 assert(scanner->beacons[0] != NULL); 279 280 scanner->beacons[0][scanner->beacons_count-1] = (struct beacon_t){ 281 .x = coordinates_data[0], 282 .y = coordinates_data[1], 283 .z = coordinates_data[2] 284 }; 285 } 286 287 struct scanner_t parse_scanner(const char *str) { 288 assert(str != NULL); 289 struct scanner_t scanner = {0}; 290 char *tmp = strndup(str, STR_LEN); 291 char *token = NULL; 292 assert(tmp != NULL); 293 int scanner_id = -1; 294 while ((token = strsep(&tmp, "- \n")) != NULL) { 295 if (*token == '\0') continue; 296 if (isdigit(token[0])) { 297 scanner_id = atoi(token); 298 break; 299 } 300 } 301 assert(scanner_id != -1); 302 scanner.id = scanner_id; 303 return scanner; 304 } 305