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

  • Strlcpy@1
    link
    fedilink
    arrow-up
    3
    ·
    2 months ago

    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);
    }
    
    • CameronDev@programming.devOPM
      link
      fedilink
      arrow-up
      2
      ·
      2 months ago

      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.