#define _GNU_SOURCE

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


// Proper modulo operator
#define modulo(n, m) ((((n) % (m)) + (m)) % (m))


enum map_type {
	M_FLAT,
	M_NET,
};


enum direction {
	D_NORTH = 3,
	D_EAST = 0,
	D_SOUTH = 1,
	D_WEST = 2,
};


char const *
direction_name(enum direction dir)
{
	switch (dir) {
	case D_NORTH: return "North";
	case D_EAST: return "East";
	case D_SOUTH: return "South";
	case D_WEST: return "West";
	}
	return NULL;
}


struct map {
	char * _buf;
	int cols;
	int rows;
	enum map_type type;
};


// Initialise a map from a buffer.
//
// The map takes ownership of the buffer from when it's called, whether
// or not the initialisation is successful
struct map *
map_init(struct map * map, char * buf, size_t buflen, enum map_type type)
{
	char * beg, * end;
	long pos;

	map->_buf = NULL;
	map->cols = 0;
	map->rows = 0;
	map->type = type;

	// Work out max lines and longest line.
	for (beg = buf; beg < buf + buflen; beg = end + 1, ++map->rows) {
		end = memchr(beg, '\n', buf + buflen - beg);
		if (end - beg > map->cols)
			map->cols = end - beg;
	}
	if (map->cols == 0 || map->rows == 0) {
		fprintf(stderr, "Unexpected map size (%d,%d)\n", map->cols, map->rows);
		free(buf);
		return NULL;
	}
	++map->cols; // Also count the newline on the end of each line.

	// Resize the map data buffer to hold a full grid of data
	if ((map->_buf = realloc(buf, map->cols * map->rows)) == NULL) {
		fprintf(stderr, "Bad realloc(%d)\n", map->cols * map->rows);
		free(buf);
		return NULL;
	}
	memset(map->_buf + buflen, ' ', map->cols * map->rows - buflen);

	// Move the map data so that it fits the grid properly
	for (end = map->_buf + buflen, pos = map->rows - 1; pos >= 0; end = beg, --pos) {
		beg = memrchr(map->_buf, '\n', (end - map->_buf) - 1);
		beg = beg ? beg + 1 : map->_buf;
		memmove(map->_buf + pos * map->cols, beg, (end - beg));
		memset(map->_buf + (pos * map->cols) + (end - beg) - 1, ' ', map->cols - (end - beg) + 1);
		map->_buf[pos * map->cols + map->cols - 1] = '\n';
	}

	return map;
}


void
map_tidy(struct map * map)
{
	if (!map)
		return;

	free(map->_buf);
	return;
}


int
map_elem(struct map const * map, int x, int y)
{
	if (x < 0 || x >= map->cols - 1
			|| y < 0 || y >= map->rows)
		return ' ';

	return map->_buf[x + (map->rows - 1 - y) * map->cols];
}


struct elf {
	int x;
	int y;
	enum direction dir;
};


int
elf_turn(struct elf * elf, char turn)
{
#define direction_go(d, t) (1000 * (d) + (t))

	switch (direction_go(elf->dir, turn)) {
	case direction_go(D_NORTH, 'R'):
	case direction_go(D_SOUTH, 'L'):
		elf->dir = D_EAST;
		break;

	case direction_go(D_NORTH, 'L'):
	case direction_go(D_SOUTH, 'R'):
		elf->dir = D_WEST;
		break;

	case direction_go(D_EAST, 'L'):
	case direction_go(D_WEST, 'R'):
		elf->dir = D_NORTH;
		break;

	case direction_go(D_EAST, 'R'):
	case direction_go(D_WEST, 'L'):
		elf->dir = D_SOUTH;
		break;

	default:
		fprintf(stderr, "Unexpected elf_turn(%d, %c)\n", elf->dir, turn);
		return -1;
	}

	return 0;

#undef direction_go
}


