1 files changed, 131 insertions, 0 deletions
diff --git a/9.c b/9.c
new file mode 100644
index 0000000..d0c6a9f
--- /dev/null
+++ b/9.c
@@ -0,0 +1,131 @@
+
+//#define _GNU_SOURCE
+
+#include <ctype.h>
+#include <search.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+struct point {
+	int x;
+	int y;
+};
+
+
+struct point *
+point_copy(struct point const * other)
+{
+	struct point * p = malloc(sizeof(struct point));
+	if (!p)
+		return NULL;
+	p->x = other->x;
+	p->y = other->y;
+	return p;
+}
+
+
+int
+point_cmp(struct point const * a, struct point const * b)
+{
+	return a->x - b->x != 0
+		? a->x - b->x
+		: a->y - b->y;
+}
+
+
+int
+point_tcmp(void const * a, void const * b)
+{
+	return point_cmp(a, b);
+}
+
+
+int
+main()
+{
+	char buf[BUFSIZ];
+	struct point head = {0}, * tail = point_copy(&head);
+	void * tails = NULL;
+	int ntails = 0;
+
+	tsearch(tail, &tails, point_tcmp);
+	++ntails;
+	fprintf(stderr, "Tail visiting %d,%d\n", tail->x, tail->y);
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		int dist, dx, dy;
+
+		if (!isalpha(buf[0])
+				|| buf[1] != ' '
+				|| !isdigit(buf[2]))
+		{
+			fprintf(stderr, "Unexpected input: %s\n", buf);
+			return -1;
+		}
+
+		dist = atoi(buf + 2);
+		if (dist == 0) {
+			fprintf(stderr, "Unexpected distance in: %s\n", buf);
+			// Allow 0 for now...
+		}
+		switch (buf[0]) {
+		case 'L': head.x -= dist; break;
+		case 'R': head.x += dist; break;
+		case 'U': head.y += dist; break;
+		case 'D': head.y -= dist; break;
+		default:
+			  fprintf(stderr, "Unexpected input: %s\n", buf);
+			  return -1;
+		}
+		fprintf(stderr, "Head %c %d to %d,%d\n", buf[0], dist, head.x, head.y);
+
+		dx = head.x - tail->x;
+		dy = head.y - tail->y;
+		while (dx * dx + dy * dy > 2) {
+			struct point ** pp;
+
+			if (dx > 0) {
+				++tail->x;
+				--dx;
+			}
+			if (dx < 0) {
+				--tail->x;
+				++dx;
+			}
+			if (dy > 0) {
+				++tail->y;
+				--dy;
+			}
+			if (dy < 0) {
+				--tail->y;
+				++dy;
+			}
+			fprintf(stderr, " Tail visiting %d,%d", tail->x, tail->y);
+
+			// Search/insert current tail in visited tails
+			pp = tsearch(tail, &tails, point_tcmp);
+			if (*pp == tail) {
+				// This was a new one, tail is now in the tree
+				//fprintf(stderr, " (new)");
+				tail = point_copy(tail);
+				++ntails;
+			}
+			else {
+				fprintf(stderr, " (old)");
+			}
+
+			fprintf(stderr, "\n");
+		}
+	}
+
+	printf("Unique tail spots visited: %d\n", ntails);
+
+	free(tail);
+#ifdef _GNU_SOURCE
+	tdestroy(tails, free);
+#endif
+
+	return 0;
+}
+