Solve puzzle 22 part 1

1 files changed, 239 insertions, 0 deletions

diff --git a/22.c b/22.c
new file mode 100644
index 0000000..706d62a
--- /dev/null
+++ b/22.c
@@ -0,0 +1,239 @@
+
+#define _GNU_SOURCE
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+// Proper modulo operator
+#define modulo(n, m) ((((n) % (m)) + (m)) % (m))
+
+
+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;
+}
+
+
+enum direction
+direction_turn(enum direction dir, char turn)
+{
+#define direction_go(d, t) (1000 * (d) + (t))
+
+	switch (direction_go(dir, turn)) {
+	case direction_go(D_NORTH, 'R'):
+	case direction_go(D_SOUTH, 'L'):
+		return D_EAST;
+
+	case direction_go(D_NORTH, 'L'):
+	case direction_go(D_SOUTH, 'R'):
+		return D_WEST;
+
+	case direction_go(D_EAST, 'L'):
+	case direction_go(D_WEST, 'R'):
+		return D_NORTH;
+
+	case direction_go(D_EAST, 'R'):
+	case direction_go(D_WEST, 'L'):
+		return D_SOUTH;
+	}
+
+	fprintf(stderr, "Unexpected direction_turn(%d, %c)\n", dir, turn);
+	return D_NORTH;
+
+#undef direction_go
+}
+
+
+int
+map_move(char * map, int cols, int rows, int pos, enum direction dir, int distance)
+{
+	int skip, wrap, base;
+
+	switch (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", dir);
+		return -1;
+	}
+
+	base = (pos / wrap) * wrap;
+
+	while (distance > 0) {
+		int newpos = base + modulo(pos + skip, wrap);
+
+		while (map[newpos] == ' ' || map[newpos] == '\n')
+			newpos = base + modulo(newpos + skip, wrap);
+
+		switch (map[newpos]) {
+		case '.':
+			pos = newpos;
+			--distance;
+			break;
+
+		case '#':
+			distance = 0;
+			break;
+
+		default:
+			fprintf(stderr, "Unexpected map character %c\n", map[newpos]);
+			return -1;
+		}
+	}
+
+	return pos;
+}
+
+
+int
+main()
+{
+	char * buf = NULL, * beg, * end;
+	long bufsiz = 0, buflen = 0, maxline = 0, lines = 0;
+	long pos;
+	enum direction dir;
+	char distance[8], c;
+	int dlen = 0;
+
+
+	// 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
+	pos = 0;
+	dir = D_EAST;
+	while (buf[pos] != '.') {
+		++pos;
+	}
+
+	// Read and follow the movement instructions.
+	while (pos >= 0 && (c = fgetc(stdin)) != EOF) {
+		if (isdigit(c)) {
+			distance[dlen++] = c;
+		}
+		else if (c == 'L' || c == 'R') {
+			distance[dlen] = '\0';
+
+			pos = map_move(buf, maxline, lines, pos, dir, atoi(distance));
+
+			dir = direction_turn(dir, c);
+			dlen = 0;
+		}
+		else if (c == '\n') {
+			// Cover last bit of distance, if any
+			distance[dlen] = '\0';
+			pos = map_move(buf, maxline, lines, pos, dir, atoi(distance));
+			break;
+		}
+		else {
+			fprintf(stderr, "Unexpected movement instruction (%c)\n", c);
+			free(buf);
+			return -1;
+		}
+	}
+	if (pos < 0) {
+		free(buf);
+		return -1;
+	}
+
+	// Done.
+	printf("Password is %ld (%ld,%ld,%d)\n",
+			1000 * (1 + pos / maxline) + 4 * (1 + pos % maxline) + dir,
+			(1 + pos % maxline), (1 + pos / maxline), dir);
+
+	// Tidy and exit.
+	free(buf);
+
+	return 0;
+}
+