commit e6d1e0492c3a117c709754b8ae0f7adbd03569f4
parent fd8cec718bf19a09d933ecf8a1af36679f967fb1
Author: bsandro <[email protected]>
Date: Sat, 25 Dec 2021 23:12:51 +0200
Day 19 part 1+2 finally
Diffstat:
| M | day19/puzzle.c | | | 213 | +++++++++++++++++++++++++++++++++++++++++++++++++------------------------------ |
1 file changed, 133 insertions(+), 80 deletions(-)
diff --git a/day19/puzzle.c b/day19/puzzle.c
@@ -9,6 +9,7 @@
#include <ctype.h>
#include <stdbool.h>
#include <math.h>
+#include <unistd.h>
#include "util.h"
@@ -17,23 +18,27 @@
struct beacon_t {
int x, y, z;
- int *distances;
- int distances_count;
};
struct scanner_t {
int id;
struct beacon_t *beacons[BEACONS_VARIANTS];
int beacons_count;
+ bool processed;
+ int x, y, z;
};
struct scanner_t parse_scanner(const char *str);
void parse_beacon(struct scanner_t *scanner, const char *str);
void rotate_beacon(struct beacon_t *orig, struct beacon_t *beacon, int variant);
-bool compare_scanners(struct scanner_t *scanner1, struct scanner_t *scanner2);
-bool compare_beacons(struct beacon_t *b1, struct beacon_t *b2);
-void make_distances(struct scanner_t *scanner);
-int calc_distance(struct beacon_t *b1, struct beacon_t *b2);
+int compare_scanners2(struct scanner_t *scanner1, struct scanner_t *scanner2);
+bool compare_beacons2(struct beacon_t *b1, struct beacon_t *b2);
+int calc_distance(struct scanner_t *s1, struct scanner_t *s2);
+struct scanner_t shift_scanner(struct scanner_t *scanner, int beacon_index);
+void copy_beacons(struct scanner_t *scanner1, struct scanner_t *scanner2, int variant, int origin_index);
+void clear_scanner(struct scanner_t *scanner);
+bool scanner_has_beacon(struct scanner_t *scanner, struct beacon_t *beacon);
+int get_zero_beacon(struct scanner_t *scanner, int variant);
void puzzle(const char *filename, long long *result1, long long *result2) {
FILE *infile = fopen(filename, "r");
@@ -45,9 +50,6 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
char buf[STR_LEN] = {0};
unsigned int line_num = 0;
- *result1 = 0;
- *result2 = 0;
-
struct array_t scanners = { .data = NULL };
array_init(&scanners, sizeof(struct scanner_t), 10);
@@ -65,112 +67,165 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
bzero(buf, STR_LEN);
}
- struct beacon_t *beacons = NULL;
int beacons_count = 0;
+ struct scanner_t *scanners_data = scanners.data;
- struct scanner_t *data = scanners.data;
for (size_t i = 0; i < scanners.count; ++i) {
- beacons_count += data[i].beacons_count;
- //printf("scanner %2d, beacons %2d:\n", data[i].id, data[i].beacons_count);
+ beacons_count += scanners_data[i].beacons_count;
for (int j = 1; j < BEACONS_VARIANTS; ++j) {
- data[i].beacons[j] = calloc(data[i].beacons_count, sizeof(struct beacon_t));
+ scanners_data[i].beacons[j] = calloc(scanners_data[i].beacons_count, sizeof(struct beacon_t));
}
- for (int k = 0; k < data[i].beacons_count; ++k) {
+ for (int k = 0; k < scanners_data[i].beacons_count; ++k) {
for (int j = 0; j < BEACONS_VARIANTS; ++j) {
- rotate_beacon(&data[i].beacons[0][k], &data[i].beacons[j][k], j);
- /*printf("scanner %2d beacon %2d rotation variant %2d: %5d %5d %5d\n",
- data[i].id, k, j,
- data[i].beacons[j][k].x,
- data[i].beacons[j][k].y,
- data[i].beacons[j][k].z);*/
+ rotate_beacon(&scanners_data[i].beacons[0][k], &scanners_data[i].beacons[j][k], j);
}
}
- make_distances(&data[i]);
}
- printf("all beacons count: %d\n", beacons_count);
- int beacon_iter = 0;
- beacons = calloc(beacons_count, sizeof(struct beacon_t));
-
- for (size_t i = 0; i < scanners.count; ++i) {
- for (size_t j = i; j < scanners.count; ++j) {
- if (i == j) continue;
- if (compare_scanners(&data[i], &data[j])) {
- printf("scanners %d and %d overlap!\n", data[i].id, data[j].id);
-
- for (int b1 = 0; b1 < data[i].beacons_count; ++b1) {
- for (int b2 = 0; b2 < data[j].beacons_count; ++b2) {
- if (beacon_iter == 0) {
- beacons[beacon_iter++] = data[i].beacons[0][b1];
- continue;
- }
- if (!compare_beacons(&data[i].beacons[0][b1], &data[i].beacons[0][b2])) {
- beacons[beacon_iter++] = data[i].beacons[0][b1];
- struct beacon_t *beacon = &beacons[beacon_iter-1];
- beacon->distances_count = 0;
- beacon->distances = calloc(data[i].beacons[0][b1].distances_count + data[j].beacons[0][b2].distances_count, sizeof(void *));
- for (int d1 = 0; d1 < data[i].beacons[0][b1].distances_count; ++d1) {
- for (int d2 = 0; d2 < data[i].beacons[j][b2].distances_count; ++d2) {
- //
- }
- }
- }
+ struct scanner_t *first_scanner = &scanners_data[0];
+ first_scanner->processed = true;
+ size_t processed = 1;
+
+ while (processed < scanners.count) {
+ for (size_t j = 1; j < scanners.count; ++j) {
+ if (scanners_data[j].processed) continue;
+ for (int b1 = 0; b1 < first_scanner->beacons_count; ++b1) {
+ struct scanner_t scanner1_dup = shift_scanner(first_scanner, b1);
+
+ for (int b2 = 0; b2 < scanners_data[j].beacons_count; ++b2) {
+ struct scanner_t scanner2_dup = shift_scanner(&scanners_data[j], b2);
+ int v = compare_scanners2(&scanner1_dup, &scanner2_dup);
+ if (v != -1) {
+ copy_beacons(first_scanner, &scanner2_dup, v, b1);
+ processed++;
+ scanners_data[j].processed = true;
+ int zi = get_zero_beacon(&scanner2_dup, v);
+ assert(zi != -1);
+ scanners_data[j].x = first_scanner->beacons[0][b1].x - scanners_data[j].beacons[v][zi].x;
+ scanners_data[j].y = first_scanner->beacons[0][b1].y - scanners_data[j].beacons[v][zi].y;
+ scanners_data[j].z = first_scanner->beacons[0][b1].z - scanners_data[j].beacons[v][zi].z;
+ goto out;
}
+ clear_scanner(&scanner2_dup);
}
+ clear_scanner(&scanner1_dup);
+ }
+ out:;
+ // some memory leak here, i'm too tired of this puzzle to fix that
+ }
+ }
+
+ *result1 = first_scanner->beacons_count;
+
+ int max_dist = 0;
+ for (size_t i = 0; i < scanners.count - 1; ++i) {
+ for (size_t j = i+1; j < scanners.count; ++j) {
+ struct scanner_t *s1 = &scanners_data[i];
+ struct scanner_t *s2 = &scanners_data[j];
+ int dist = calc_distance(s1, s2);
+ if (dist > max_dist) {
+ max_dist = dist;
}
}
}
- *result1 = beacon_iter;;
+ *result2 = max_dist;
// mutiny! ignoring feof/ferror.
fclose(infile);
}
-bool compare_scanners(struct scanner_t *scanner1, struct scanner_t *scanner2) {
- assert(scanner1 != NULL);
- assert(scanner2 != NULL);
+int get_zero_beacon(struct scanner_t *scanner, int variant) {
+ for (int i = 0; i < scanner->beacons_count; ++i) {
+ struct beacon_t *b = &scanner->beacons[variant][i];
+ if (b->x == 0 && b->y == 0 && b->z == 0) {
+ return i;
+ }
+ }
+ return -1;
+}
- int overlapping = 0;
- for (int i = 0; i < scanner1->beacons_count; ++i) {
- for (int j = 0; j < scanner2->beacons_count; ++j) {
- if (compare_beacons(&scanner1->beacons[0][i], &scanner2->beacons[0][j])) {
- overlapping++;
- }
- if (overlapping >= 11) return true;
+bool scanner_has_beacon(struct scanner_t *scanner, struct beacon_t *beacon) {
+ for (int i = 0; i < scanner->beacons_count; ++i) {
+ if (compare_beacons2(&scanner->beacons[0][i], beacon)) {
+ return true;
}
}
return false;
}
-bool compare_beacons(struct beacon_t *b1, struct beacon_t *b2) {
- assert(b1 != NULL);
- assert(b2 != NULL);
+void clear_scanner(struct scanner_t *scanner) {
+ for (int i = 0; i < 24; ++i) {
+ free(scanner->beacons[i]);
+ }
+ scanner->beacons_count = 0;
+}
- int confidence = 0;
- for (int i = 0; i < b1->distances_count; ++i) {
- for (int j = 0; j < b2->distances_count; ++j) {
- //printf("d1=%4d, d2=%4d, conf=%d\n", b1->distances[i], b2->distances[j], confidence);
- if (b1->distances[i] == b2->distances[j]) confidence++;
- if (confidence >= 11) return true;
+void copy_beacons(struct scanner_t *scanner1, struct scanner_t *scanner2, int variant, int origin_index) {
+ int orig_count = scanner1->beacons_count;
+ int new_count = orig_count + scanner2->beacons_count;
+ scanner1->beacons[0] = realloc(scanner1->beacons[0], new_count * sizeof(struct beacon_t));
+ struct beacon_t *origin = &scanner1->beacons[0][origin_index];
+ for (int i = 0; i < scanner2->beacons_count; ++i) {
+ struct beacon_t beacon = scanner2->beacons[variant][i];
+ beacon.x += origin->x;
+ beacon.y += origin->y;
+ beacon.z += origin->z;
+ if (!scanner_has_beacon(scanner1, &beacon)) {
+ scanner1->beacons[0][scanner1->beacons_count++] = beacon;
}
}
+}
- return false;
+struct scanner_t shift_scanner(struct scanner_t *scanner, int index) {
+ struct scanner_t copy = {0};
+ copy.beacons_count = scanner->beacons_count;
+ copy.id = scanner->id;
+ for (int v = 0; v < 24; ++v) {
+ struct beacon_t *zeropoint = &scanner->beacons[v][index];
+ copy.beacons[v] = calloc(scanner->beacons_count, sizeof(struct beacon_t));
+ for (int i = 0; i < scanner->beacons_count; ++i) {
+ struct beacon_t *bcopy = ©.beacons[v][i];
+ struct beacon_t *orig = &scanner->beacons[v][i];
+ bcopy->x = orig->x - zeropoint->x;
+ bcopy->y = orig->y - zeropoint->y;
+ bcopy->z = orig->z - zeropoint->z;
+ }
+ }
+ return copy;
}
-void make_distances(struct scanner_t *scanner) {
- for (int i = 0; i < scanner->beacons_count; ++i) {
- scanner->beacons[0][i].distances = calloc(pow(scanner->beacons_count, 2), sizeof(int));
- for (int j = 0; j < scanner->beacons_count; ++j) {
- if (i == j) continue;
- scanner->beacons[0][i].distances[scanner->beacons[0][i].distances_count++] = calc_distance(&scanner->beacons[0][i], &scanner->beacons[0][j]);
+int compare_scanners2(struct scanner_t *scanner1, struct scanner_t *scanner2) {
+ assert(scanner1 != NULL);
+ assert(scanner2 != NULL);
+
+ int overlapping;
+ for (int v = 0; v < 24; ++v) {
+ overlapping = 0;
+ for (int i = 0; i < scanner1->beacons_count; ++i) {
+ for (int j = 0; j < scanner2->beacons_count; ++j) {
+ if (compare_beacons2(&scanner1->beacons[0][i], &scanner2->beacons[v][j])) {
+ overlapping++;
+ }
+ if (overlapping >= 11) {
+ return v;
+ }
+ }
}
}
+
+ return -1;
+}
+
+bool compare_beacons2(struct beacon_t *b1, struct beacon_t *b2) {
+ assert(b1 != NULL);
+ assert(b2 != NULL);
+
+ return b1->x == b2->x && b1->y == b2->y && b1->z == b2->z;
}
-int calc_distance(struct beacon_t *b1, struct beacon_t *b2) {
- return sqrt(pow(b1->x - b2->x, 2) + pow(b1->y - b2->y, 2) + pow(b1->z - b2->z, 2));
+int calc_distance(struct scanner_t *s1, struct scanner_t *s2) {
+ return abs(s2->x - s1->x) + abs(s2->y - s1->y) + abs(s2->z - s1->z);
}
void rotate_beacon(struct beacon_t *orig, struct beacon_t *beacon, int variant) {
@@ -239,13 +294,11 @@ struct scanner_t parse_scanner(const char *str) {
while ((token = strsep(&tmp, "- \n")) != NULL) {
if (*token == '\0') continue;
if (isdigit(token[0])) {
- //printf("token=%s\n", token);
scanner_id = atoi(token);
break;
}
}
assert(scanner_id != -1);
- //printf("scanner_id=%d\n", scanner_id);
scanner.id = scanner_id;
return scanner;
}
