Solve puzzle 12 part 1

1 files changed, 176 insertions, 0 deletions

diff --git a/12.c b/12.c
new file mode 100644
index 0000000..c647410
--- /dev/null
+++ b/12.c
@@ -0,0 +1,176 @@
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+struct pos {
+	int x;
+	int y;
+	struct pos * next;
+};
+
+
+struct pos *
+pos_create(int x, int y, struct pos * next)
+{
+	struct pos * p = malloc(sizeof(struct pos));
+	if (!p)
+		return NULL;
+	p->x = x;
+	p->y = y;
+	p->next = next;
+	return p;
+}
+
+
+void
+pos_free(struct pos * p)
+{
+	if (!p)
+		return;
+	pos_free(p->next);
+	free(p);
+}
+
+
+int
+visited(unsigned char c)
+{
+	return c & 0x80;
+}
+
+
+int
+height(unsigned char c)
+{
+	c &= 0x7F;
+
+	switch (c) {
+	case 'S': return 'a';
+	case 'E': return 'z';
+	}
+	return c;
+}
+
+
+int
+tryvisit(unsigned char * range, int cols, int rows, struct pos const * from, int dx, int dy)
+{
+	int x, y;
+	unsigned char src, dst;
+
+	x = from->x + dx;
+	y = from->y + dy;
+
+	// Check bounds.
+	if (x < 0 || x >= cols - 1
+			|| y < 0 || y >= rows)
+		return 0;
+
+	// Check if already visited
+	dst = range[x + y * cols];
+	if (visited(dst))
+		return 0;
+
+	// Check height
+	src = range[from->x + from->y * cols];
+	if (height(dst) > height(src) + 1)
+		return 0;
+
+	// OK. We can visit, so mark the new position as visited.
+	range[x + y * cols] |= 0x80;
+
+	return 1;
+}
+
+
+int
+main()
+{
+	unsigned char * range, * p;
+	size_t rangesize, rangelen, bytes;
+	int cols, rows;
+	struct pos * front;
+	int steps;
+
+	// Read hill range
+	rangesize = BUFSIZ;
+	rangelen = 0;
+	range = malloc(rangesize);
+	while ((bytes = fread(range + rangelen, 1, rangesize - rangelen, stdin)) > 0) {
+		rangelen += bytes;
+		if (rangelen == rangesize) {
+			rangesize += BUFSIZ;
+			if ((p = realloc(range, rangesize)) == NULL) {
+				fprintf(stderr, "realloc(%zu) failed\n", rangesize);
+				free(range);
+				return -1;
+			}
+			range = p;
+		}
+	}
+
+	// Get cols/rows in hill range
+	if ((p = memchr(range, '\n', rangelen)) == NULL) {
+		fprintf(stderr, "No lines found in input!\n");
+		free(range);
+		return -1;
+	}
+	cols = p - range + 1;
+	if (rangelen % cols != 0) {
+		fprintf(stderr, "Input length %zu is not a multiple of line length %d\n",
+				rangelen, cols);
+		free(range);
+		return -1;
+	}
+	rows = rangelen / cols;
+
+	// Find start, and mark it as visited
+	if ((p = memchr(range, 'S', rangelen)) == NULL) {
+		fprintf(stderr, "No start position!\n");
+		free(range);
+		return -1;
+	}
+	front = pos_create((p - range) % cols, (p - range) / cols, NULL);
+	range[front->x + front->y * cols] |= 0x80;
+
+	// Take steps, widening the search front each iteration.
+	for (steps = 0; 1; ++steps) {
+		struct pos * nextfront = NULL;
+		struct pos * loc;
+
+		for (loc = front; loc != NULL; loc = loc->next) {
+			if ((range[loc->x + loc->y * cols] & 0x7F) == 'E')
+				// We found the end point!
+				break;
+
+			if (tryvisit(range, cols, rows, loc, -1, 0))
+				nextfront = pos_create(loc->x - 1, loc->y, nextfront);
+			if (tryvisit(range, cols, rows, loc, +1, 0))
+				nextfront = pos_create(loc->x + 1, loc->y, nextfront);
+			if (tryvisit(range, cols, rows, loc, 0, -1))
+				nextfront = pos_create(loc->x, loc->y - 1, nextfront);
+			if (tryvisit(range, cols, rows, loc, 0, +1))
+				nextfront = pos_create(loc->x, loc->y + 1, nextfront);
+		}
+		if (loc) {
+			// Create a duplicate of the final location at the start
+			// of the current search front
+			front = pos_create(loc->x, loc->y, front);
+			pos_free(nextfront);
+			break;
+		}
+
+		pos_free(front);
+		front = nextfront;
+	}
+
+	printf("Found end at %d,%d in %d steps\n", front->x, front->y, steps);
+
+	pos_free(front);
+	free(range);
+
+	return 0;
+}
+