path: root/23.c

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


#define arrlen(x) (sizeof(x)/sizeof((x)[0]))


// Directions. Use characters corresponding to directions surrounding the 's'
// on a querty keyboard. Because why not?
#define DIR_N		'w'
#define DIR_S		'x'
#define DIR_W		'a'
#define DIR_E		'd'

#define DIR_NW		'q'
#define DIR_NE		'e'
#define DIR_SW		'z'
#define DIR_SE		'c'


// Is this location an elf?
int
loc_elf(char ch)
{
	switch (ch) {
	case '#':
	case DIR_N:
	case DIR_S:
	case DIR_W:
	case DIR_E:
		return 1;
	}
	return 0;
}


// What direction does the elf at this location want to move?
int
loc_elf_dir(char ch)
{
	switch (ch) {
	case DIR_N:
	case DIR_S:
	case DIR_W:
	case DIR_E:
		return ch;
	case '#':
		return 0;
	}
	return -1;

}


// Is this location clear?
int
loc_clear(char ch)
{
	switch (ch) {
	case '.':
	case '\n':
		return 1;
	}
	return 0;
}


// Is this location a proposed destination?
int
loc_proposed(char ch)
{
	return isdigit(ch);
}


// Get the offset of a position in a buffer, one move in a given direction
char *
posd(char * buf, int cols, int rows, int i, int j, int dir)
{
	int offset;

	switch (dir) {
	case 0: offset = i + j * cols; break;

	case DIR_N: offset = i + (j - 1) * cols; break;
	case DIR_S: offset = i + (j + 1) * cols; break;
	case DIR_W: offset = (i - 1) + j * cols; break;
	case DIR_E: offset = (i + 1) + j * cols; break;

	case DIR_NW: offset = (i - 1) + (j - 1) * cols; break;
	case DIR_NE: offset = (i + 1) + (j - 1) * cols; break;
	case DIR_SW: offset = (i - 1) + (j + 1) * cols; break;
	case DIR_SE: offset = (i + 1) + (j + 1) * cols; break;

	default:
		fprintf(stderr, "Unknown direction %d\n", dir);
		return NULL;
	}

	if (offset < 0 || offset > rows * cols) {
		fprintf(stderr, "Invalid location at %d,%d", i, j);
		switch (dir) {
		case DIR_N: fprintf(stderr, "+N"); break;
		case DIR_S: fprintf(stderr, "+S"); break;
		case DIR_W: fprintf(stderr, "+W"); break;
		case DIR_E: fprintf(stderr, "+E"); break;
		case DIR_NW: fprintf(stderr, "+NW"); break;
		case DIR_NE: fprintf(stderr, "+NE"); break;
		case DIR_SW: fprintf(stderr, "+SW"); break;
		case DIR_SE: fprintf(stderr, "+SE"); break;
		}
		fprintf(stderr, " in %dx%d\n", cols, rows);
		return NULL;
	}

	return buf + offset;
}


// Get the offset of a position in a buffer
char *
pos(char * buf, int cols, int rows, int i, int j)
{
	return posd(buf, cols, rows, i, j, 0);
}


// Get the bounding box for elves
int
bounding(int * xmin, int * xmax, int * ymin, int * ymax,
		char const * buf, int cols, int rows)
{
	int i, j;

	*xmin = *xmax = *ymin = *ymax = -1;

	for (j = 0; j < rows; ++j) {
		for (i = 0; i < cols; ++i) {
			if (buf[i + j * cols] != '#')
				continue;

			if (*xmin == -1) {
				*xmin = i;
				*xmax = i;
				*ymin = j;
				*ymax = j;
			}
			if (i < *xmin)
				*xmin = i;
			if (i > *xmax)
				*xmax = i;
			if (j < *ymin)
				*ymin = j;
			if (j > *ymax)
				*ymax = j;
		}
	}

	if (*xmin == -1)
		return -1;

	// use a semi-open range.
	++*xmax;
	++*ymax;

	return 0;
}


