#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 elf {
	long pos;
	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, char const * map, int cols, int rows, enum map_type mtype, int distance)
{
	while (distance > 0) {
		int skip, wrap, base, newpos;

		switch (elf->dir) {
		case D_NORTH:
			skip = -cols;
			wrap = cols * rows;
			break;

		case D_EAST:
			skip = 1;
			wrap = cols;
			break;

		case D_SOUTH:
			skip = cols;
			wrap = cols * rows;
			break;

		case D_WEST:
			skip = -1;
			wrap = cols;
			break;

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

		base = (elf->pos / wrap) * wrap;

		newpos = base + modulo(elf->pos + skip, wrap);

		if (map[newpos] == ' ' || map[newpos] == '\n') {
			switch (mtype) {
			case M_FLAT:
				// Just keep going until we wrap around to a non-blank position
				while (map[newpos] == ' ' || map[newpos] == '\n')
					newpos = base + modulo(newpos + skip, wrap);
				break;

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

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

		switch (map[newpos]) {
		case '.':
			elf->pos = newpos;
			--distance;
			break;

		case '#':
			distance = 0;
			break;

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

	return 0;
}


int
main(int argc, char ** argv)
{
	char * buf = NULL, * beg, * end;
	enum map_type mtype = M_FLAT;
	long bufsiz = 0, buflen = 0, maxline = 0, lines = 0;
	long pos;
	struct elf elf;
	char distance[8], c;
	int 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);
	}

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

	// Resize the map data buffer to hold a full grid of data
	if ((beg = realloc(buf, lines * maxline)) == NULL) {
		fprintf(stderr, "Bad realloc(%ld)\n", bufsiz);
		free(buf);
		return -1;
	}
	buf = beg;
	memset(buf + buflen, ' ', lines * maxline - buflen);

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

	// Set initial position
	elf.pos = 0;
	elf.dir = D_EAST;
	while (buf[elf.pos] != '.')
		++elf.pos;

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

			if (elf_move(&elf, buf, maxline, lines, mtype, atoi(distance)) != 0)
				elf.pos = -1;
			if (elf_turn(&elf, c) != 0)
				elf.pos = -1;

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

	// Done.
	printf("Password is %ld (%ld,%ld,%d)\n",
			1000 * (1 + elf.pos / maxline) + 4 * (1 + elf.pos % maxline) + elf.dir,
			(1 + elf.pos % maxline), (1 + elf.pos / maxline), elf.dir);

	// Tidy and exit.
	free(buf);

	return 0;
}