#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;
}


// For each face of a cuboid, list adjoining faces in anti-clockwise order
//
// The faces are numbered as a right-handed six-sided die labelled 0 to 5.
// Opposite pairs add up to 5 (0/5, 1/4 and 2/3), and if you imagine curling the
// fingers of your right hand from the 0 to the 1, the 2 is on the face that
// your thumb is pointing to. e.g. if the 0 is on the front, and the 1 is on
// top, the 2 is on the left side.
//
// When a face is "oriented" a certain way, then if that face is on top, the
// first adjoining face listed in table below is in that direction.
//
// e.g. If the 3 face is on the top of the cuboid and "oriented" west, then the
// 4 face is to its west, the 5 is to its south, the 1 is to its east, and the 0
// is to its north.
static int const faceids[6][4] = {
	{ 1, 2, 4, 3 },		// 0 sees 1, 2, 4, 3
	{ 0, 3, 5, 2 },		// 1 sees 0, 3, 5, 2
	{ 5, 4, 0, 1 },		// 2 sees 5, 4, 0, 1
	{ 4, 5, 1, 0 },		// 3 sees 4, 5, 1, 0
	{ 3, 0, 2, 5 },		// 4 sees 3, 0, 2, 5
	{ 2, 1, 3, 4 },		// 5 sees 2, 1, 3, 4
};


// Given an oriented top face, which face do we see in a given direction?
int
faceid_look(int topid, enum direction orient, enum direction look)
{
	static enum direction const dirs[] = { D_NORTH, D_WEST, D_SOUTH, D_EAST };
	int topdir, destdir;

	if (topid < 0 || topid >= 6)
		return -1;

	// Go through `dirs` until we find the one that topid is pointing to
	for (topdir = 0; topdir < 4; ++topdir)
		if (dirs[topdir % 4] == orient)
			break;
	if (topdir >= 4)
		return -1;

	// Keep going through `dirs` until we find the one that the caller wants
	for (destdir = topdir; destdir < topdir + 4; ++destdir)
		if (dirs[destdir % 4] == look)
			break;
	if (destdir >= topdir + 4)
		return -1;

	// Look up the destination face id.
	return faceids[topid][destdir - topdir];
}


// Given an oriented top face, which direction do we look to see another face?
enum direction
faceid_find(int topid, enum direction orient, int destid)
{
	static enum direction const dirs[] = { D_NORTH, D_WEST, D_SOUTH, D_EAST };
	int topdir, destix;

	// Go through the directions until we find the one that fsrc is pointing
	for (topdir = 0; topdir < 4; ++topdir)
		if (dirs[topdir % 4] == orient)
			break;
	if (topdir >= 4)
		return -1;

	// Go through topid's faces until we find destid
	for (destix = 0; destix < 4; ++destix)
		if (faceids[topid][destix] == destid)
			break;
	if (destix >= 4)
		return -1;

	// Return the direction that dest should be in
	return dirs[(topdir + destix) % 4];
}


// Given a top face, if we see another face in one direction, what is the
// orientation of the top face?
enum direction
faceid_orientation(int topid, int destid, enum direction destdir)
{
	static enum direction const dirs[] = { D_NORTH, D_WEST, D_SOUTH, D_EAST };
	int topdir, destix;

	// Go through topid's faces until we find destid
	for (destix = 0; destix < 4; ++destix)
		if (faceids[topid][destix] == destid)
			break;
	if (destix >= 4)
		return -1;

	// From faceid_find(), if dirs[topdir + destix] points to destdir,
	// then we just go through possible topdirs until we find the one
	// that makes this true
	for (topdir = 0; topdir < 4; ++topdir)
		if (dirs[(topdir + destix) % 4] == destdir)
			break;
	if (topdir >= 4)
		return -1;

	// Return the direction that dest should be in
	return dirs[topdir];
}


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;
	struct elf elf;
	char distance[8];
	int c, dlen = 0;

	while ((c = getopt(argc, argv, "p:m:")) != -1) {
		switch (c) {
		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;
}