path: root/22.c

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


int
mymemswap(void * a, void * b, size_t len)
{
	char tmp[BUFSIZ];

	if (a == b)
		return 0;

	while (len > 0) {
		size_t chunk = len < sizeof(tmp) ? len : sizeof(tmp);

		memcpy(tmp, a, chunk);
		memcpy(a, b, chunk);
		memcpy(b, tmp, chunk);
		len -= chunk;
	}

	return 0;
}


struct point {
	int x;
	int y;
};


struct point *
point_init(struct point * pt, int x, int y)
{
	pt->x = x;
	pt->y = y;
	return pt;
}


struct face {
	struct point vertices[4];
	enum direction dir;	// The orientation of the face (as in faceids[])
};


struct face *
face_init(struct face * face, struct point const * bl, struct point const * tr,
		enum direction dir)
{
	if (bl->x >= tr->x || bl->y >= tr->y)
		return NULL;

	point_init(face->vertices + 0, bl->x, bl->y);
	point_init(face->vertices + 1, tr->x, bl->y);
	point_init(face->vertices + 2, tr->x, tr->y);
	point_init(face->vertices + 3, bl->x, tr->y);
	face->dir = dir;
	return face;
}


struct map {
	char * _buf;
	int cols;
	int rows;
	enum map_type type;
	struct face faces[6];
};


int map_elem(struct map const * map, int x, int y);

struct face const * map_face_at(struct map const * map, int x, int y);

int map_outline(struct point ** outline, struct map const * map);


static
int
map__init_faces_reorder(struct map * map, struct face const * face, struct face const * from)
{
	static enum direction const dirs[] = { D_NORTH, D_WEST, D_SOUTH, D_EAST };

	int fsrcid, dir;

	fsrcid = face - map->faces;

	for (dir = 0; dir < 4; ++dir) {
		struct face * nbr;
		int nbrid;

		// Get the neighbour in the net in one of the directions
		switch (dirs[dir]) {
		case D_NORTH:
			nbr = (struct face *) map_face_at(map, face->vertices[3].x, face->vertices[3].y);
			break;

		case D_WEST:
			nbr = (struct face *) map_face_at(map, face->vertices[0].x - 1, face->vertices[0].y);
			break;

		case D_SOUTH:
			nbr = (struct face *) map_face_at(map, face->vertices[0].x, face->vertices[0].y - 1);
			break;

		case D_EAST:
			nbr = (struct face *) map_face_at(map, face->vertices[1].x, face->vertices[1].y);
			break;

		default:
			nbr = NULL;
			break;
		}

		if (!nbr)
			// There is no neighbour in the net at that location.
			continue;
		if (nbr == from)
			// The neighbour is the face that told us to rearrange
			// our neighbours. Do nothing.
			continue;

		// Find the id of the neighbour
		nbrid = faceid_look(fsrcid, face->dir, dirs[dir]);

		// Move the face into the right position in faces[]
		mymemswap(map->faces + nbrid, nbr, sizeof(struct face));
		nbr = map->faces + nbrid;

		// Set its direction.
		nbr->dir = faceid_orientation(nbrid, fsrcid, dirs[(dir + 2) % 4]);

		// And reorder the faces around it
		map__init_faces_reorder(map, nbr, face);
	}

	return 0;
}


static
int
map__init_faces(struct map * map)
{
	struct point * outline, * ol, min, max, pt;
	int len, nfaces;

	if ((len = map_outline(&outline, map)) < 0) {
		return -1;
	}

	// Find the limits of the outline
	ol = outline;
	point_init(&min, ol->x, ol->y);
	point_init(&max, ol->x, ol->y);
	for (++ol; ol < outline + len - 1; ++ol) {
		if (ol->x < min.x)
			min.x = ol->x;
		if (ol->x > max.x)
			max.x = ol->x;
		if (ol->y < min.y)
			min.y = ol->y;
		if (ol->x > max.x)
			max.y = ol->y;
	}

	// Go through all combinations of x and y coordinates in the outline,
	// find pairs that are the bottom-left corners of faces, and create
	// faces out of them.
	nfaces = 0;
	pt = min;
	while (pt.y != max.y) {
		struct point next;

		// Find the "next" individual x and y coords in the outline
		next = max;
		for (ol = outline; ol < outline + len - 1; ++ol) {
			if (ol->x > pt.x && ol->x < next.x)
				next.x = ol->x;
			if (ol->y > pt.y && ol->y < next.y)
				next.y = ol->y;
		}

		// Is the current point a face?
		if (map_elem(map, pt.x, pt.y) != ' ') {
			if (nfaces == 6) {
				fprintf(stderr, "%s: Already %d faces at %d,%d\n",
						__FUNCTION__, nfaces, pt.x, pt.y);
				free(outline);
				return -1;
			}
			// Set to north for now. Will change later.
			face_init(map->faces + nfaces, &pt, &next, D_NORTH);
			++nfaces;
		}

		// Try the next candidate point
		pt.x = next.x;
		if (pt.x == max.x) {
			pt.x = min.x;
			pt.y = next.y;
		}
	}
	if (nfaces != 6) {
		// TODO: Add face-splitting logic here, to account for e.g.
		// T-shaped nets, where we don't have outline corners to tell
		// us where the faces are.
		fprintf(stderr, "%s: Only %d faces\n", __FUNCTION__, nfaces);
		free(outline);
		return -1;
	}

	// Reorder the faces around face 0, so that each face is in the right
	// place in the faces[] array, and oriented appropriately, according
	// to faceids[]
	map__init_faces_reorder(map, map->faces + 0, NULL);

	free(outline);
	return 0;
}


