advent2021

commit 35c67ee884ea91515df3545b91677acfd48b4f2c
parent 68ba4ca5e9020a2064f94f6bbfaa711ad0a1a935
Author: bsandro <[email protected]>
Date:   Mon, 20 Dec 2021 03:36:22 +0200

Day 19 part 1 wip

Diffstat:
M
day19/Makefile
 | 
2
+-
M
day19/puzzle.c
 | 
94
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 95 insertions(+), 1 deletion(-)
diff --git a/day19/Makefile b/day19/Makefile
@@ -3,7 +3,7 @@ SRC=$(wildcard *.c ../common/*.c)
 DEPS:=$(wildcard *.h ../common/*.h)
 OBJ:=$(SRC:.c=.o)
 CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common
-LDFLAGS=-lc
+LDFLAGS=-lc -lm
 
 all: $(NAME)
 
diff --git a/day19/puzzle.c b/day19/puzzle.c
@@ -7,6 +7,8 @@
 #include <strings.h>
 #include <assert.h>
 #include <ctype.h>
+#include <stdbool.h>
+#include <math.h>
 
 #include "util.h"
 
@@ -15,6 +17,8 @@
 
 struct beacon_t {
 	int x, y, z;
+	int *distances;
+	int distances_count;
 };
 
 struct scanner_t {
@@ -26,6 +30,10 @@ struct scanner_t {
 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);
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
@@ -57,8 +65,12 @@ 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 *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);
 		for (int j = 1; j < BEACONS_VARIANTS; ++j) {
 			data[i].beacons[j] = calloc(data[i].beacons_count, sizeof(struct beacon_t));
@@ -73,12 +85,94 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
 					data[i].beacons[j][k].z);*/
 			}
 		}
+		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);
+							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) {
+									//
+								}
+							}
+						}
+					}
+				}
+			}
+		}
 	}
 
+	*result1 = beacon_iter;;
+
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
+bool compare_scanners(struct scanner_t *scanner1, struct scanner_t *scanner2) {
+	assert(scanner1 != NULL);
+	assert(scanner2 != NULL);
+
+	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;
+		}
+	}
+	return false;
+}
+
+bool compare_beacons(struct beacon_t *b1, struct beacon_t *b2) {
+	assert(b1 != NULL);
+	assert(b2 != NULL);
+
+	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;
+		}
+	}
+
+	return false;
+}
+
+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 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));
+}
+
 void rotate_beacon(struct beacon_t *orig, struct beacon_t *beacon, int variant) {
 	assert(orig != NULL);
 	assert(beacon != NULL);