2
1
Fork 0
aoc2021/14/solution.c

69 lines
1.8 KiB
C
Raw Permalink Normal View History

2021-12-14 21:14:00 +01:00
#include <stdio.h>
#include <string.h>
/* we can pack the pairs into integers… */
#define P(a,b) (( (a-'A')<<6 )| (b-'A'))
/* …and use them as keys for a lookup table */
enum {maxk=P('Z','Z')+1};
size_t counts[maxk] = {0}, tcounts[maxk];
void pcounts(const char *s) {
size_t min=-1,max=0,k,n,i;
for(i='A';i<'Z'+1;i++) {
k=P(i,'z');
if ((n=counts[k])){
if (n<min) min=n;
else if (n>max) max=n;
}
}
printf("%s: %lu\n", s, max-min);
}
int main(void) {
char tmpl[128], rules[128][3]={0};
size_t i,j,n,k;
scanf("%127[A-Z]\n", tmpl);
for(i=0;tmpl[i];i++){
/* set initial counts for pairs and single chars */
if(i) counts[P(tmpl[i-1],tmpl[i])]++;
/* use the same LUT for both */
counts[P(tmpl[i],'z')]++;
}
for(i=0;scanf("%c%c -> %c\n",
&rules[i][0], &rules[i][1], &rules[i][2])==3;i++);
for(i=0;i<40;i++) {
/* reset temp LUT */
memset(tcounts, 0, maxk*sizeof(size_t));
/* apply each rule */
for(j=0;rules[j][0];j++) {
k=P(rules[j][0],rules[j][1]);
if ((n=counts[k])) {
counts[k]=0;
/* single chars can be updated here */
counts[P(rules[j][2],'z')]+=n;
/* pairs must be counted independently */
tcounts[P(rules[j][0],rules[j][2])]+=n;
tcounts[P(rules[j][2],rules[j][1])]+=n;
}
}
/* commit temp results */
for(j=0;rules[j][0];j++) {
k=P(rules[j][0],rules[j][2]);
counts[k] = tcounts[k];
k=P(rules[j][2],rules[j][1]);
counts[k] = tcounts[k];
}
if (i==9)
pcounts("Silver");
}
pcounts("Gold");
}