From 52c6ea8676fc931974ef4783633aeb494db51226 Mon Sep 17 00:00:00 2001
From: June McEnroe <june@causal.agency>
Date: Wed, 16 Dec 2020 13:15:35 -0500
Subject: Solve day 16 part 2

---
 2020/day16.c | 46 +++++++++++++++++++++++++++++++++++++++++++---
 1 file 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);
 }
-- 
cgit 1.4.1