sjmulder

#include "common.h"

static char *pats[480];
static int lens[480];
int np;

/* memoized for 's' by mem[off], 0 = unknown, >0 = value+1 */
static int64_t
recur(char *s, int off, int64_t *mem)
{
	int64_t acc=0;
	int i;

	if (!s[off]) return 1;
	if (mem[off]) return mem[off]-1;

	for (i=0; i<np; i++)
		if (!strncmp(s+off, pats[i], lens[i]))
			acc += recur(s, off+lens[i], mem);

	mem[off] = acc+1;
	return acc;
}

int
main(int argc, char **argv)
{
	static char patbuf[3200], design[64];
	int64_t p1=0,p2=0, mem[64], n;
	char *rest, *lf;

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

	rest = fgets(patbuf, sizeof(patbuf), stdin);

	for (; (pats[np] = strsep(&rest, ",")); np++) {
		while (isspace(pats[np][0]))
			pats[np]++;	/* skip spaces */
		if ((lf = strchr(pats[np], '\n')))
			*lf = '\0';	/* trim trailing \n */
		lens[np] = strlen(pats[np]);
		assert(np+1 < (int)LEN(pats));
	}

	while (scanf(" %63s", design) == 1) {
		memset(mem, 0, sizeof(mem));
		n = recur(design, 0, mem);
		p1 += n >0;
		p2 += n;
	}

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

#ingesloten "zee.kop"
#ingesloten "algemeen.kop"

besloten letterverwijzing patronen[480];
besloten getal lengtes[480];
getal patroonsom;

besloten zeer groot getal
afdaling(
    letterverwijzing tekst,
    getal startpositie,
    zeergrootgetalreeksverwijzing onthouden)
{
	zeer groot getal deelsom=0;
	getal sortering, teller;

	tenzij (tekst[startpositie])
		lever 1;
	mits (onthouden[startpositie])
		lever onthouden[startpositie]-1;

	voor (teller=0; teller < patroonsom; teller++) {
		sortering = tekstdeelvergelijking(
		    tekst + startpositie,
		    patronen[teller],
		    lengtes[teller]);

		mits (sortering == 0) {
			deelsom += afdaling(
			    tekst,
			    startpositie + lengtes[teller],
			    onthouden);
		}
	}

	onthouden[startpositie] = deelsom+1;
	lever deelsom;
}

getal
aanvang(
    getal parametersom,
    letterverwijzingsreeksverwijzing parameters)
{
	blijvende letter patroonruimte[3200];
	blijvende letter ontwerp[64];
	zeer groot getal deel1=0, aantal;
	zeer groot getal deel2=0, onthouden[64];
	letterverwijzing rest;
	letterverwijzing regeleinde;

	mits (parametersom > 1)
		VERWERP(heropen(parameters[1], "r", standaardinvoer));

	rest = geefregel(patroonruimte, grootte(patroonruimte),
	    standaardinvoer);

	voor (; ; patroonsom++) {
		verzeker(patroonsom+1 < (getal)LENGTE(patronen));
		patronen[patroonsom] = tekstsplitsing(naar rest, ",");
		mits (patronen[patroonsom] == NIETS)
			klaar;

		zolang (iswitruimte(patronen[patroonsom][0]))
			patronen[patroonsom]++;
		mits ((regeleinde = zoekletter(patronen[patroonsom], '\n')))
			volg regeleinde = '\0';

		lengtes[patroonsom] = tekstlengte(patronen[patroonsom]);
	}

	zolang (invorm(" %63s", ontwerp) == 1) {
		overschrijf(onthouden, 0, grootte(onthouden));
		aantal = afdaling(ontwerp, 0, onthouden);
		deel1 += aantal >0;
		deel2 += aantal;
	}

	uitvorm("19: %"GEEFZGG" %"GEEFZGG"\n", deel1, deel2);
	lever 0;
}

#include "common.h"

#define SAMPLE	0
#define PTZ	3600
#define GZ	(SAMPLE ? 9 : 73)
#define P1STEP	(SAMPLE ? 12 : 1024)
#define CORR	-1

static int g[GZ][GZ];

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

	if (x <= 0 || x >= GZ-1 ||
	    y <= 0 || y >= GZ-1 || g[y][x] == CORR)
		return;

	if (g[y-1][x] > 0) lo = MIN(lo, g[y-1][x] +1);
	if (g[y+1][x] > 0) lo = MIN(lo, g[y+1][x] +1);
	if (g[y][x-1] > 0) lo = MIN(lo, g[y][x-1] +1);
	if (g[y][x+1] > 0) lo = MIN(lo, g[y][x+1] +1);

	if (lo != INT_MAX && (!g[y][x] || g[y][x] > lo)) {
		g[y][x] = lo;

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

int
main(int argc, char **argv)
{
	static int xs[PTZ], ys[PTZ];
	static char p2[32];
	int p1=0, npt=0, i;

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

	for (i=0; i<GZ; i++)
		g[0][i] = g[GZ-1][i] =
		g[i][0] = g[i][GZ-1] = CORR;

	for (npt=0; npt<PTZ && scanf(" %d,%d", xs+npt, ys+npt)==2; npt++) {
		assert(xs[npt] >= 0); assert(xs[npt] < GZ-2);
		assert(ys[npt] >= 0); assert(ys[npt] < GZ-2);
	}

	assert(npt < PTZ);

	for (i=0; i<npt; i++)
		g[ys[i]+1][xs[i]+1] = CORR;

	g[1][1] = 1;
	flood(2, 1);
	flood(1, 2);

	for (i=npt-1; i >= P1STEP; i--) {
		g[ys[i]+1][xs[i]+1] = 0;
		flood(xs[i]+1, ys[i]+1);

		if (!p2[0] && g[GZ-2][GZ-2] > 0)
			snprintf(p2, sizeof(p2), "%d,%d", xs[i],ys[i]);
	}

	p1 = g[GZ-2][GZ-2]-1;

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

#include "common.h"

#define SAMPLE	0
#define GZ	(SAMPLE ? 9 : 73)
#define NCORR	(SAMPLE ? 12 : 1024)
#define CORR	-1

int g[GZ][GZ];

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

	for (y=1; y<GZ-1; y++)
	for (x=1; x<GZ-1; x++)
		if (g[y][x] > 1)
			g[y][x] = 0;

	while (dirty) {
		dirty = 0;

		for (y=1; y<GZ-1; y++)
		for (x=1; x<GZ-1; x++) {
			if (g[y][x] == CORR) continue;
			lo = INT_MAX;
			if (g[y-1][x] > 0) lo = MIN(lo, g[y-1][x]);
			if (g[y+1][x] > 0) lo = MIN(lo, g[y+1][x]);
			if (g[y][x-1] > 0) lo = MIN(lo, g[y][x-1]);
			if (g[y][x+1] > 0) lo = MIN(lo, g[y][x+1]);
			if (lo != INT_MAX && (!g[y][x] || g[y][x]>lo+1))
				{ dirty=1; g[y][x] = lo+1; }
		}
	}
}

int
main(int argc, char **argv)
{
	int p1=0, x,y, i;

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

	for (i=0; i<GZ; i++)
		g[0][i] = g[GZ-1][i] =
		g[i][0] = g[i][GZ-1] = CORR;
	
	g[1][1] = 1;

	for (i=0; scanf(" %d,%d", &x, &y) == 2; i++) {
		assert(x >= 0); assert(x < GZ-2);
		assert(y >= 0); assert(y < GZ-2);
		g[y+1][x+1] = CORR;

		flood();

		if (i==NCORR-1)
			p1 = g[GZ-2][GZ-2]-1;
		if (g[GZ-2][GZ-2] <= 0) {
			printf("18: %d %d,%d\n", p1, x,y);
			return 0;
		}
	}

	assert(!"no solution");
	return -1;
}

#include "common.h"

#define MEMZ 32
#define OUTZ 32
#define BUFZ 64

enum { ADV, BXL, BST, JNZ, BXC, OUT, BDV, CDV };

struct vm {
	int64_t mem[MEMZ]; int nm, pc;
	int64_t out[OUTZ]; int no;
	int64_t a,b,c;
} vm;

/* returns 0 if halted, 1 otherwise */
static int
step(void)
{
	int64_t op, ar, ac;	/* operator, lit. arg, combo arg */

	assert(vm.pc >= 0);
	assert(vm.pc+2 <= MEMZ);

	if (vm.pc >= vm.nm)
		return 0;

	op = vm.mem[vm.pc++];
	ar = vm.mem[vm.pc++];
	ac = ar==4 ? vm.a : ar==5 ? vm.b : ar==6 ? vm.c : ar;

	switch (op) {
	case ADV: vm.a = vm.a >> ac; break;
	case BDV: vm.b = vm.a >> ac; break;
	case CDV: vm.c = vm.a >> ac; break;
	case BXL: vm.b = vm.b ^ ar; break;
	case BXC: vm.b = vm.b ^ vm.c; break;
	case BST: vm.b = ac % 8; break;
	case JNZ: if (vm.a) vm.pc = ar; break;
	case OUT: assert(vm.no < OUTZ); vm.out[vm.no++] = ac%8; break;
	default: assert(!"invalid opcode"); return 0;
	}

	return 1;
}

static int64_t
recur_p2(int64_t a0, int pos)
{
	int64_t a, i;

	/*
	 * The code in the input uses up to 7 low bits of the A register
	 * to produce a single number, then chops off the low 3 bits and
	 * continues.
	 *
	 * That means bits above the current triplet influence what
	 * number it generates, but bits below don't. To generate a
	 * desired sequence then, we append, not prepend,  candidate
	 * triplets.
	 *
	 * We may end up in a situation where, given the prefix found
	 * for the numbers so far, no triplet yields the desired next
	 * number. Then we have to backtrack and find another prefix,
	 * hence the recursion.
	 */

	if (pos >= vm.nm)
		return a0 >> 3;

	for (i=0; i<8; i++) {
		vm.a=a= a0+i;
		vm.b=vm.c=vm.pc=vm.no= 0;

		while (step() && !vm.no)
			;

		if (vm.no && vm.out[0] == vm.mem[vm.nm-pos-1])
			if ((a = recur_p2(a << 3, pos+1)))
				return a;
	}

	return 0;
}

int
main(int argc, char **argv)
{
	char b[BUFZ], *tok, *rest;
	int i;

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

	fgets(b, BUFZ, stdin); sscanf(b, "Register A: %lld", &vm.a);
	fgets(b, BUFZ, stdin); sscanf(b, "Register B: %lld", &vm.b);
	fgets(b, BUFZ, stdin); sscanf(b, "Register C: %lld", &vm.c);
	fgets(b, BUFZ, stdin);

	assert(vm.b == 0);	/* assumption for part 2 */
	assert(vm.c == 0);

	rest = fgets(b, sizeof(b), stdin);
	strsep(&rest, ":");

	while ((tok = strsep(&rest, ","))) {
		assert(vm.nm < MEMZ);
		vm.mem[vm.nm++] = atoll(tok);
	}

	while (step())
		;
	for (i=0; i<vm.no; i++)
		printf(i ? ",%lld" : "17: %lld", vm.out[i]);

	printf(" %lld\n", recur_p2(0, 0));
	return 0;
}

#include "common.h"

#define GZ 145

enum {NN, EE, SS, WW};

static const int dx[]={0,1,0,-1}, dy[]={-1,0,1,0};

static char g[GZ][GZ];		/* with 1 tile border */
static int cost[GZ][GZ][4];	/* per direction, starts at 1, 0=no info */

static int traversible(char c) { return c=='.' || c=='S' || c=='E'; }

static int
minat(int x, int y)
{
	int acc=0, d;

	for (d=0; d<4; d++)
		if (cost[y][x][d] && (!acc || cost[y][x][d] < acc))
			acc = cost[y][x][d];

	return acc;
}


static int
count_exits(int x, int y)
{
	int acc=0, i;

	assert(x>0); assert(x<GZ-1);
	assert(y>0); assert(y<GZ-1);

	for (i=0; i<4; i++)
		acc += traversible(g[y+dy[i]][x+dx[i]]);
	
	return acc;
}

/* remove all dead ends */
static void
prune_dead(void)
{
	int dirty=1, x,y;

	while (dirty) {
		dirty = 0;

		for (y=1; y<GZ-1; y++)
		for (x=1; x<GZ-1; x++)
			if (g[y][x]=='.' && count_exits(x,y) < 2)
				{ dirty = 1; g[y][x] = '#'; }
	}
}

/* remove all dead ends from cost[], leaves only optimal paths */
static void
prune_subopt(void)
{
	int dirty=1, x,y,d;

	while (dirty) {
		dirty = 0;

		for (y=1; y<GZ-1; y++)
		for (x=1; x<GZ-1; x++)
		for (d=0; d<4; d++) {
			if (!cost[y][x][d])
				continue;

			if (g[y][x]=='E') {
				if (cost[y][x][d] != minat(x,y))
					{ dirty = 1; cost[y][x][d] = 0; }
				continue;
			}

			if (cost[y][x][d]+1 > cost[y+dy[d]][x+dx[d]][d] &&
			    cost[y][x][d]+1000 > cost[y][x][(d+1)%4] &&
			    cost[y][x][d]+1000 > cost[y][x][(d+3)%4])
				{ dirty = 1; cost[y][x][d] = 0; }
		}
	}
}

static void
propagate_costs(void)
{
	int dirty=1, cost1, x,y,d;

	while (dirty) {
		dirty = 0;

		for (y=1; y<GZ-1; y++)
		for (x=1; x<GZ-1; x++)
		for (d=0; d<4; d++) {
			if (!traversible(g[y][x]))
				continue;

			/* from back */
			if ((cost1 = cost[y-dy[d]][x-dx[d]][d]) &&
			    (cost1+1 < cost[y][x][d] || !cost[y][x][d]))
				{ dirty = 1; cost[y][x][d] = cost1+1; }

			/* from right */
			if ((cost1 = cost[y][x][(d+1)%4]) &&
			    (cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
				{ dirty = 1; cost[y][x][d] = cost1+1000; }

			/* from left */
			if ((cost1 = cost[y][x][(d+3)%4]) &&
			    (cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
				{ dirty = 1; cost[y][x][d] = cost1+1000; }
		}
	}
}

int
main(int argc, char **argv)
{
	int p1=0,p2=0, sx=0,sy=0, ex=0,ey=0, x,y;
	char *p;

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

	for (y=1; fgets(g[y]+1, GZ-1, stdin); y++) {
		if ((p = strchr(g[y]+1, 'S'))) { sy=y; sx=p-g[y]; }
		if ((p = strchr(g[y]+1, 'E'))) { ey=y; ex=p-g[y]; }
		assert(y+1 < GZ-1);
	}

	cost[sy][sx][EE] = 1;

	prune_dead();
	propagate_costs();
	prune_subopt();

	p1 = minat(ex, ey) -1;	/* costs[] values start at 1! */

	for (y=1; y<GZ-1; y++)
	for (x=1; x<GZ-1; x++)
		p2 += minat(x,y) > 0;

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

#include "common.h"

#define GW 104
#define GH 52

struct world { char g[GH][GW]; int px,py; };

static int
can_clear(struct world *w, int x, int y, int dx, int dy)
{
	assert(x>=0); assert(x<GW);
	assert(y>=0); assert(y<GH);
	assert((dx && !dy) || (dy && !dx));

	return
	    (x+dx >= 0 || x+dx < GW) &&
	    (y+dy >= 0 || y+dy < GW) &&
	    (w->g[y][x] == '.' || (
	     w->g[y][x] != '#' && can_clear(w, x+dx,y+dy, dx,dy) &&
	     (!dy || w->g[y][x]!='[' || can_clear(w, x+1,y+dy, 0,dy)) &&
	     (!dy || w->g[y][x]!=']' || can_clear(w, x-1,y,    0,dy)) &&
	     (!dy || w->g[y][x]!=']' || can_clear(w, x-1,y+dy, 0,dy))));
}

/* check can_clear() first! */
static void
clear(struct world *w, int x, int y, int dx, int dy)
{
	assert(x>=0); assert(x<GW); assert(x+dx>=0); assert(x+dx<GW);
	assert(y>=0); assert(y<GH); assert(y+dy>=0); assert(y+dy<GH);

	if (w->g[y][x] == '.')
		return;
	if (dy && w->g[y][x] == ']')
		{ clear(w, x-1,y, dx,dy); return; }

	if (dy && w->g[y][x] == '[') {
		clear(w, x+1,y+dy, dx,dy);
		w->g[y+dy][x+dx+1] = ']';
		w->g[y][x+1] = '.';
	}

	clear(w, x+dx,y+dy, dx,dy);
	w->g[y+dy][x+dx] = w->g[y][x];
	w->g[y][x] = '.';
}

static void
move(struct world *w, int dx, int dy)
{
	if (can_clear(w, w->px+dx, w->py+dy, dx,dy)) {
		clear(w, w->px+dx, w->py+dy, dx,dy);
		w->px += dx;
		w->py += dy;
	}
}

static int
score(struct world *w)
{
	int acc=0, x,y;

	for (y=0; y<GH && w->g[y][0]; y++)
	for (x=0; x<GW && w->g[y][x]; x++)
		if (w->g[y][x] == 'O' || w->g[y][x] == '[')
			acc += 100*y + x;

	return acc;
}

int
main(int argc, char **argv)
{
	static struct world w1,w2;
	int x,y, c;
	char *p;

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

	for (y=0; fgets(w1.g[y], GW, stdin); y++) {
		if (!w1.g[y][0] || w1.g[y][0]=='\n')
			break;

		assert(y+1 < GH);
		assert(strlen(w1.g[y])*2+1 < GW);

		for (x=0; w1.g[y][x]; x++)
			if (w1.g[y][x] == 'O') {
				w2.g[y][x*2]   = '[';
				w2.g[y][x*2+1] = ']';
			} else {
				w2.g[y][x*2]   = w1.g[y][x];
				w2.g[y][x*2+1] = w1.g[y][x];
			}

		if ((p = strchr(w1.g[y], '@'))) {
			w1.py = y; w1.px = p-w1.g[y];
			w2.py = y; w2.px = w1.px*2;

			w1.g[w1.py][w1.px]   = '.';
			w2.g[w2.py][w2.px]   = '.';
			w2.g[w2.py][w2.px+1] = '.';
		}
	}

	while ((c = getchar()) != EOF)
		switch (c) {
		case '^': move(&w1, 0,-1); move(&w2, 0,-1); break;
		case 'v': move(&w1, 0, 1); move(&w2, 0, 1); break;
		case '<': move(&w1,-1, 0); move(&w2,-1, 0); break;
		case '>': move(&w1, 1, 0); move(&w2, 1, 0); break;
		}

	printf("15: %d %d\n", score(&w1), score(&w2));
	return 0;
}

#include "common.h"

#define SAMPLE 0
#define GW (SAMPLE ? 11 : 101)
#define GH (SAMPLE ?  7 : 103)
#define NR 501

int
main(int argc, char **argv)
{
	static char g[GH][GW];
	static int px[NR],py[NR], vx[NR],vy[NR];

	int p1=0, n=0, sec, i, x,y, q[4]={}, run;

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

	for (; scanf(" p=%d,%d v=%d,%d", px+n,py+n, vx+n,vy+n)==4; n++)
		assert(n+1 < NR);

	for (sec=1; !SAMPLE || sec <= 100; sec++) {
		memset(g, 0, sizeof(g));
		memset(q, 0, sizeof(q));

		for (i=0; i<n; i++) {
			px[i] = (px[i] + vx[i] + GW) % GW;
			py[i] = (py[i] + vy[i] + GH) % GH;

			g[py[i]][px[i]] = 1;

			if (sec == 100) {
				if (px[i] < GW/2) {
					if (py[i] < GH/2) q[0]++; else
					if (py[i] > GH/2) q[1]++;
				} else if (px[i] > GW/2) {
					if (py[i] < GH/2) q[2]++; else
					if (py[i] > GH/2) q[3]++;
				}
			}
		}

		if (sec == 100)
			p1 = q[0]*q[1]*q[2]*q[3];

		for (y=0; y<GH; y++)
		for (x=0, run=0; x<GW; x++)
			if (!g[y][x])
				run = 0;
			else if (++run >= 10)
				goto found_p2;
	}

found_p2:
	printf("14: %d %d\n", p1, sec);
	return 0;
}

#include "common.h"

static int64_t
score(int ax, int ay, int bx, int by, int64_t px, int64_t py)
{
	int64_t a,b, x;
	double as,bs;

	as = (double)ay / ax;
	bs = (double)by / bx;

	/* intersection between a (from start) and b (from end) */
	x = (int64_t)round((px*bs - py) / (bs-as));

	a = x / ax;
	b = (px-x) / bx;

	return
	    a*ax + b*bx == px &&
	    a*ay + b*by == py ? a*3 + b : 0;
}

int
main(int argc, char **argv)
{
	int ax,ay, bx,by;
	int64_t p1=0,p2=0, px,py;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (scanf(
	    " Button A: X+%d, Y+%d"
	    " Button B: X+%d, Y+%d"
	    " Prize: X=%"SCNd64", Y=%"SCNd64,
	    &ax, &ay, &bx, &by, &px, &py) == 6) {
		p1 += score(ax,ay, bx,by, px,py);
		p2 += score(ax,ay, bx,by,
		    px + 10000000000000LL,
		    py + 10000000000000LL);
	}

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

#include "common.h"

#define GZ 144
static char g[GZ][GZ];
static char seen[GZ][GZ];

static void
count(char c, int x, int y, int *area, int *perim, int *sides)
{
	if (g[y][x] != c) { (*perim)++; return; }
	if (seen[y][x]) return;

	*area += 1;
	seen[y][x] = 1;

	/* count start of top/left edges, end of bottom/right edges */
	*sides += g[y-1][x]!=c && ((g[y-1][x-1]==c) || (g[y][x-1]!=c));
	*sides += g[y+1][x]!=c && ((g[y+1][x+1]==c) || (g[y][x+1]!=c));
	*sides += g[y][x-1]!=c && ((g[y-1][x-1]==c) || (g[y-1][x]!=c));
	*sides += g[y][x+1]!=c && ((g[y+1][x+1]==c) || (g[y+1][x]!=c));

	count(c, x, y-1, area, perim, sides);
	count(c, x, y+1, area, perim, sides);
	count(c, x-1, y, area, perim, sides);
	count(c, x+1, y, area, perim, sides);
}

int
main(int argc, char **argv)
{
	int p1=0,p2=0, x,y, area, perim, sides;

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

	for (y=1; fgets(g[y]+1, GZ-2, stdin); y++)
		assert(y+1 < GZ);

	for (y=1; y<GZ-1; y++)
	for (x=1; x<GZ-1; x++)
		if (isalpha(g[y][x]) && !seen[y][x]) {
			area  = perim = sides = 0;
			count(g[y][x], x, y, &area, &perim, &sides);
			p1 += area * perim;
			p2 += area * sides;
		}

	printf("12: %d %d\n", p1, p2);
}