Solve puzzle 21 part 1

2 files changed, 216 insertions, 0 deletions

diff --git a/21.c b/21.c
new file mode 100644
index 0000000..b1eebd4
--- /dev/null
+++ b/21.c
@@ -0,0 +1,215 @@
+
+//#define _GNU_SOURCE
+
+#include <regex.h>
+#include <search.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#define arrlen(x) (sizeof(x)/sizeof((x)[0]))
+
+
+enum operation {
+	OP_VAL,
+	OP_ADD,
+	OP_SUB,
+	OP_MUL,
+	OP_DIV,
+};
+
+
+enum operation
+operation_get(char op)
+{
+	switch (op) {
+	case '+': return OP_ADD;
+	case '-': return OP_SUB;
+	case '*': return OP_MUL;
+	case '/': return OP_DIV;
+	}
+	return OP_VAL;
+}
+
+
+struct monkey {
+	char name[5];
+	enum operation op;
+	long value;
+	char left[5];
+	char right[5];
+};
+
+
+struct monkey *
+monkey_create_val(char const * name, long value)
+{
+	struct monkey * m;
+
+	if (!name || strlen(name) != 4)
+		return NULL;
+
+	if ((m = malloc(sizeof(struct monkey))) == NULL)
+		return NULL;
+
+	snprintf(m->name, sizeof(m->name), "%s", name);
+	m->op = OP_VAL;
+	m->value = value;
+	m->left[0] = '\0';
+	m->right[0] = '\0';
+	return m;
+}
+
+
+struct monkey *
+monkey_create_op(char const * name, enum operation op, char const * left, char const * right)
+{
+	struct monkey * m;
+
+	if (!name || strlen(name) != 4
+			|| op == OP_VAL
+			|| !left || strlen(left) != 4
+			|| !right || strlen(right) != 4)
+		return NULL;
+
+	if ((m = malloc(sizeof(struct monkey))) == NULL)
+		return NULL;
+
+	snprintf(m->name, sizeof(m->name), "%s", name);
+	m->op = op;
+	m->value = 0;
+	snprintf(m->left, sizeof(m->left), "%s", left);
+	snprintf(m->right, sizeof(m->right), "%s", right);
+	return m;
+}
+
+
+int
+monkey_cmp(struct monkey const * a, struct monkey const * b)
+{
+	return strcmp(a->name, b->name);
+}
+
+
+int
+monkey_cmp_t(void const * a, void const * b)
+{
+	return monkey_cmp(a, b);
+}
+
+
+struct monkey *
+monkey_find(void * monkey_tree, char const * name)
+{
+	struct monkey tmp, ** result;
+
+	if (!name || strlen(name) != 4) {
+		fprintf(stderr, "Invalid monkey name %s\n", name ? name : "(null)");
+		return NULL;
+	}
+
+	snprintf(tmp.name, sizeof(tmp.name), "%s", name);
+	result = tfind(&tmp, &monkey_tree, monkey_cmp_t);
+	return result ? *result : NULL;
+}
+
+
+long
+monkey_value(void * monkey_tree, struct monkey * m)
+{
+	long v;
+
+	if (!m) {
+		fprintf(stderr, "%s: Bad monkey\n", __FUNCTION__);
+		return 0;
+	}
+
+	switch (m->op) {
+	case OP_VAL:
+		v = m->value;
+		break;
+
+	case OP_ADD:
+		v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left))
+			+ monkey_value(monkey_tree, monkey_find(monkey_tree, m->right));
+		break;
+
+	case OP_SUB:
+		v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left))
+			- monkey_value(monkey_tree, monkey_find(monkey_tree, m->right));
+		break;
+
+	case OP_MUL:
+		v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left))
+			* monkey_value(monkey_tree, monkey_find(monkey_tree, m->right));
+		break;
+
+	case OP_DIV:
+		v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left))
+			/ monkey_value(monkey_tree, monkey_find(monkey_tree, m->right));
+		break;
+
+	default:
+		fprintf(stderr, "Unexpected operation for %s: %d\n", m->name, m->op);
+		return 0;
+	}
+
+	return v;
+}
+
+
+int
+main()
+{
+	regex_t reval, reop;
+	char buf[BUFSIZ];
+	void * monkey_tree = NULL;
+
+	if (regcomp(&reval, "([[:alpha:]]{4}): (-?[[:digit:]]+)", REG_EXTENDED) != 0
+			|| regcomp(&reop, "([[:alpha:]]{4}): ([[:alpha:]]{4}) ([-+*/]) ([[:alpha:]]{4})", REG_EXTENDED) != 0)
+	{
+		fprintf(stderr, "Bad regex\n");
+		return -1;
+	}
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		regmatch_t matches[5];
+		struct monkey * m;
+
+		if (regexec(&reval, buf, arrlen(matches), matches, 0) == 0) {
+			buf[matches[1].rm_eo] = '\0';
+			m = monkey_create_val(buf + matches[1].rm_so, atoi(buf + matches[2].rm_so));
+		}
+		else if (regexec(&reop, buf, arrlen(matches), matches, 0) == 0) {
+			buf[matches[1].rm_eo] = '\0';
+			buf[matches[2].rm_eo] = '\0';
+			buf[matches[4].rm_eo] = '\0';
+			m = monkey_create_op(buf + matches[1].rm_so,
+					operation_get(buf[matches[3].rm_so]),
+					buf + matches[2].rm_so,
+					buf + matches[4].rm_so);
+		}
+		else {
+			fprintf(stderr, "Bad monkey: %s\n", buf);
+			regfree(&reop);
+			regfree(&reval);
+			return -1;
+		}
+
+		tsearch(m, &monkey_tree, monkey_cmp_t);
+	}
+
+
+
+	printf("root value: %ld\n", monkey_value(monkey_tree, monkey_find(monkey_tree, "root")));
+
+#ifdef _GNU_SOURCE
+	tdestroy(monkey_tree, free);
+#endif
+	regfree(&reop);
+	regfree(&reval);
+
+	return 0;
+}
+
diff --git a/makefile b/makefile
index 819be29..90dd39f 100644
--- a/makefile
+++ b/makefile
@@ -22,6 +22,7 @@ all: bin \
 	bin/18 \
 	bin/19 \
 	bin/20 \
+	bin/21 \
 
 bin:
 	mkdir -p $@