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


#define C_EMPTY	0x00

#define C_BLZ_N	0x01
#define C_BLZ_E	0x02
#define C_BLZ_S 0x04
#define C_BLZ_W	0x08

#define C_BLZ	(C_BLZ_N | C_BLZ_E | C_BLZ_S | C_BLZ_W)

#define C_WALL  0x10
#define C_ELF	0x20


unsigned char *
pos(unsigned char * buf, int cols, int rows, int i, int j)
{
	i = ((i % cols) + cols) % cols;
	j = ((j % rows) + rows) % rows;

	return buf + i + j * cols;
}


void
clear_mask(unsigned char * buf, int cols, int rows, unsigned mask)
{
	int i, j;

	for (j = 0; j < rows; ++j) {
		for (i = 0; i < cols; ++i) {
			*pos(buf, cols, rows, i, j) &= ~mask;
		}
	}
}


int
find_path(unsigned char * buf, int cols, int rows,
		int start_col, int start_row, int exit_col, int exit_row)
{
	unsigned char * realnext, * next;
	int i, j, round;

	// Create the "next" buffer, and place the walls in it.
	if ((next = realnext = calloc(rows, cols)) == NULL) {
		fprintf(stderr, "Bad next alloc(%d)\n", cols * rows);
		return -1;
	}
	for (j = 0; j < rows; ++j) {
		for (i = 0; i < cols; ++i) {
			if (*pos(buf, cols, rows, i, j) == C_WALL)
				*pos(next, cols, rows, i, j) = C_WALL;
		}
	}

	// Place the start elf
	*pos(buf, cols, rows, start_col, start_row) = C_ELF;

	for (round = 0; (*pos(buf, cols, rows, exit_col, exit_row) & C_ELF) == 0; ++round) {
		int elves = 0;
		unsigned char * psrc, * pdest, * tmp;

		// Work out the possible positions of elves and blizzards in `next`
		for (j = 0; j < rows; ++j) {
			for (i = 0; i < cols; ++i) {
				int o;

				psrc = pos(buf, cols, rows, i, j);

				if (*psrc & C_ELF) {
					*pos(next, cols, rows, i, j) |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i, j - 1)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i + 1, j)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i, j + 1)) & C_WALL) == 0)
						*pdest |= C_ELF;
					if ((*(pdest = pos(next, cols, rows, i - 1, j)) & C_WALL) == 0)
						*pdest |= C_ELF;
					++elves;
				}
				if (*psrc & C_BLZ_N) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i, j - o)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_N;
				}
				if (*psrc & C_BLZ_E) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i + o, j)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_E;
				}
				if (*psrc & C_BLZ_S) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i, j + o)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_S;
				}
				if (*psrc & C_BLZ_W) {
					for (o = 1; (*(pdest = pos(next, cols, rows, i - o, j)) & C_WALL) != 0; ++o)
						;
					*pdest |= C_BLZ_W;
				}
			}
		}
		if (elves == 0) {
			fprintf(stderr, "Warning, ran out of elves after %d rounds!\n", round);
			free(realnext);
			return -1;
		}

		// Whereever there is a blizzard and and elf together, remove the elf
		for (j = 0; j < rows; ++j) {
			for (i = 0; i < cols; ++i) {
				if ((*(pdest = pos(next, cols, rows, i, j)) & C_ELF) != 0
						&& (*pdest & C_BLZ) != 0)
				{
					*pdest &= ~C_ELF;
				}
			}
		}

		// Swap next and buf, and clear `next` for next round
		tmp = buf;
		buf = next;
		next = tmp;
		clear_mask(next, rows, cols, C_ELF | C_BLZ);
	}

	if (next != realnext) {
		// Our `next` and `buf` variables are flipped.
		// Copy `buf` into `next` so that the caller has an up-to-date
		// copy of the map.
		memcpy(next, buf, cols * rows);
	}

	// Tidy and exit
	free(realnext);

	return round;
}


int
main(int argc, char ** argv)
{
	unsigned char * buf = NULL;
	int part = 1, bufsiz = 0, buflen = 0;
	int cols = -1, rows = -1, start_col = -1, start_row = -1, exit_col = -1, exit_row = -1;
	int i, round;

	// Parse options
	while ((i = getopt(argc, argv, "p:")) != -1) {
		switch (i) {
		case 'p':
			part = atoi(optarg);
			break;

		default:
			return -1;
		}
	}

	// Read input
	while (1) {
		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 ((i = fgetc(stdin)) == EOF)
			break;
		switch (i) {
		case '#':
			buf[buflen++] = C_WALL;
			break;

		case '.':
			buf[buflen++] = C_EMPTY;
			break;

		case '^':
			buf[buflen++] = C_BLZ_N;
			break;

		case '>':
			buf[buflen++] = C_BLZ_E;
			break;

		case 'v':
			buf[buflen++] = C_BLZ_S;
			break;

		case '<':
			buf[buflen++] = C_BLZ_W;
			break;

		case '\n':
			if (cols == -1)
				cols = buflen;
			break;

		default:
			fprintf(stderr, "Unexpected input char %c\n", i);
			return -1;
		}
	}
	if (cols == -1 || buflen % cols != 0) {
		fprintf(stderr, "Input size %d is not a multiple of row length %d\n",
				buflen, cols);
		free(buf);
		return -1;
	}
	rows = buflen / cols;

	// Find the start/exit positions
	start_row = 0;
	exit_row = rows - 1;
	for (i = 0; i < cols; ++i) {
		if (*pos(buf, cols, rows, i, start_row) == C_EMPTY)
			start_col = i;
		if (*pos(buf, cols, rows, i, exit_row) == C_EMPTY)
			exit_col = i;
	}
	if (exit_col == -1) {
		fprintf(stderr, "No exit position found!\n");
		free(buf);
		return -1;
	}

	switch (part) {
	case 1:
		round = find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row);
		break;

	case 2:
		round = find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row);
		clear_mask(buf, cols, rows, C_ELF);
		round += find_path(buf, cols, rows, exit_col, exit_row, start_col, start_row);
		clear_mask(buf, cols, rows, C_ELF);
		round += find_path(buf, cols, rows, start_col, start_row, exit_col, exit_row);
		break;

	default:
		fprintf(stderr, "Unexpected part %d\n", part);
		free(buf);
		return -1;
	}

	printf("Found exit after %d rounds\n", round);

	// Tidy and exit
	free(buf);

	return 0;
}