Puzzle 13: Solve part 2

1 files changed, 77 insertions, 18 deletions

diff --git a/13.c b/13.c
index 42113f7..3d49167 100644
--- a/13.c
+++ b/13.c
@@ -2,6 +2,7 @@
 #include <ctype.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <unistd.h>
 
 
 struct node {
@@ -90,7 +91,7 @@ node_dump(struct node * n)
 
 
 int
-node_cmp(struct node * l, struct node * r)
+node_cmp(struct node const * l, struct node const * r)
 {
 	while (l && r) {
 		int ret;
@@ -136,6 +137,13 @@ node_cmp(struct node * l, struct node * r)
 }
 
 
+int
+node_cmp_q(void const * a, void const * b)
+{
+	return node_cmp(*(struct node const **) a, *(struct node const **) b);
+}
+
+
 struct node *
 node_parse(char ** ppch)
 {
@@ -185,11 +193,24 @@ node_parse(char ** ppch)
 
 
 int
-main()
+main(int argc, char ** argv)
 {
-	struct node * packets = NULL, * last = NULL, * n;
+	struct node * packets = NULL, * last = NULL, * n, * sep1, * sep2;
+	struct node ** ppackets;
 	char buf[BUFSIZ];
-	int index_sum = 0, i;
+	int part = 1, npackets = 0, index_sum = 0, i;
+	int isep1 = -1, isep2 = -1;
+
+	while ((i = getopt(argc, argv, "p:")) != -1) {
+		switch (i) {
+		case 'p':
+			part = atoi(optarg);
+			break;
+
+		default:
+			return -1;
+		}
+	}
 
 	while (fgets(buf, sizeof(buf), stdin)) {
 		char * pch;
@@ -221,28 +242,66 @@ main()
 		else {
 			packets = last = n;
 		}
+		++npackets;
 	}
 
-	for (n = packets, i = 1; n != NULL && n->next != NULL; n = n->next->next, ++i) {
-		int j;
+	switch (part) {
+	case 1:
+		for (n = packets, i = 1; n != NULL && n->next != NULL; n = n->next->next, ++i) {
+			int j;
 
-		if ((j = node_cmp(n->val_list, n->next->val_list)) < 0) {
-			index_sum += i;
-		}
+			if ((j = node_cmp(n->val_list, n->next->val_list)) < 0) {
+				index_sum += i;
+			}
 #if 0
-		node_dump(n->val_list); fputc('\n', stderr);
-		node_dump(n->next->val_list); fputc('\n', stderr);
-		fprintf(stderr, "Result: %d (%s)\n", j, j < 0 ? "yes" : "no");
+			node_dump(n->val_list); fputc('\n', stderr);
+			node_dump(n->next->val_list); fputc('\n', stderr);
+			fprintf(stderr, "Result: %d (%s)\n", j, j < 0 ? "yes" : "no");
 #endif
 
-		if (j == 0) {
-			fprintf(stderr, "Got two identical packets?\n");
-			node_dump(n); fputc('\n', stderr);
-			node_dump(n->next); fputc('\n', stderr);
+			if (j == 0) {
+				fprintf(stderr, "Got two identical packets?\n");
+				node_dump(n); fputc('\n', stderr);
+				node_dump(n->next); fputc('\n', stderr);
+			}
 		}
-	}
 
-	printf("Index sum: %d\n", index_sum);
+		printf("Index sum: %d\n", index_sum);
+		break;
+
+	case 2:
+		if ((ppackets = malloc((npackets + 2) * sizeof(struct node *))) == NULL) {
+			fprintf(stderr, "Bad malloc(%ld)\n", npackets * sizeof(struct node *));
+			node_free(packets);
+			return -1;
+		}
+		sep1 = node_create_list(node_create_int(2)); // ???
+		sep2 = node_create_list(node_create_int(6));
+		ppackets[0] = sep1;
+		ppackets[1] = sep2;
+		for (n = packets, i = 2; n != NULL; n = n->next, ++i)
+			ppackets[i] = n->val_list;
+		qsort(ppackets, npackets + 2, sizeof(struct node *), node_cmp_q);
+		for (i = 0; i < npackets + 2; ++i) {
+			if (ppackets[i] == sep1)
+				isep1 = i;
+			else if (ppackets[i] == sep2)
+				isep2 = i;
+		}
+
+		printf("Separator index product: %d (%d * %d)\n",
+				(isep1 + 1) * (isep2 + 1), isep1, isep2);
+
+		node_free(sep2);
+		node_free(sep1);
+		free(ppackets);
+		break;
+
+	default:
+		fprintf(stderr, "Unexpected puzzle part %d\n", part);
+		node_free(packets);
+		return -1;
+	}
 
 	node_free(packets);