advent2025

day08.c (4980B)

---

 #include <stdio.h>
 #include <stdlib.h>
 #include <inttypes.h>
 #include <math.h>
 #include <stdbool.h>
 #include <string.h>
 #include <strings.h>
 #include "cputime.h"
 
 typedef union {
     struct { int x, y, z; };
     int n[3];
 } Point;
 
 typedef struct {
     Point *p1;
     Point *p2;
     int d;
 } Distance;
 
 typedef struct {
     int id;
     Point *points[1000];
     int points_l;
 } Circuit;
 
 static int btoi(int bufl, int buf[bufl]) {
     int num = 0;
     for (int i=0;i<bufl;++i) num = num*10+buf[i];
     return num;
 }
 
 static int dist(Point p1, Point p2) {
     return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2)+pow(p1.z-p2.z,2));
 }
 
 static int cmp_dist(const void *vd1, const void *vd2) {
     Distance *d1 = (Distance *)vd1;
     Distance *d2 = (Distance *)vd2;
     return d1->d - d2->d;
 }
 
 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) {
     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
             return;
         } else if (hit1||hit2) { // only one of two points found
             cir->points[cir->points_l++] = hit1?dist->p2:dist->p1;
             return;
         }
     }
 
     int cir_id = (*cirs_l)++;
     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 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;
 }
 
 static int circuits_merge(int circuits_l, Circuit *circuits) {
     int new_len = circuits_l;
     for (int i=0;i<circuits_l;++i) {
         for (int j=i;j<circuits_l;++j) {
             Circuit *cir1 = &circuits[i];
             Circuit *cir2 = &circuits[j];
             if (i==j) continue;
             if (cir1==cir2) continue;
             if (circuits_overlap(cir1, cir2)) {
                 circuit_merge(cir1, cir2);
                 new_len--;
                 break;
             }
         }
     }
     qsort(circuits, circuits_l, sizeof(Circuit), cmp_circuits);
     return new_len;
 }
 
 #define MAX_POINTS 1000
 
 int main(void) {
     uint64_t part1 = 0;
     uint64_t part2 = 0;
     Point *points = calloc(MAX_POINTS, sizeof(Point));
     int points_l = 0;
     int *n = points[0].n;
     int buf[16] = {0};
     int bufl = 0;
     for (int c=getchar();c!=EOF;c=getchar()) {
         if (c>='0'&&c<='9') buf[bufl++] = c-'0';
         else if (c==','||c=='\n') {
             *n = btoi(bufl, buf);
             bufl = 0;
             n++;
             if (c=='\n') n = points[++points_l].n;
         }
         if (points_l>MAX_POINTS) {
             printf("Too many input points, max: %d\n", MAX_POINTS);
             return 1;
         }
     }
     const int dists_cnt = (points_l*points_l-points_l)/2;
     const int conns_cnt = dists_cnt<1000 ? 10 : 1000;
     Distance *dists = calloc(dists_cnt, sizeof(Distance));
     int dists_l = 0;
     for (int i1=0;i1<points_l;++i1) {
         for (int i2=i1;i2<points_l;++i2) {
             if (i1==i2) continue;
             Point *p1 = &points[i1];
             Point *p2 = &points[i2];
             int d = dist(points[i1], points[i2]);
             dists[dists_l++] = (Distance){ p1, p2, d };
         }
     }
     qsort(dists, dists_l, sizeof(Distance), cmp_dist);
     Circuit *circuits = calloc(conns_cnt*2, sizeof(Circuit));
     int circuits_l = 0;
     for (int i=0;i<conns_cnt;++i) {
         circuits_add(&circuits_l, circuits, &dists[i]);
         circuits_l = circuits_merge(circuits_l, circuits);
     }
     qsort(circuits, circuits_l, sizeof(Circuit), cmp_circuits);
     part1 = circuits[0].points_l*circuits[1].points_l*circuits[2].points_l;
     free(circuits);
     // ---------------- p2 -------------------
     circuits = calloc(dists_l/2, sizeof(Circuit));
     circuits_l = 0;
     for (int i=0;i<dists_l;++i) {
         circuits_add(&circuits_l, circuits, &dists[i]);
         circuits_l = circuits_merge(circuits_l, circuits);
         if (circuits[0].points_l==points_l) {
             part2 = dists[i].p1->x * dists[i].p2->x;
             break;
         }
     }
     free(circuits);
     free(dists);
     free(points);
 
     printf("p1: %"PRIu64"\np2: %"PRIu64"\n", part1, part2);
     return 0;
 }