C
Got stuck for a bit on part 1 on a silly mistake in the group (circuit) merging code, where the nodes from one group are reassigned to the other:
for (i=0; i < nnodes; i++)
if (nodes[i].group == pair->b->group)
nodes[i].group = pair->a->group;
At some point in the loop pair->b.group itself is updated, from then on the check is against the new group value. Oops.
In the end, my solution's runtime on my (10 year old!) PC is about 160 ms for both parts, which is more than I would like, so maybe I'll look into better set representations.
Code
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <assert.h>
#define LEN(a) (sizeof(a)/sizeof(*(a)))
#define NPAIRS(x) ((x)*((x)-1)/2)
#define MAXN 1024
struct node { int x,y,z, group; };
struct pair { struct node *a, *b; int64_t dist_sq; };
struct group { int count; };
static struct node nodes[MAXN];
static struct pair pairs[NPAIRS(MAXN)];
static struct group groups[MAXN];
static int nnodes;
static int ngroups;
static int64_t
node_dist_sq(const struct node *a, const struct node *b)
{
return
(int64_t)(a->x - b->x) * (a->x - b->x) +
(int64_t)(a->y - b->y) * (a->y - b->y) +
(int64_t)(a->z - b->z) * (a->z - b->z);
}
static int
cmp_pairs(const void *va, const void *vb)
{
const struct pair *a = va;
const struct pair *b = vb;
return
a->dist_sq < b->dist_sq ? -1 :
a->dist_sq > b->dist_sq ? 1 : 0;
}
static int
cmp_groups_asc(const void *va, const void *vb)
{
const struct group *a = va;
const struct group *b = vb;
return b->count - a->count;
}
static void
merge_groups(int group_a, int group_b)
{
int i;
if (group_a == group_b)
return;
groups[group_a].count += groups[group_b].count;
groups[group_b].count = 0;
for (i=0; i<nnodes; i++)
if (nodes[i].group == group_b)
nodes[i].group = group_a;
ngroups--;
}
int
main()
{
int p1=0,p2=0, p1_limit, i,j, n,p;
for (; ; nnodes++) {
assert(nnodes < MAXN);
n = scanf(" %d,%d,%d",
&nodes[nnodes].x,
&nodes[nnodes].y,
&nodes[nnodes].z);
if (n < 3)
break;
nodes[nnodes].group = nnodes;
groups[nnodes].count = 1;
}
ngroups = nnodes;
for (p=0, i=0; i<nnodes-1; i++)
for (j=i+1; j<nnodes; j++, p++) {
pairs[p].a = &nodes[i];
pairs[p].b = &nodes[j];
pairs[p].dist_sq = node_dist_sq(&nodes[i], &nodes[j]);
}
qsort(pairs, NPAIRS(nnodes), sizeof(*pairs), cmp_pairs);
p1_limit = nnodes <= 100 ? 10 : 1000;
for (i=0; ngroups > 1; i++) {
merge_groups(pairs[i].a->group, pairs[i].b->group);
if (ngroups == 1)
p2 = pairs[i].a->x * pairs[i].b->x;
if (i == p1_limit) {
qsort(groups, LEN(groups), sizeof(*groups),
cmp_groups_asc);
p1 = groups[0].count *
groups[1].count *
groups[2].count;
}
}
printf("08: %d %d\n", p1, p2);
}