#include "common.h"

int
main(int argc, char **argv)
{
	static char buf[7];
	static short h[500][5];	/* heights */
	static short iskey[500];
	int p1=0, nh=0, i,j,k;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	for (nh=0; !feof(stdin) && !ferror(stdin); nh++) {
		assert(nh < (int)LEN(h));

		for (i=0; i<7; i++) {
			fgets(buf, 7, stdin);
			if (i==0)
				iskey[nh] = buf[0] == '#';
			for (j=0; j<5; j++)
				h[nh][j] += buf[j] == '#';
		}

		/* skip empty line */
		fgets(buf, 7, stdin);
	}

	for (i=0; i<nh; i++)
	for (j=0; j<nh; j++)
		if (iskey[i] && !iskey[j]) {
			for (k=0; k<5 && h[i][k] + h[j][k] <= 7; k++) ;
			p1 += k == 5;
		}

	printf("25: %d\n", p1);
	return 0;
}

#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;
}

#include "common.h"

#define STEPS	2000
#define NCODES	(19*19*19*19)

int
main(int argc, char **argv)
{
	static int8_t prices[STEPS];
	static int8_t by_deltas[NCODES];
	static int sums[NCODES];

	uint64_t p1=0, secret;
	int p2=0, i;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (scanf(" %"SCNu64, &secret) == 1) {
		memset(by_deltas, 0, sizeof(by_deltas));

		for (i=0; i<STEPS; i++) {
			secret = (secret ^ secret << 6)  & 0xFFFFFF;
			secret = (secret ^ secret >> 5);
			secret = (secret ^ secret << 11) & 0xFFFFFF;

			prices[i] = secret % 10;
		}

		/*
		 * Build a deltas->price map for the buyer. Deltas are
		 * encoded as an integer for easy indexing. Iterating
		 * backwards ensures the stored price is the _earliest_
		 * occurence of that sequence.
		 */
		for (i=STEPS-1; i>=4; i--)
			by_deltas[
			    (prices[i-3] - prices[i-4] +9) *19*19*19 +
			    (prices[i-2] - prices[i-3] +9) *19*19 +
			    (prices[i-1] - prices[i-2] +9) *19 +
			    (prices[i]   - prices[i-1] +9)
			] = prices[i];

		for (i=0; i<NCODES; i++)
			sums[i] += by_deltas[i];

		p1 += secret;
	}

	for (i=0; i<NCODES; i++)
		p2 = MAX(p2, sums[i]);

	printf("22: %"PRIu64" %d\n", p1, p2);
	return 0;
}

#include "common.h"

#define VZ 520	/* max no. vertices */
#define SZ 32	/* max set size */

static char names[VZ][3];
static char adj[VZ][VZ];
static int nvert;

static int
to_id(const char *name)
{
	int i;

	for (i=0; i<nvert; i++)
		if (!strcmp(name, names[i]))
			return i;

	assert(nvert < VZ);
	assert(strlen(name) < LEN(*names));

	snprintf(names[nvert++], sizeof(*names), "%s", name);
	return i;
}

static int
cmp_id(const void *a, const void *b)
{
	return strcmp(names[*(int*)a], names[*(int*)b]);
}

/*
 * Construct all unique combinations of nodes, with every extension,
 * confirm they're all connected. Essentally this but recursive:
 *
 *   for (a=0; a<nvert; a++)
 *   for (b=a+1; b<nvert; b++)
 *   for (c=b+1; c<nvert; c++)
 *     ...
 *
 * Note the inner loops continue forward from the point of the outside
 * loop, avoiding duplicate combinations.
 *
 * 'set' and 'best' are arrays of size SZ, length 'sz' and 'bz'. 'set'
 * is the current working state; 'best' is a copy of the longest known
 * set.
 */
static int
max_set(int *set, int sz, int *best, int bz)
{
	int bz1, v,i;

	assert(sz < SZ);

	/* for each potential candidate */
	for (v = sz ? set[sz-1]+1 : 0; v < nvert; v++) {
		 /* adjacent to all in current set? */
		for (i=0; i<sz && adj[set[i]][v]; i++) ;
		if (i != sz) continue;
		 /* recur and update 'best size' if needed */
		set[sz] = v;
		if (bz < (bz1 = max_set(set, sz+1, best, bz))) bz = bz1;
	}

	/* store longest known set in 'best' */
	if (sz > bz)
		memcpy(best, set, (bz = sz) * sizeof(*best));

	return bz;
}

