From f328e9a8fe0ab35252ff48a4238800f9f9f826b5 Mon Sep 17 00:00:00 2001
From: Adam Spragg <adam@spra.gg>
Date: Tue, 13 Dec 2022 23:40:29 +0000
Subject: First attempt at puzzle 13 part 1 (buggy)

Gets correct answer for test input, but wrong answer (5711) for main
input. The problem is, I don't know where it's going wrong, and the
inputs are complicated, so tracking down the source of the problem is
going to be a major pain.

Wish I hadn't put this off for most of the day, and had more time to
look at it now.
---
 13.c     | 251 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 makefile |   1 +
 2 files changed, 252 insertions(+)
 create mode 100644 13.c

diff --git a/13.c b/13.c
new file mode 100644
index 0000000..5bee612
--- /dev/null
+++ b/13.c
@@ -0,0 +1,251 @@
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+struct node {
+	int val_int;
+	struct node * val_list;
+	struct node * next;
+};
+
+
+struct node list_empty = { 0, &list_empty, NULL };
+
+struct node * const LIST_EMPTY = &list_empty;
+
+
+struct node *
+node_create_int(int i)
+{
+	struct node * n = malloc(sizeof(struct node));
+	if (!n)
+		return NULL;
+	n->val_list = NULL;
+	n->val_int = i;
+	n->next = NULL;
+	return n;
+}
+
+
+struct node *
+node_create_list(struct node * list)
+{
+	struct node * n = malloc(sizeof(struct node));
+	if (!n)
+		return NULL;
+	n->val_list = list ? list : LIST_EMPTY;
+	n->val_int = 0;
+	n->next = NULL;
+	return n;
+}
+
+
+void
+node_free(struct node * n)
+{
+	if (!n || n == LIST_EMPTY)
+		return;
+	node_free(n->val_list);
+	node_free(n->next);
+	free(n);
+	return;
+}
+
+
+int
+node_isint(struct node const * n)
+{
+	return n->val_list == NULL;
+}
+
+
+int
+node_islist(struct node const * n)
+{
+	return n->val_list != NULL;
+}
+
+
+void
+node_dump(struct node * n)
+{
+	fputc('[', stderr);
+
+	while (n && n != LIST_EMPTY) {
+		if (node_isint(n))
+			fprintf(stderr, "%d", n->val_int);
+		else
+			node_dump(n->val_list);
+
+		if (n->next)
+			fputc(',', stderr);
+
+		n = n->next;
+	}
+
+	fputc(']', stderr);
+}
+
+
+int
+node_cmp(struct node * l, struct node * r)
+{
+	while (l && r) {
+		int ret;
+
+		if (node_isint(l) && node_isint(r)) {
+			ret = l->val_int - r->val_int;
+		}
+		else if (node_isint(l)) {
+			struct node * tmp = node_create_list(l);
+			ret = node_cmp(tmp, r);
+			free(tmp); // Not node_free(), because we don't want to delete the contents
+		}
+		else if (node_isint(r)) {
+			struct node * tmp = node_create_list(r);
+			ret = node_cmp(l, tmp);
+			free(tmp); // Not node_free(), because we don't want to delete the contents
+		}
+		else if (l == LIST_EMPTY && r == LIST_EMPTY) {
+			return 0;
+		}
+		else if (l == LIST_EMPTY) {
+			return -1000;
+		}
+		else if (r == LIST_EMPTY) {
+			return 1000;
+		}
+		else {
+			ret = node_cmp(l->val_list, r->val_list);
+		}
+
+		if (ret != 0)
+			return ret;
+
+		l = l->next;
+		r = r->next;
+	}
+
+	if (!l && !r)
+		// Lists were same length
+		return 0;
+
+	return l ? 2000 : -2000;
+}
+
+
+struct node *
+node_parse(char ** ppch)
+{
+	char * pch = *ppch;
+	struct node * head = NULL, * tail = NULL;
+
+	while (*pch != '\0') {
+		struct node * n = NULL;
+
+		while (isspace(*pch))
+			++pch;
+
+		if (isdigit(*pch)) {
+			n = node_create_int(strtol(pch, &pch, 10));
+		}
+		else if (*pch == '[') {
+			++pch;
+			n = node_create_list(node_parse(&pch));
+		}
+		else if (*pch == ']') {
+			*ppch = ++pch;
+			return head ? head : LIST_EMPTY;
+		}
+		else {
+			*ppch = pch;
+			node_free(head);
+			return NULL;
+		}
+
+		if (head && tail) {
+			tail->next = n;
+			tail = n;
+		}
+		else {
+			head = tail = n;
+		}
+
+		while (isspace(*pch))
+			++pch;
+		if (*pch == ',')
+			++pch;
+	}
+
+	*ppch = pch;
+	return head;
+}
+
+
+int
+main()
+{
+	struct node * packets = NULL, * last = NULL, * n;
+	char buf[BUFSIZ];
+	int index_sum = 0, i;
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		char * pch;
+
+		if (buf[0] == '\n' || buf[0] == '\0')
+			continue;
+
+		pch = buf;
+		n = node_parse(&pch);
+		if (!n && pch == buf) {
+			fprintf(stderr, "Invalid input\n");
+			node_free(packets);
+			return -1;
+		}
+		if (!n)	// Just whitespace or whatever
+			continue;
+		if (!node_islist(n)) {
+			fprintf(stderr, "Got a packet that's not a list?\n");
+			node_dump(n); fputc('\n', stderr);
+			free(n);
+			node_free(packets);
+			return -1;
+		}
+
+		if (last) {
+			last->next = n;
+			last = n;
+		}
+		else {
+			packets = last = n;
+		}
+	}
+
+	for (n = packets, i = 1; n != NULL && n->next != NULL; n = n->next->next, ++i) {
+		int j;
+
+		if ((j = node_cmp(n, n->next)) < 0) {
+			index_sum += i;
+		}
+#if 1
+		node_dump(n); fputc('\n', stderr);
+		node_dump(n->next); 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);
+		}
+	}
+
+	printf("Index sum: %d\n", index_sum);
+
+	node_free(packets);
+
+	return 0;
+}
+
diff --git a/makefile b/makefile
index ec3e374..05247f8 100644
--- a/makefile
+++ b/makefile
@@ -14,6 +14,7 @@ all: bin \
 	bin/10 \
 	bin/11 \
 	bin/12 \
+	bin/13 \
 
 bin:
 	mkdir -p $@
-- 
cgit v1.2.1