// Check if it's possible to move in a certain direction
int
trymove(char * buf, int cols, int rows, int round, int i, int j)
{
	static char const dirs[4] = { DIR_N, DIR_S, DIR_W, DIR_E };
	int d, dir;

	if (!loc_elf(*pos(buf, cols, rows, i, j)))
		// ???
		return -1;

	if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_N))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_S))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_W))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_E))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW))
			&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE)))
		// No elves nearby, do not move.
		return 0;

	for (d = 0, dir = 0; d < arrlen(dirs) && dir == 0; ++d) {
		switch (dirs[(round + d) % 4]) {
		case DIR_N:
			if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_N))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE)))
				dir = DIR_N;
			break;

		case DIR_S:
			if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_S))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE)))
				dir = DIR_S;
			break;

		case DIR_W:
			if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_W))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NW))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SW)))
				dir = DIR_W;
			break;

		case DIR_E:
			if (!loc_elf(*posd(buf, cols, rows, i, j, DIR_E))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_NE))
					&& !loc_elf(*posd(buf, cols, rows, i, j, DIR_SE)))
				dir = DIR_E;
			break;

		default:
			return -1;
		}
	}

	return dir;
}


#if 0
void
grid_dump(char * buf, int cols, int rows)
{
	int i, j;

	for (j = 0; j < rows; ++j) {
		for (i = 0; i < cols; ++i) {
			int c = buf[i + cols * j];
			fputc(c == '\n' ? '.' : c, stderr);
		}
		fputc('\n', stderr);
	}
}
#endif


