Solve puzzle 11 part 1

1 files changed, 230 insertions, 0 deletions

diff --git a/11.c b/11.c
new file mode 100644
index 0000000..ec06772
--- /dev/null
+++ b/11.c
@@ -0,0 +1,230 @@
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+enum worry_op {
+	WO_NONE,
+	WO_ADD,
+	WO_MUL,
+	WO_SQR,
+};
+
+
+struct monkey {
+	int * items;
+	int nitems;
+	enum worry_op wo;
+	int wparam;
+	int test_div;
+	int test_true;
+	int test_false;
+	int inspections;
+};
+
+
+void
+monkey_init(struct monkey * m)
+{
+	m->items = NULL;
+	m->nitems = 0;
+	m->wo = WO_NONE;
+	m->wparam = 0;
+	m->test_div = 0;
+	m->test_true = 0;
+	m->test_false = 0;
+	m->inspections = 0;
+}
+
+
+void
+monkey_dtor(struct monkey * m)
+{
+	free(m->items);
+}
+
+
+int
+monkey_isvalid(struct monkey const * m, int max)
+{
+	return m->wo != WO_NONE
+		&& m->test_div != 0
+		&& m->test_true >= 0 && m->test_true < max
+		&& m->test_false >= 0 && m->test_false < max;
+}
+
+
+int
+monkey_additem(struct monkey * m, int worry)
+{
+	void * p;
+
+	++m->nitems;
+	p = realloc(m->items, m->nitems * sizeof(int));
+	if (!p)
+		return 0;
+	m->items = p;
+	m->items[m->nitems - 1] = worry;
+	return 1;
+}
+
+
+void
+monkey_dump(struct monkey const * m, int n)
+{
+	int * i;
+
+	fprintf(stderr, "Monkey %d: %d/%d/%d/%d/%d/%d: ",
+			n, m->wo, m->wparam, m->test_div, m->test_true, m->test_false, m->inspections);
+	for (i = m->items; i < m->items + m->nitems; ++i) {
+		fprintf(stderr, "%s%d", i == m->items ? "" : ", ", *i);
+	}
+	fprintf(stderr, "\n");
+}
+
+
+int
+main()
+{
+	char buf[BUFSIZ];
+	struct monkey * monkeys = NULL, * m = NULL;
+	int nmonkeys = 0;
+	int i, j;
+
+	// Read monkey data
+	while (fgets(buf, sizeof(buf), stdin)) {
+		if (buf[0] == '\n') {
+			// Ignore blank line
+		}
+		else if (strncmp(buf, "Monkey ", 7) == 0 && isdigit(buf[7])) {
+			void * p;
+
+			++nmonkeys;
+
+			if ((i = atoi(buf + 7)) != nmonkeys - 1) {
+				fprintf(stderr, "Bad monkey %d/%d!\n", i, nmonkeys);
+				free(monkeys);
+				return -1;
+			}
+			p = realloc(monkeys, nmonkeys * sizeof(struct monkey));
+			if (!p) {
+				fprintf(stderr, "realloc(%zd) fail\n", nmonkeys * sizeof(struct monkey));
+				free(monkeys);
+				return -1;
+			}
+			monkeys = p;
+			m = monkeys + nmonkeys - 1;
+			monkey_init(m);
+		}
+		else if (strncmp(buf, "  Starting items: ", 18) == 0 && isdigit(buf[18])) {
+			char * cur, * next;
+			int worry;
+
+			cur = buf + 18;
+			worry = strtol(cur, &next, 10);
+			while (next != cur) {
+				monkey_additem(m, worry);
+				cur = next + 1;
+				worry = strtol(cur, &next, 10);
+			}
+		}
+		else if (strncmp(buf, "  Operation: new = old ", 23) == 0) {
+			switch (buf[23]) {
+			case '+': m->wo = WO_ADD; break;
+			case '*': m->wo = WO_MUL; break;
+			default:
+				  fprintf(stderr, "Unexpected op %c\n", buf[23]);
+				  free(monkeys);
+				  return -1;
+			}
+			if (strncmp(buf + 25, "old", 3) == 0 && m->wo == WO_MUL) {
+				m->wo = WO_SQR;
+			}
+			else {
+				m->wparam = atoi(buf + 25);
+			}
+		}
+		else if (strncmp(buf, "  Test: divisible by ", 21) == 0 && isdigit(buf[21])) {
+			m->test_div = atoi(buf + 21);
+		}
+		else if (strncmp(buf, "    If true: throw to monkey ", 29) == 0 && isdigit(buf[29])) {
+			m->test_true = atoi(buf + 29);
+		}
+		else if (strncmp(buf, "    If false: throw to monkey ", 30) == 0 && isdigit(buf[30])) {
+			m->test_false = atoi(buf + 30);
+		}
+		else {
+			fprintf(stderr, "Unexpected monkey: %s\n", buf);
+			free(monkeys);
+			return -1;
+		}
+	}
+
+	// Check monkeys are valid
+	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
+#if 0
+		monkey_dump(m, m - monkeys);
+#endif
+		if (!monkey_isvalid(m, nmonkeys)) {
+			fprintf(stderr, "Bad monkey %d\n", (int) (m - monkeys));
+			monkey_dump(m, m - monkeys);
+			free(monkeys);
+			return -1;
+		}
+	}
+
+	// Perform monkey inspection rounds
+	for (i = 0; i < 20; ++i) {
+		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
+			int * item;
+
+			for (item = m->items; item < m->items + m->nitems; ++item) {
+				int catcher;
+
+				switch (m->wo) {
+				case WO_NONE: break; /* shouldn't happen */
+				case WO_ADD: *item += m->wparam; break;
+				case WO_MUL: *item *= m->wparam; break;
+				case WO_SQR: *item *= *item; break;
+				}
+				*item /= 3;
+
+				catcher = *item % m->test_div ? m->test_false : m->test_true;
+				monkey_additem(monkeys + catcher, *item);
+
+				++m->inspections;
+			}
+			m->nitems = 0;
+		}
+
+#if 0
+		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
+			monkey_dump(m, m - monkeys);
+		}
+#endif
+	}
+
+	// Calculate monkey business
+	i = j = 0;
+	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
+		if (m->inspections > i) {
+			j = i;
+			i = m->inspections;
+		}
+		else if (m->inspections > j) {
+			j = m->inspections;
+		}
+	}
+	printf("Monkey business: %d (%d * %d)\n", i * j, i, j);
+
+	// Done.
+	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
+		monkey_dtor(m);
+	}
+	free(monkeys);
+
+	return 0;
+}
+