2011-day12.c

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

struct offset
{
	int x, y;
};

struct cell
{
	char c;
	char v;
	struct offset o;
	int steps;
};

static struct cell grid[144*41];

static struct offset o[4] =
{
	{ 1,  0},
	{ 0, -1},
	{-1,  0},
	{ 0,  1},
};

struct node
{
	struct cell *c;
	struct node *next;
};

struct list
{
	struct node *head, **tail;
};

static struct list l = {NULL, &l.head};
static int pushes, pops;

static void push(struct cell *c)
{
	struct node *n = malloc(sizeof *n);
	n->c = c;
	n->next = NULL;

	*l.tail = n;
	l.tail = &n->next;
}

static struct cell *pop(void)
{
	if(!l.head)
		return NULL;

	struct cell *c = l.head->c;
	struct node *n = l.head->next;

	free(l.head);
	l.head = n;

	if(!l.head)
		l.tail = &l.head;

	return c;
}

static void dump(void)
{
	printf("\n\n\n\n\n");
	for(int j = 0; j < 41; j++)
	{
		for(int i = 0; i < 144; i++)
		{
			putchar(grid[j*144+i].v ? grid[j*144+i].c : ' ');
		}
		putchar('\n');
	}
	Sleep(1);
}

static int doop(int x, int y)
{
	struct cell *p;

	/* Prime search list from starting pos */
	for(int i = 0; i < 4; i++)
	{
		if(y+o[i].y < 0 || y+o[i].y >= 41)
			continue;
		if(x+o[i].x < 0 || x+o[i].x >= 144)
			continue;

		p = &grid[(y+o[i].y)*144+(x+o[i].x)];

		if(!p->v && p->c >= 'z')
		{
			printf("Initial setup pushing (%d,%d)\n", p->o.x, p->o.y);
			push(p);
		}
	}

	/* Take node from list, add its neighbours, repeat */
	while((p = pop()))
	{
		/* dump(); */

		for(int i = 0; i < 4; i++)
		{
			int tx, ty;

			tx = p->o.x + o[i].x;
			ty = p->o.y + o[i].y;

			if(ty < 0 || ty >= 41)
				continue;

			if(tx < 0 || tx >= 144)
				continue;

			struct cell *n = &grid[ty*144+tx];

			if(n->c == 'a' && p->c == 'b')
			{
				return p->steps + 1 + 1 /* No idea why it's off by 1 */;
			}

			if(!n->v && (p->c - n->c <= 1))
			{
					n->v = 1;
					n->steps = p->steps + 1;
					push(n);
			}
		}
	}

	return -1;
}

int main(void)
{
	char line[4096];
	FILE *f;
	int startx, starty;

	f = fopen("day12.txt", "r");


	for(int j = 0; j < 41; j++)
	{
		if(!fgets(line, 4096, f))
			break;

		for(int i = 0; i < 144; i++)
		{
			char c = line[i];
			if(c == 'E')
			{
				startx = i;
				starty = j;
			}
			grid[j*144+i].c = c;
			grid[j*144+i].v = 0;
			grid[j*144+i].o.x = i;
			grid[j*144+i].o.y = j;
			grid[j*144+i].steps = 0;
		}
	}

	grid[starty*144+startx].v = 1;

	printf("Length: %d\n", doop(startx, starty));

	return 0;
}