int
main(int argc, char ** argv)
{
	int rounds = 10;
	char * buf = NULL, * pch;
	int bufsiz = 0, buflen = 0;
	int cols, rows, round;
	int xmin, xmax, ymin, ymax, i, j;
	int empty;

	while ((i = getopt(argc, argv, "p:r:")) != -1) {
		switch (i) {
		case 'p':
			switch (atoi(optarg)) {
			case 1: rounds = 10; break;
			case 2: rounds = -1; break;
			default:
				fprintf(stderr, "Unexpected part %s\n", optarg);
				return -1;
			}
			break;

		case 'r':
			rounds = atoi(optarg);
			break;

		default:
			return -1;
		}
	}

	// Read input
	while (1) {
		size_t n;

		if (bufsiz - buflen < BUFSIZ) {
			void * p;

			bufsiz += BUFSIZ;
			if ((p = realloc(buf, bufsiz)) == NULL) {
				fprintf(stderr, "Bad realloc(%d)\n", bufsiz);
				free(buf);
				return -1;
			}
			buf = p;
		}

		if ((n = fread(buf + buflen, 1, bufsiz - buflen, stdin)) == 0)
			break;
		buflen += n;
	}
	if ((pch = memchr(buf, '\n', buflen)) == NULL) {
		fprintf(stderr, "No lines in input!\n");
		free(buf);
		return -1;
	}

	// Work out grid dimensions
	cols = pch + 1 - buf;
	rows = buflen / cols;
	if (buflen % cols != 0) {
		fprintf(stderr, "Input size %d is not a multiple of row length %d\n",
				buflen, cols);
		free(buf);
		return -1;
	}

	// Do rounds of movement simulation
	for (round = 0; round < rounds || rounds < 0; ++round) {
		char * psrc, * pdest;
		int dir, moves = 0;

		// Get current bounding box.
		if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) {
			fprintf(stderr, "Can't find bounding box!\n");
			free(buf);
			return -1;
		}

		// Expand it to cover all possible movement
		--xmin;
		++xmax;
		--ymin;
		++ymax;

		// Expand it to cover the current grid (resizing only checked for growth)
		if (xmin > 0)
			xmin = 0;
		if (xmax < cols)
			xmax = cols;
		if (ymin > 0)
			ymin = 0;
		if (ymax < rows)
			ymax = rows;

		// Check grid is big enough to contain any proposed movement
		if (xmin < 0 || xmax > cols
				|| ymin < 0 || ymax > rows)
		{
			int newcols, newrows;
			void * p;

#if 0
			fprintf(stderr, "Before\n");
			grid_dump(buf, cols, rows);
#endif

			newcols = xmax - xmin;
			newrows = ymax - ymin;
			bufsiz = newcols * newrows;
			if ((p = realloc(buf, bufsiz)) == NULL) {
				fprintf(stderr, "Bad realloc(%d)\n", bufsiz);
				free(buf);
				return -1;
			}
			buf = p;

			// Set bottom row(s) as empty.
			memset(buf + rows * newcols, '.', (newrows - rows) * newcols);
			// Move old rows into position, last first
			for (j = rows - 1; j >= 0; --j) {
				pdest = pos(buf, newcols, newrows, -xmin + cols, j + -ymin);
				if (pdest + (newcols - (-xmin + cols)) - buf > newcols * newrows) {
					fprintf(stderr, "Writing %d bytes to offset %d with buffer size %d\n",
							newcols - cols, (int) (pdest - buf), newcols * newrows);
				}

				memset(pos(buf, newcols, newrows, -xmin + cols, j + -ymin), '.', newcols - (-xmin + cols));
				memmove(pos(buf, newcols, newrows, -xmin, j + -ymin),
						pos(buf, cols, rows, 0, j),
						cols);
				memset(pos(buf, newcols, newrows, 0, j + -ymin), '.', -xmin);
			}
			// Set top row(s) as empty.
			memset(buf, '.', -ymin * newcols);

			// Set new rows, cols, and recalc bounding box.
			cols = newcols;
			rows = newrows;

			if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) {
				fprintf(stderr, "Can't find bounding box!\n");
				free(buf);
				return -1;
			}

#if 0
			fprintf(stderr, "After\n");
			grid_dump(buf, cols, rows);
#endif
		}

		// Find proposed moves.
		for (j = ymin; j < ymax; ++j) {
			for (i = xmin; i < xmax; ++i) {
				psrc = pos(buf, cols, rows, i, j);
				if (!loc_elf(*psrc))
					continue;
				if ((dir = trymove(buf, cols, rows, round, i, j)) <= 0)
					continue;

				// Elf can potentially move.
				// Set which direction they want to move in
				*psrc = dir;

				// Count how many elves want to move to that position.
				pdest = posd(buf, cols, rows, i, j, dir);
				if (loc_clear(*pdest))
					*pdest = '1';
				else if (loc_proposed(*pdest))
					++*pdest;
				else
					fprintf(stderr, "Unexpected destination at %d,%d\n", i, j);
			}
		}

		// Cancel moves which clash
		for (j = ymin; j < ymax; ++j) {
			for (i = xmin; i < xmax; ++i) {
				psrc = pos(buf, cols, rows, i, j);
				if (!loc_elf(*psrc))
					continue;
				if ((dir = loc_elf_dir(*psrc)) <= 0)
					continue;

				// Elf can potentially move.
				// If more than one elf wants to move to dest, cancel movement.
				pdest = posd(buf, cols, rows, i, j, dir);
				if (*pdest != '1')
					*psrc = '#';
			}
		}

		// Finalise moves and clean up grid
		for (j = ymin; j < ymax; ++j) {
			for (i = xmin; i < xmax; ++i) {
				psrc = pos(buf, cols, rows, i, j);
				if ((dir = loc_elf_dir(*psrc)) > 0) {
					// Finalise move.
					pdest = posd(buf, cols, rows, i, j, dir);
					*pdest = '#';
					*psrc = '.';
					++moves;
				}
				else if (loc_proposed(*psrc)) {
					// Clean up count of elves who wanted to move here.
					*psrc = '.';
				}
			}
		}

		if (!moves)
			break;

#if 0
		fprintf(stderr, "Round %d\n", round + 1);
		grid_dump(buf, cols, rows);
#endif
	}

	if (rounds < 0) {
		printf("Number of rounds needed to stabilise: %d\n", round + 1);
	}
	else {
		// Find the number of empty cells in the bounding box
		empty = 0;
		if (bounding(&xmin, &xmax, &ymin, &ymax, buf, cols, rows) != 0) {
			fprintf(stderr, "Can't find bounding box!\n");
			free(buf);
			return -1;
		}
		for (j = ymin; j < ymax; ++j) {
			for (i = xmin; i < xmax; ++i) {
				if (loc_clear(*pos(buf, cols, rows, i, j))) {
					++empty;
				}
			}
		}

		printf("Number of empty spaces after %d rounds: %d\n", rounds, empty);
	}

	// Tidy and exit
	free(buf);

	return 0;
}