diff options
| -rw-r--r-- | 9.c | 131 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 132 insertions, 0 deletions
@@ -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; +} + @@ -10,6 +10,7 @@ all: bin \ bin/6 \ bin/7 \ bin/8 \ + bin/9 \ bin: mkdir -p $@ |