commit f9e0572f8dac8018300e00fa159888c71d8390bc
parent 3e04e6d02f2b8c230f6577f61062e16c11c0ede6
Author: bsandro <brian.drosan@gmail.com>
Date: Mon, 8 Dec 2025 22:53:00 +0200
day08 p1 after despair
Diffstat:
| M | day08.c | | | 166 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------- |
1 file changed, 120 insertions(+), 46 deletions(-)
diff --git a/day08.c b/day08.c
@@ -7,8 +7,6 @@
#include <strings.h>
#include "cputime.h"
-#define LEN(x) (sizeof((x))/sizeof(*(x)))
-
typedef union {
struct { int x, y, z; };
int n[3];
@@ -18,12 +16,12 @@ typedef struct {
Point *p1;
Point *p2;
int d;
- int id;
} Distance;
typedef struct {
int id;
- int num;
+ Point *points[1000];
+ int points_l;
} Circuit;
static int btoi(int bufl, int buf[bufl]) {
@@ -42,38 +40,104 @@ static int cmp_dist(const void *vd1, const void *vd2) {
return d1->d - d2->d;
}
-static int find_dist_id(int distsl, const Distance dists[distsl], const Distance *d) {
- for (int i=0;i<distsl;++i) {
- if (d==&dists[i]) continue; // skip self
- Distance di = dists[i];
- if (d->p1==di.p1||d->p2==di.p2||d->p1==di.p2||d->p2==di.p1) {
- return di.id;
+static bool has_point(Circuit *cir, const Point *p) {
+ for (int i=0;i<cir->points_l;++i) {
+ if (cir->points[i]==p) return true;
+ }
+ return false;
+}
+
+static void circuits_add(int *cirs_l, Circuit *cirs, Distance *dist) {
+ //printf("circuits[%d] try add %d -> %d... ", *cirs_l, dist->p1->x, dist->p2->x);
+ for (int i=0;i<*cirs_l;++i) {
+ Circuit *cir = &cirs[i];
+ bool hit1 = has_point(cir, dist->p1);
+ bool hit2 = has_point(cir, dist->p2);
+ if (hit1&&hit2) { // both points are already in circuit
+ //printf("circuit %d has both %d and %d\n", cir->id, dist->p1->x, dist->p2->x);
+ return;
+ } else if (hit1||hit2) { // only one of two points found
+ cir->points[cir->points_l++] = hit1?dist->p2:dist->p1;
+ //printf("add %d to circuit %d\n", hit1?dist->p2->x:dist->p1->x, cir->id);
+ return;
}
}
- return -1;
+
+ int cir_id = (*cirs_l)++;
+ //printf("circuits_add(%d) %d, %d\n", cir_id, dist->p1->x, dist->p2->x);
+ Circuit *cir = &cirs[cir_id];
+ cir->id = cir_id;
+ cir->points[cir->points_l++] = dist->p1;
+ cir->points[cir->points_l++] = dist->p2;
}
static bool has_points(int distsl, const Distance dists[distsl], const Point *p1, const Point *p2) {
for (int i=0;i<distsl;++i) {
- if (dists[i].p1==p2&&dists[i].p2==p1) return true;
+ if ((dists[i].p1==p2&&dists[i].p2==p1) ||
+ (dists[i].p2==p1&&dists[i].p1==p2))
+ return true;
}
return false;
}
-static int cmp_cir(const void *vc1, const void *vc2) {
- return *(int *)(vc2) - *(int *)(vc1);
+static bool circuits_overlap(Circuit *cir1, Circuit *cir2) {
+ for (int i=0;i<cir1->points_l;++i) {
+ if (has_point(cir2, cir1->points[i])) {
+ return true;
+ }
+ }
+ return false;
+}
+
+static void circuit_merge(Circuit *to, Circuit *from) {
+ for (int i=0;i<from->points_l;++i) {
+ if (!has_point(to, from->points[i])) {
+ to->points[to->points_l++] = from->points[i];
+ }
+ }
+ from->points_l = 0;
+}
+
+static int cmp_circuits(const void *vc1, const void *vc2) {
+ const Circuit *c1 = (const Circuit *)vc1;
+ const Circuit *c2 = (const Circuit *)vc2;
+ return c2->points_l - c1->points_l;
+}
+
+void points_print(int points_l, Point *points[points_l]) {
+ for (int i=0;i<points_l;++i) {
+ Point *p = points[i];
+ printf("[%d]", p->x);
+ }
+ printf("\n");
+}
+
+static int circuits_merge(int circuits_l, Circuit circuits[]) {
+ int new_len = circuits_l;
+ for (int i=0;i<circuits_l;++i) {
+ Circuit *cir1 = &circuits[i];
+ for (int j=0;j<circuits_l;++j) {
+ Circuit *cir2 = &circuits[j];
+ if (cir1==cir2) continue;
+ if (circuits_overlap(cir1, cir2)) {
+ circuit_merge(cir1, cir2);
+ new_len--;
+ }
+ }
+ }
+ return new_len;
}
#define POINTS 1000
+#define CONNS 1000
+//#define POINTS 20
+//#define CONNS 10
int main(void) {
uint64_t part1 = 0;
uint64_t part2 = 0;
- //Point *points = malloc(sizeof(Point)*POINTS);
Point *points = calloc(POINTS, sizeof(Point));
- //bzero(points, sizeof(Point)*POINTS);
printf("malloc ok\n");
- exit(0);
int pointsl = 0;
int *n = points[0].n;
int buf[16] = {0};
@@ -87,44 +151,54 @@ int main(void) {
if (c=='\n') n = points[++pointsl].n;
}
}
- Distance dists[POINTS*POINTS] = {0};
- int distsl = 0;
+ printf("%d points\n", pointsl);
+ Distance *dists = calloc((POINTS*POINTS-POINTS)/2, sizeof(Distance));
+ printf("%d dists\n", (POINTS*POINTS-POINTS)/2);
+ int dicts_l = 0;
for (size_t i1=0;i1<POINTS;++i1) {
for (size_t i2=0;i2<POINTS;++i2) {
if (i1==i2) continue;
Point *p1 = &points[i1];
Point *p2 = &points[i2];
int d = dist(points[i1], points[i2]);
- //printf("{ x:%3d,y:%3d,z:%3d } -> ", points[i1].x, points[i1].y, points[i1].z);
- //printf("{ x:%3d,y:%3d,z:%3d } ", points[i2].x, points[i2].y, points[i2].z);
- //printf("%d\n", d);
- if (!has_points(distsl, dists, p1, p2)) dists[distsl++] = (Distance){ p1, p2, d, 0 };
+ if (!has_points(dicts_l, dists, p1, p2)) {
+ dists[dicts_l++] = (Distance){ p1, p2, d };
+ }
}
}
- qsort(dists, distsl, sizeof(Distance), cmp_dist);
- /*for (int i=0;i<distsl;++i) {
- printf("%p -> %p %d\n", dists[i].p1, dists[i].p2, dists[i].d);
- }*/
- int max_id = 0;
- int cir[15] = {0};
- for (int i=0;i<10;++i) { // 10 connections for test
- //for (int d=0;d<distsl;++d) {
- int id = find_dist_id(distsl, dists, &dists[i]);
- //printf("found id: %d\n", id);
- if (id<1) {
- dists[i].id = ++max_id;
- cir[max_id] = 2; // initial circuit always has two junction boxes
- } else {
- dists[i].id = id;
- cir[id]++;
- }
- //}
+ printf("%d dists real\n", dicts_l);
+ qsort(dists, dicts_l, sizeof(Distance), cmp_dist);
+ for (int i=0;i<11;++i) printf("%3d -> %3d (%3d)\n", dists[i].p1->x, dists[i].p2->x, dists[i].d);
+ Circuit *circuits = calloc(CONNS*2, sizeof(Circuit));
+ int circuits_l = 0;
+ printf("Circuits: %zu/%zu\n", sizeof(circuits), sizeof(Circuit));
+ for (int i=0;i<CONNS;++i) {
+ circuits_add(&circuits_l, circuits, &dists[i]);
+ //printf("cir_id: %d (%d -> %d) (max: %d)\n", cir_id, dists[i].p1->x, dists[i].p2->x, max_id);
+ }
+ printf("circuits_l: %d\n", circuits_l);
+ for (int i=0;i<10;++i) {
+ printf("circuit[%2d] = %2d: ", i, circuits[i].points_l);
+ points_print(circuits[i].points_l, circuits[i].points);
+ }
+ int len_prev = circuits_l;
+ while (1) {
+ printf("\nMERGE %d circuits\n", circuits_l);
+ circuits_l = circuits_merge(circuits_l, circuits);
+ if (circuits_l==len_prev) break;
+ len_prev = circuits_l;
+ }
+ for (int i=0;i<10;++i) {
+ printf("circuit[%2d] = %2d: ", circuits[i].id, circuits[i].points_l);
+ points_print(circuits[i].points_l, circuits[i].points);
+ }
+ qsort(circuits, circuits_l, sizeof(Circuit), cmp_circuits);
+ printf("\nSORT\n");
+ for (int i=0;i<10;++i) {
+ printf("circuit[%2d] = %2d: ", circuits[i].id, circuits[i].points_l);
+ points_print(circuits[i].points_l, circuits[i].points);
}
- qsort(cir, 10, sizeof(int), cmp_cir);
- for (int i=0;i<15;++i) printf("cir[%2d] = %d\n", i, cir[i]);
- part2 = cir[0]*cir[1]*cir[2];
- printf("max_id: %d\n", max_id);
- printf("cir[0]: %d\n", cir[0]);
+ part1 = circuits[0].points_l*circuits[1].points_l*circuits[2].points_l;
printf("p1: %"PRIu64"\np2: %"PRIu64"\n", part1, part2);
return 0;
}
