aoc15_7.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_NAME 7
#define NAME_FMT "%7[a-z] "
#define ALPHABET_SIZE 26
#define IS_ALPHA(c) ((c) >= 'a' && (c) <= 'z')
#define TO_INDEX(c) ((c)-'a')
#define NAME_SIZE (MAX_NAME+1)

struct operand {
	enum {
		NUMBER,
		VARIABLE
	} type;
	union {
		unsigned value;
		char name[NAME_SIZE];
	};
};

struct expr {
	enum {
		NOT,
		AND,
		OR,
		LSHIFT,
		RSHIFT,
		NONE
	} op;
	struct operand lhs, rhs;
	unsigned result;
	int cached;
};

static int last_modified;

static void put(const char *, const struct expr *);
static struct expr *get(const char *);
static int eval(struct expr *);

static int
parse_operand(struct operand *x) {
	int c;

	c = getchar();
	if (c == EOF)
		return EOF;

	ungetc(c, stdin);

	if (c >= '0' && c <= '9') {
		assert(scanf("%u ", &x->value) == 1);
		x->type = NUMBER;
	}
	else if (IS_ALPHA(c)) {
		assert(scanf(NAME_FMT, x->name) == 1);
		x->type = VARIABLE;
	}
	else {
		return 0;
	}

	return 1;
}

static int
parse_operator(struct expr *e) {
	int c;

	c = getchar();
	assert(c != EOF);
	ungetc(c, stdin);

	switch (c) {
	case 'N':
		assert(scanf("NOT ") == 0);
		e->op = NOT;
		break;
	case 'A':
		assert(scanf("AND ") == 0);
		e->op = AND;
		break;
	case 'O':
		assert(scanf("OR ") == 0);
		e->op = OR;
		break;
	case 'L':
		assert(scanf("LSHIFT ") == 0);
		e->op = LSHIFT;
		break;
	case 'R':
		assert(scanf("RSHIFT ") == 0);
		e->op = RSHIFT;
		break;
	default:
		return 0;
	}

	return 1;
}

static int
parse(struct expr *e) {
	if (parse_operand(&e->lhs) == EOF)
		return 0;

	if (parse_operator(e)) {
		assert(parse_operand(&e->rhs) != EOF);
	}
	else {
		e->op = NONE;
		e->rhs = e->lhs;
	}

	e->cached = 0;
	return 1;
}

static void
parse_input(void) {
	char name[NAME_SIZE];
	struct expr buf;

	while (parse(&buf)) {
		assert(scanf("-> " NAME_FMT, name) == 1);
		put(name, &buf);
	}
}

static int
eval_operand(const struct operand *x) {
	struct expr *e;

	switch (x->type) {
	case NUMBER:
		return x->value;
	case VARIABLE:
		e = get(x->name);
		assert(e != NULL);
		return eval(e);
	}
}

static int
eval(struct expr *e) {
	unsigned lhs, rhs;
	unsigned result;

	if (e->cached > last_modified)
		return e->result;

	switch (e->op) {
	case AND:
	case OR:
	case LSHIFT:
	case RSHIFT:
		lhs = eval_operand(&e->lhs);
	default:
		rhs = eval_operand(&e->rhs);
	}

	switch (e->op) {
	case NOT:
		result = ~rhs;
		break;
	case AND:
		result = lhs & rhs;
		break;
	case OR:
		result = lhs | rhs;
		break;
	case LSHIFT:
		result = lhs << rhs;
		break;
	case RSHIFT:
		result = lhs >> rhs;
		break;
	case NONE:
		result = rhs;
		break;
	}

	result &= 65535;
	e->result = result;
	e->cached = last_modified+1;
	return result;
}

int
main(void) {
	struct expr *a, *b;

	parse_input();

	a = get("a");
	assert(a != NULL);
	printf("%u\n", eval(a));

	b = get("b");
	assert(b != NULL);
	b->op = NONE;
	b->rhs.type = NUMBER;
	b->rhs.value = eval(a);
	last_modified++;
	printf("%u\n", eval(a));
}

struct node {
	struct node *children[ALPHABET_SIZE];
	int is_terminal;
	struct expr value;
};

static struct node root;

static void
put(const char *name, const struct expr *value) {
	const char *p;
	struct node *v, *u;
	struct node **e;
	size_t i;

	v = &root;
	for (p = name; *p; p++) {
		e = &v->children[TO_INDEX(*p)];
		if (!*e) {
			u = malloc(sizeof *u);
			assert(u != NULL);

			for (i = 0; i < ALPHABET_SIZE; i++)
				u->children[i] = NULL;

			u->is_terminal = 0;
			*e = u;
		}

		v = *e;
	}

	v->is_terminal = 1;
	v->value = *value;
}

static struct expr *
get(const char *name) {
	const char *p;
	struct node *v;

	v = &root;
	for (p = name; *p; p++) {
		v = v->children[TO_INDEX(*p)];
		if (!v)
			return NULL;
	}

	if (v->is_terminal)
		return &v->value;
	else
		return NULL;
}