Day 5: Print Queue

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

  • sjmulder@lemmy.sdf.orgEnglish
    2·
    7 days ago

    C

    I got the question so wrong - I thought a|b and b|c would imply a|c so I went and used dynamic programming to propagate indirect relations through a table.

    It worked beautifully but not for the input, which doesn’t describe an absolute global ordering at all. It may well give a|c and b|c AND c|a. Nothing can be deduced then, and nothing needs to, because all required relations are directly specified.

    The table works great though, the sort comparator is a simple 2D array index, so O(1).

    Code 
    #include "common.h"

#define TSZ 100
#define ASZ 32

/* tab[a][b] is -1 if a<b and 1 if a>b */
static int8_t tab[TSZ][TSZ];

static int
cmp(const void *a, const void *b)
{
	return tab[*(const int *)a][*(const int *)b];
}

int
main(int argc, char **argv)
{
	char buf[128], *rest, *tok;
	int p1=0,p2=0, arr[ASZ],srt[ASZ], n,i, a,b;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		if (sscanf(buf, "%d|%d", &a, &b) != 2)
			break;
		assert(a>=0); assert(a<TSZ);
		assert(b>=0); assert(b<TSZ);
		tab[a][b] = -(tab[b][a] = 1);
	}

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		for (n=0; (tok = strsep(&rest, ",")); n++) {
			assert(n < (int)LEN(arr));
			sscanf(tok, "%d", &arr[n]);
		}

		memcpy(srt, arr, n*sizeof(*srt));
		qsort(srt, n, sizeof(*srt), cmp);
		*(memcmp(srt, arr, n*sizeof(*srt)) ? &p1 : &p2) += srt[n/2];
	}

	printf("05: %d %d\n", p1, p2);
	return 0;
}

    https://github.com/sjmulder/aoc/blob/master/2024/c/day05.c

    • reboot6675@sopuli.xyz
      1·
      7 days ago

      Same, I initially also thought a|b and a|c implies a|c. However when I drew the graph of the example on paper, I suspected that all relations will be given, and coded it with that assumption, that turned out to be correct