#include "common.h"

/*
 * The approach behind part 2 was to essentially write a bunch of
 * validation rules for the structure of the adder, and then writing
 * fixups for problems it would find. That means it's likely quite
 * tailored to my input, but at least it's not hardcoding manual graph
 * analysis.
 */

enum { W_NULL, W_OFF, W_ON };

struct wire;

struct wire {
	struct wire *in[2];
	char name[4];
	char op; 		/* [A]ND, [O]R, [X]OR */
	int8_t val;		/* W_NULL, W_OFF, W_ON */
};

static struct wire wires[320];
static struct wire *zs[46], *swapped[8];
static int nw, nsw;

static struct wire *
get_wire(const char *name)
{
	int i;

	for (i=0; i<nw; i++)
		if (!strcmp(name, wires[i].name))
			return &wires[i];

	assert(nw < (int)LEN(wires));
	assert(strlen(name) < LEN(wires[i].name));

	snprintf(wires[nw].name, sizeof(wires[nw].name), "%s", name);
	return &wires[nw++];
}


static int
cmp_wires(const void *a, const void *b)
{
	struct wire * const *wa = a;
	struct wire * const *wb = b;

	return strcmp((*wa)->name, (*wb)->name);
}

static int
eval(struct wire *wire)
{
	int in1,in2;

	if (wire->val)
		return wire->val == W_ON;

	assert(wire->in[0]);
	assert(wire->in[1]);

	in1 = eval(wire->in[0]);
	in2 = eval(wire->in[1]);

	wire->val = W_OFF + (
	    wire->op=='A' ? in1 && in2 :
	    wire->op=='O' ? in1 || in2 :
	    wire->op=='X' ? in1 != in2 : (assert(!"bad op"), -1));

	return wire->val == W_ON;
}

static void
swap(struct wire *a, struct wire *b)
{
	struct wire tmp;

	//printf("swapping %s and %s\n", a->name, b->name);

	tmp = *a;

	a->op = b->op;
	a->in[0] = b->in[0];
	a->in[1] = b->in[1];

	b->op = tmp.op;
	b->in[0] = tmp.in[0];
	b->in[1] = tmp.in[1];

	assert(nsw+2 <= (int)LEN(swapped));
	swapped[nsw++] = a;
	swapped[nsw++] = b;
}

static struct wire *
find_z_xor(int bit)
{
	struct wire *xy_xor;
	int i;

	for (i=0; i<nw; i++) {
		 /* must be a XOR */
		if (wires[i].op != 'X')
			continue;

		 /* with an input XOR */
		xy_xor = wires[i].in[0]->op == 'X' ? wires[i].in[0] :
		         wires[i].in[1]->op == 'X' ? wires[i].in[1] :
		         NULL;
		if (!xy_xor)
			continue;

		 /* connected to the X and Y */
		if (xy_xor->in[0]->name[0] != 'x' &&
		    xy_xor->in[0]->name[0] != 'y')
			continue;

		 /* with the same bit number */
		if (atoi(xy_xor->in[0]->name+1) != bit)
			continue;

		return &wires[i];
	}

	return NULL;
}

static struct wire *
find_xy_and(int bit)
{
	int i;

	for (i=0; i<nw; i++) {
		 /* must be AND */
		if (wires[i].op != 'A')
			continue;

		 /* must have XY inputs */
		if ((wires[i].in[0]->name[0] != 'x'  ||
		     wires[i].in[1]->name[0] != 'y') &&
		    (wires[i].in[0]->name[0] != 'y'  ||
		     wires[i].in[1]->name[0] != 'x'))
			continue;
		
		 /* with the right bit number */
		if (atoi(wires[i].in[0]->name+1) != bit ||
		    atoi(wires[i].in[0]->name+1) != bit)
			continue;
		
		return &wires[i];
	}

	return NULL;
}

static void
fsck_carry_or(struct wire *or, int bit)
{
	struct wire *wire;
	int i;

	 /* both inputs must be AND; no fixup if neither */
	assert(
	    or->in[0]->op == 'A' ||
	    or->in[1]->op == 'A');

	for (i=0; i<2; i++) {
		if (or->in[i]->op == 'A')
			continue;

		//printf("carry OR parent %s not AND\n", or->in[i]->name);

		 /* only have fixup for the XY AND */
		assert(
		    or->in[!i]->in[0]->name[0] != 'x' &&
		    or->in[!i]->in[0]->name[0] != 'y');

		wire = find_xy_and(bit);
		assert(wire);
		swap(or->in[i], wire);
	}
}

static void
fsck_z(struct wire *z)
{
	struct wire *wire, *carry_or;
	int bit;

	assert(z->name[0] == 'z');

	bit = atoi(z->name+1);

	 /* first bit is very different */
	if (!bit)
		return;

	 /* for the final bit, Z is the carry OR */
	if (!zs[bit+1]) {
		 /* no fixup if it isn't */
		assert(z->op == 'O');

		fsck_carry_or(z, bit-1);
		return;
	}

	 /* must be a XOR */
	if (z->op != 'X') {
		//printf("Z %s isn't XOR\n", z->name);
		wire = find_z_xor(bit);
		assert(wire);
		swap(z, wire);
	}

	 /* bit 2 and up must have a carry OR */
	if (bit > 1) {
		carry_or =
		    z->in[0]->op == 'O' ? z->in[0] :
		    z->in[1]->op == 'O' ? z->in[1] : NULL;
		assert(carry_or);
		fsck_carry_or(carry_or, bit-1);
	}
}

int
main(int argc, char **argv)
{
	struct wire *wire;
	char buf[64], *rest, *lf, *name1,*name2, *opstr;
	uint64_t p1=0;
	int bit, i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		if (!strchr(buf, ':'))
			break;

		wire = get_wire(strsep(&rest, ":"));
		wire->val = W_OFF + atoi(rest);

	}

	while ((rest = fgets(buf, sizeof(buf), stdin))) {
		if ((lf = strchr(buf, '\n')))
			*lf = '\0';

		name1 = strsep(&rest, " ");
		opstr = strsep(&rest, " ");
		name2 = strsep(&rest, " ");
		strsep(&rest, " ");

		wire = get_wire(rest);
		wire->in[0] = get_wire(name1);
		wire->in[1] = get_wire(name2);
		wire->op = opstr[0];
	}

	for (i=0; i<nw; i++)
		if (wires[i].name[0] == 'z') {
			bit = atoi(&wires[i].name[1]);
			assert(bit >= 0);
			assert(bit < (int)LEN(zs));
			zs[bit] = &wires[i];
		}

	for (i=0; i < (int)LEN(zs); i++)
		if (zs[i])
			p1 |= (uint64_t)eval(zs[i]) << i;

	for (i=0; i < (int)LEN(zs); i++)
		if (zs[i])
			fsck_z(zs[i]);

	qsort(swapped, nsw, sizeof(*swapped), cmp_wires);

	printf("24: %"PRIu64, p1);

	for (i=0; i<nsw; i++)
		printf(i ? ",%s" : " %s", swapped[i]->name);

	putchar('\n');
	return 0;
}