// 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';
	}

	if (map->type == M_NET) {
		if (map__init_faces(map) != 0) {
			free(map->_buf);
			return NULL;
		}

		fprintf(stderr, "Faces initialised\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];
}


// Get the face at a particular x,y co-ordinate
struct face const *
map_face_at(struct map const * map, int x, int y)
{
	struct face const * face;

	if (map->type != M_NET)
		return NULL;

	for (face = map->faces; face < map->faces + 6; ++face)
		if (x >= face->vertices[0].x && x < face->vertices[2].x
				&& y >= face->vertices[0].y && y < face->vertices[2].y)
			return face;

	return NULL;
}


// Get the outline of the map, anti-clockwise
//
// Note that for lengths to be correct, as we're tracing south and east we keep
// inside the map, but as we're tracing north and west we keep one element
// outside the map.
//
// Duplicates the first/last corner, because this makes some things easier.
//
// Returns number of corners found (including duplicate), or -1 on error
int
map_outline(struct point ** outline, struct map const * map)
{
	struct point * pt;
	int len = 2;
	enum direction dir;

	if ((*outline = malloc(len * sizeof(struct point))) == NULL) {
		fprintf(stderr, "%s: Bad malloc(%ld)\n",
				__FUNCTION__, len * sizeof(struct point));
		return -1;
	}

	// Start from the top-left, because we know there has to be a
	// starting point for the elf there, and head south.
	pt = *outline;
	point_init(pt, 0, map->rows - 1);
	while (map_elem(map, pt->x, pt->y) == ' ')
		++pt->x;
	++pt->y;
	dir = D_SOUTH;

	while (1) {
		struct point pt_move, pt_left, pt_right;
		enum direction turn_left, turn_right;

		// Based on which direction we're going, figure out how to move
		// forward, which elements to look at to decide if we need to
		// turn left or right, and which way is left and right.
		switch (dir) {
		case D_NORTH:
			point_init(&pt_move, 0, 1);
			point_init(&pt_left, -1, 0);
			point_init(&pt_right, 0, 0);
			turn_left = D_WEST;
			turn_right = D_EAST;
			break;

		case D_SOUTH:
			point_init(&pt_move, 0, -1);
			point_init(&pt_left, 0, -1);
			point_init(&pt_right, -1, -1);
			turn_left = D_EAST;
			turn_right = D_WEST;
			break;

		case D_EAST:
			point_init(&pt_move, 1, 0);
			point_init(&pt_left, 0, 0);
			point_init(&pt_right, 0, -1);
			turn_left = D_NORTH;
			turn_right = D_SOUTH;
			break;

		case D_WEST:
			point_init(&pt_move, -1, 0);
			point_init(&pt_left, -1, -1);
			point_init(&pt_right, -1, 1);
			turn_left = D_SOUTH;
			turn_right = D_NORTH;
			break;
		}

		// Move forward until we need to turn
		pt = *outline + len - 1;
		point_init(pt, (pt - 1)->x, (pt - 1)->y);
		while (1) {
			pt->x += pt_move.x;
			pt->y += pt_move.y;

			if (map_elem(map, pt->x + pt_left.x, pt->y + pt_left.y) == ' ') {
				dir = turn_left;
				break;
			}
			if (map_elem(map, pt->x + pt_right.x, pt->y + pt_right.y) != ' ') {
				dir = turn_right;
				break;
			}
		}

		// Is the turning point back at the start? If so, we're done.
		if (len > 4 && pt->x == (*outline)->x && pt->y == (*outline)->y)
			return len;

		// Sanity check
		if (len > 100) {
			fprintf(stderr, "%s: Too many corners (%d)!\n",
					__FUNCTION__, len);
			free(*outline);
			*outline = NULL;
			return -1;
		}

		// No? OK, add a new point to check for.
		++len;
		if ((pt = realloc(*outline, len * sizeof(struct point))) == NULL) {
			fprintf(stderr, "%s: Bad realloc(%ld)\n",
					__FUNCTION__, len * sizeof(struct point));
			free(*outline);
			*outline = NULL;
			return -1;
		}
		*outline = pt;
	}

	fprintf(stderr, "%s: Unreachable!\n", __FUNCTION__);
	free(*outline);
	*outline = NULL;
	return -1;
}


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