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
- 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
You are viewing a single thread.
View all comments 2 points
*
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;
}
1 point