int
elf_move(struct elf * elf, struct map const * map, int distance)
{
	while (distance > 0) {
		int dx = 0, dy = 0, elem;
		struct elf newelf;

		switch (elf->dir) {
		case D_NORTH: dy = +1; break;
		case D_SOUTH: dy = -1; break;
		case D_EAST: dx = +1; break;
		case D_WEST: dx = -1; break;
		default:
			fprintf(stderr, "Unexpected direction %d\n", elf->dir);
			return -1;
		}

		switch (map->type) {
		case M_FLAT:
			newelf.x = modulo(elf->x + dx, map->cols);
			newelf.y = modulo(elf->y + dy, map->rows);
			newelf.dir = elf->dir;
			elem = map_elem(map, newelf.x, newelf.y);

			// Just keep going until we wrap around to a non-blank position
			while (elem == ' ') {
				newelf.x = modulo(newelf.x + dx, map->cols);
				newelf.y = modulo(newelf.y + dy, map->rows);
				elem = map_elem(map, newelf.x, newelf.y);
			}
			break;

		case M_NET:
			fprintf(stderr, "Map type not yet supported!\n");
			return -1;

		default:
			fprintf(stderr, "Unknown map type %d\n", map->type);
			return -1;
		}

		switch (elem) {
		case '.':
			*elf = newelf;
			--distance;
			break;

		case '#':
			distance = 0;
			break;

		default:
			fprintf(stderr, "Unexpected map character %c\n", elem);
			return -1;
		}
	}

	return 0;
}


int
main(int argc, char ** argv)
{
	char * buf = NULL;
	struct map map;
	enum map_type mtype = M_FLAT;
	long bufsiz = 0, buflen = 0;
	long pos;
	struct elf elf;
	char distance[8];
	int c, dlen = 0;

	while ((pos = getopt(argc, argv, "p:m:")) != -1) {
		switch (pos) {
		case 'p':
			switch (atoi(optarg)) {
			case 1:
				mtype = M_FLAT;
				break;

			case 2:
				mtype = M_NET;
				break;

			default:
				fprintf(stderr, "Unexpected puzzle part %s\n", optarg);
				return -1;
			}
			break;

		case 'm':
			if (strcmp(optarg, "flat") == 0) {
				mtype = M_FLAT;
			}
			else if (strcmp(optarg, "net") == 0) {
				mtype = M_NET;
			}
			else {
				fprintf(stderr, "Unexpected map type %s\n", optarg);
				return -1;
			}
			break;

		default:
			return -1;
		}
	}

	// Read map data
	// Don't try and figure out lines yet, in case we get a line longer than
	// our read buffer, which could make things awkward.
	while (1) {
		if (bufsiz - buflen < BUFSIZ / 2) {
			void * p;
			bufsiz += BUFSIZ;
			if ((p = realloc(buf, bufsiz)) == NULL) {
				fprintf(stderr, "Bad realloc(%ld)\n", bufsiz);
				free(buf);
				return -1;
			}
			buf = p;
		}

		if (!fgets(buf + buflen, bufsiz - buflen, stdin))
			// End of file!
			break;

		if (buflen > 0 && buf[buflen] == '\n' && buf[buflen - 1] == '\n')
			// End of map input.
			break;

		buflen += strlen(buf + buflen);
	}

	if (map_init(&map, buf, buflen, mtype) == NULL) {
		fprintf(stderr, "Failed to initialise map\n");
		return -1;
	}

	// Set initial position
	elf.x = 0;
	elf.y = map.rows - 1;
	elf.dir = D_EAST;
	while (elf.x < map.cols && map_elem(&map, elf.x, elf.y) != '.')
		++elf.x;

	// Read and follow the movement instructions.
	while (elf.x >= 0 && (c = fgetc(stdin)) != EOF) {
		if (isdigit(c)) {
			distance[dlen++] = c;
		}
		else if (c == 'L' || c == 'R') {
			distance[dlen] = '\0';

			if (elf_move(&elf, &map, atoi(distance)) != 0)
				elf.x = -1;
			if (elf_turn(&elf, c) != 0)
				elf.x = -1;

			dlen = 0;
		}
		else if (c == '\n') {
			// Cover last bit of distance, if any
			distance[dlen] = '\0';
			if (elf_move(&elf, &map, atoi(distance)) != 0)
				elf.x = -1;
			break;
		}
		else {
			fprintf(stderr, "Unexpected movement instruction (%c)\n", c);
			map_tidy(&map);
			return -1;
		}
	}
	if (elf.x < 0) {
		map_tidy(&map);
		return -1;
	}

	// Done.
	printf("Password is %d (%d,%d,%d)\n",
			1000 * (map.rows - elf.y) + 4 * (1 + elf.x) + elf.dir,
			1 + elf.x, map.rows - elf.y, elf.dir);

	// Tidy and exit.
	map_tidy(&map);

	return 0;
}