2
1
Fork 0
aoc2021/03/solution_2.c

66 lines
1.6 KiB
C
Raw Permalink Normal View History

2021-12-03 21:29:10 +01:00
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long long flt(long long *data, size_t n, size_t rlen, char most) {
size_t nused = n;
char used[n];
memset(used, 1, n);
for (size_t b = 0; b < rlen; b++) {
size_t bitcnt[2][rlen];
memset(bitcnt[0], 0, rlen * sizeof(size_t));
memset(bitcnt[1], 0, rlen * sizeof(size_t));
for (size_t i = 0; i < n; i++) {
if (used[i]) {
if ((data[i] >> (rlen - b - 1)) & 1)
bitcnt[1][b]++;
else
bitcnt[0][b]++;
}
}
if (nused > 1) {
char cond;
if (bitcnt[0][b] == bitcnt[1][b])
cond = most;
else
cond = (bitcnt[0][b] > bitcnt[1][b]) ? !most : most;
for (size_t i = 0; i < n; i++) {
if (used[i]) {
if (((data[i] >> (rlen - b - 1)) & 1) != cond) {
used[i] = 0;
nused--;
}
}
}
}
if (nused == 1) {
for (size_t i = 0; i < n; i++) {
if (used[i])
return data[i];
}
}
}
return 0;
}
int main(void) {
FILE *fp = fopen("input.txt", "r");
char buf[16], *end;
size_t n = 0;
long long data[1000] = {0};
while (fgets(buf, sizeof(buf), fp) != NULL) {
data[n] = strtoll(buf, &end, 2);
n++;
}
printf("Answer: %lld\n",
flt(data, n, end - buf, 1) * flt(data, n, end - buf, 0));
}