Day 8: Playground
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465


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.groupitself 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); }I think we basically did the same bug, but I did it in rust.
160ms is respectable, I am at 300ms. Probably should remove my sqrt.