diff options
| -rw-r--r-- | 2020/day16.c | 46 |
1 files changed, 43 insertions, 3 deletions
diff --git a/2020/day16.c b/2020/day16.c index 6b3d29e..df28ae6 100644 --- a/2020/day16.c +++ b/2020/day16.c @@ -40,16 +40,56 @@ int main(void) { int len; for (len = 0; parse(&nearby[len]); ++len); int error = 0; + struct Ticket valids[256]; + int vlen = 0; for (int i = 0; i < len; ++i) { + bool ticket = true; for (int j = 0; j < nrules; ++j) { - bool valid = false; + bool field = false; for (int r = 0; r < nrules; ++r) { if (!check(&rules[r], nearby[i].fields[j])) continue; - valid = true; + field = true; break; } - if (!valid) error += nearby[i].fields[j]; + if (!field) { + error += nearby[i].fields[j]; + ticket = false; + } } + if (ticket) valids[vlen++] = nearby[i]; } printf("%d\n", error); + int map[32] = {0}; + for (int r = 0; r < nrules; ++r) { + for (int f = 0; f < nrules; ++f) { + bool valid = true; + for (int i = 0; i < vlen; ++i) { + if (check(&rules[r], valids[i].fields[f])) continue; + valid = false; + break; + } + if (valid) map[r] |= 1 << f; + } + } + for (bool done = false; !done;) { + for (int i = 0; i < nrules; ++i) { + if (__builtin_popcount(map[i]) > 1) continue; + for (int j = 0; j < nrules; ++j) { + if (j != i) map[j] &= ~map[i]; + } + } + done = true; + for (int i = 0; i < nrules; ++i) { + if (__builtin_popcount(map[i]) > 1) done = false; + } + } + for (int i = 0; i < nrules; ++i) { + map[i] = __builtin_ctz(map[i]); + } + long departure = 1; + for (int i = 0; i < nrules; ++i) { + if (strncmp(rules[i].name, "departure", 9)) continue; + departure *= mine.fields[map[i]]; + } + printf("%ld\n", departure); } |