int
main(int argc, char **argv)
{
	static int set[SZ], best[SZ];
	char buf[8];
	int p1=0, a,b,c, i, bz;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		assert(strlen(buf) >= 5);
		buf[2] = buf[5] = '\0';
		a = to_id(buf);
		b = to_id(buf+3);
		adj[a][b] = adj[b][a] = 1;
	}

	for (a=0; a<nvert; a++)
	for (b=a+1; b<nvert; b++)
	for (c=b+1; c<nvert; c++)
		p1 += adj[a][b] && adj[a][c] && adj[b][c] && (
		      names[a][0] == 't' || names[b][0] == 't' ||
		      names[c][0] == 't');

	printf("23: %d ", p1);

	bz = max_set(set, 0, best, 0);
	qsort(best, bz, sizeof(*best), cmp_id);

	for (i=0; i<bz; i++)
		printf(i ? ",%s" : "%s", names[best[i]]);

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

#include "common.h"

static int64_t dpmem[26][8][2];

enum {NW,NN,NE,EE,SE,SS,SW,WW};

/*
 * We can sufficiently describe npad/dpad movements as: "move N x, N y,
 * then press A N times" (a 'move'). It's never faster to take a detour.
 * After pressing A on one dpad, dpads on all levels above will also be
 * on A, so these moves can be considered in isolation.
 *
 * This function gives the cost of executing a move with the dpad in
 * direction 'd' at level 'l', excluding the A presses for actually
 * tapping the selected directions, but including returning the cursor
 * back to the A button.
 *
 * E.g., moving 2 up and 3 left (NW), the steps could be <AAv<AAA>>^.
 * Excluding the A presses, that's 6 steps. Pulling out the A presses
 * lets us drop the dx and dy arguments and simplify the memoization.
 * They're easily calculated: it's |dx|+|dy|.
 *
 * The gaps present a problem: picking the lowest-cost option (e.g.
 * left-then-up vs. up-then-left) may cause us to cross a gap. The
 * "mind the gap" argument 'mtg' must be set to 1 if-and-only-if there
 * is such potential, e.g. a move from < to ^ on the dpad (up,right
 * crosses the gap) or a move from A to 1 on the npad (left,up crosses
 * the gap). With the flag set, these orderings will be avoided.
 */
static int64_t
dp(int d, int mtg, int l)
{
	int64_t ret, alt=INT64_MAX;

	if (l<=0)
		return 0;
	
	assert(l >= 0);
	assert(l < (int)LEN(dpmem));
	assert(mtg==0 || mtg==1);

	if ((ret = dpmem[l][d][mtg]))
		return ret;

	/* routes avoiding gaps where necessary */
	ret = d==SE ? 1+dp(SS,0,l-1) + 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) :
	      d==SW ? 2+dp(SW,0,l-1) + 1+dp(WW,0,l-1) + 3+dp(NE,1,l-1) :
	      d==SS ? 2+dp(SW,0,l-1) + 2+dp(NE,0,l-1) :
	      d==NE ? 1+dp(SS,0,l-1) + 2+dp(NW,0,l-1) + 1+dp(EE,0,l-1) :
	      d==NW ? 1+dp(WW,0,l-1) + 2+dp(SW,1,l-1) + 3+dp(NE,1,l-1) :
	      d==NN ? 1+dp(WW,0,l-1) + 1+dp(EE,0,l-1) :
	      d==EE ? 1+dp(SS,0,l-1) + 1+dp(NN,0,l-1) :
	      d==WW ? 3+dp(SW,1,l-1) + 3+dp(NE,1,l-1) :
	      (assert(!"bad dir"), -1);

	/* alternatives crossing the gaps */
	alt = mtg ? INT64_MAX :
	      d==SE ? 2+dp(SW,0,l-1) + 1+dp(EE,0,l-1) + 1+dp(NN,0,l-1) :
	      d==SW ? 3+dp(SW,1,l-1) + 1+dp(EE,0,l-1) + 2+dp(NE,0,l-1) :
	      d==NE ? 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) + 1+dp(NN,0,l-1) :
	      d==NW ? 3+dp(SW,1,l-1) + 2+dp(NE,1,l-1) + 1+dp(EE,0,l-1) :
	      INT64_MAX;

	return dpmem[l][d][mtg] = MIN(ret, alt);
}

static int64_t
npcost(const char *s, int lv)
{
	int64_t cost=0;
	int x=2,y=3, x1,y1, mtg, dir;

	for (; *s == 'A' || (*s >= '0' && *s <= '9'); s++) {
		x1 = *s=='A' ? 2 : *s=='0' ? 1 : 2-(9-*s+'0') % 3;
		y1 = *s=='A' ? 3 : *s=='0' ? 3 :   (9-*s+'0') / 3;

		/* potentially crossing a gap? */
		mtg = (x==0 && y1==3) || (x1==0 && y==3);

		dir = y1>y ? (x1>x ? SE : x1<x ? SW : SS) :
		      y1<y ? (x1>x ? NE : x1<x ? NW : NN) :
		             (x1>x ? EE : x1<x ? WW : 0);

		cost += dp(dir, mtg, lv) + abs(x1-x) + abs(y1-y) +1;

		x = x1;
		y = y1;
	}

	return cost;
}

int
main(int argc, char **argv)
{
	char buf[8];
	int digits;
	int64_t p1=0,p2=0;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		digits = atoi(buf);
		p1 += digits * npcost(buf, 2);
		p2 += digits * npcost(buf, 25);
	}

	printf("21: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}

#include "common.h"

#define GB 2	/* safety border on X/Y plane */
#define GZ (GB+141+2+GB)

static char G[GZ][GZ];		/* grid */
static int  C[GZ][GZ];		/* costs */
static int sx,sy, ex,ey;	/* start, end pos */

static void
flood(int x, int y)
{
	int lo = INT_MAX;

	if (x<1 || x>=GZ-1 ||
	    y<1 || y>=GZ-1 || G[y][x]!='.')
		return;

	if (C[y-1][x]) lo = MIN(lo, C[y-1][x]+1);
	if (C[y+1][x]) lo = MIN(lo, C[y+1][x]+1);
	if (C[y][x-1]) lo = MIN(lo, C[y][x-1]+1);
	if (C[y][x+1]) lo = MIN(lo, C[y][x+1]+1);

	if (lo != INT_MAX && (!C[y][x] || lo < C[y][x])) {
		C[y][x] = lo;

		flood(x, y-1); flood(x-1, y);
		flood(x, y+1); flood(x+1, y);
	}
}

static int
count_shortcuts(int lim, int min)
{
	int acc=0, x,y, dx,dy;

	for (y=GB; y<GZ-GB; y++)
	for (x=GB; x<GZ-GB; x++)
	for (dy = -lim; dy <= lim; dy++)
	for (dx = abs(dy)-lim; dx <= lim-abs(dy); dx++)
		acc += x+dx >= 0 && x+dx < GZ &&
		       y+dy >= 0 && y+dy < GZ && C[y][x] &&
		       C[y][x]+abs(dx)+abs(dy) <= C[y+dy][x+dx]-min;

	return acc;
}

int
main(int argc, char **argv)
{
	int x,y;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	for (y=2; fgets(G[y]+GB, GZ-GB*2, stdin); y++)
		assert(y < GZ-3);

	for (y=GB; y<GZ-GB; y++)
	for (x=GB; x<GZ-GB; x++)
		if (G[y][x] == 'S') { G[y][x]='.'; sx=x; sy=y; } else
		if (G[y][x] == 'E') { G[y][x]='.'; ex=x; ey=y; }

	C[sy][sx] = 1;

	flood(sx, sy-1); flood(sx-1, sy);
	flood(sx, sy+1); flood(sx+1, sy);

	printf("20: %d %d\n",
	    count_shortcuts(2, 100),
	    count_shortcuts(20, 100));

	return 0;
}