diff options
Diffstat (limited to '9.c')
| -rw-r--r-- | 9.c | 136 |
1 files changed, 93 insertions, 43 deletions
@@ -5,6 +5,7 @@ #include <search.h> #include <stdio.h> #include <stdlib.h> +#include <unistd.h> struct point { @@ -14,17 +15,24 @@ struct point { struct point * -point_copy(struct point const * other) +point_create(int x, int y) { struct point * p = malloc(sizeof(struct point)); if (!p) return NULL; - p->x = other->x; - p->y = other->y; + p->x = x; + p->y = y; return p; } +struct point * +point_copy(struct point const * other) +{ + return point_create(other->x, other->y); +} + + int point_cmp(struct point const * a, struct point const * b) { @@ -42,19 +50,49 @@ point_tcmp(void const * a, void const * b) int -main() +main(int argc, char ** argv) { + int len = 2, i; char buf[BUFSIZ]; - struct point head = {0}, * tail = point_copy(&head); + struct point * rope; void * tails = NULL; int ntails = 0; - tsearch(tail, &tails, point_tcmp); - tail = point_copy(tail); + while ((i = getopt(argc, argv, "p:l:")) != -1) { + switch (i) { + case 'p': + switch (atoi(optarg)) { + case 1: len = 2; break; + case 2: len = 10; break; + default: + fprintf(stderr, "Unexpected part: %s\n", optarg); + return -1; + } + break; + + case 'l': + len = atoi(optarg); + if (len < 2) { + fprintf(stderr, "Unexpected length: %d\n", len); + return -1; + } + break; + + default: + return -1; + } + } + + rope = malloc(len * sizeof(struct point)); + for (i = 0; i < len; ++i) { + rope[i].x = rope[i].y = 0; + } + + tsearch(point_create(0, 0), &tails, point_tcmp); ++ntails; while (fgets(buf, sizeof(buf), stdin)) { - int dist, dx, dy; + int dist; if (!isalpha(buf[0]) || buf[1] != ' ' @@ -69,51 +107,63 @@ main() 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; - } + while (dist > 0) { + int seg; + + switch (buf[0]) { + case 'L': --rope[0].x; break; + case 'R': ++rope[0].x; break; + case 'U': ++rope[0].y; break; + case 'D': --rope[0].y; break; + default: + fprintf(stderr, "Unexpected input: %s\n", buf); + return -1; + } - dx = head.x - tail->x; - dy = head.y - tail->y; - while (dx * dx + dy * dy > 2) { - struct point ** pp; + for (seg = 1; seg < len; ++seg) { + int dx, dy; - if (dx > 0) { - ++tail->x; - --dx; - } - if (dx < 0) { - --tail->x; - ++dx; - } - if (dy > 0) { - ++tail->y; - --dy; - } - if (dy < 0) { - --tail->y; - ++dy; + dx = rope[seg - 1].x - rope[seg].x; + dy = rope[seg - 1].y - rope[seg].y; + + if (dx * dx + dy * dy <= 2) + break; + + if (dx > 0) + ++rope[seg].x; + if (dx < 0) + --rope[seg].x; + if (dy > 0) + ++rope[seg].y; + if (dy < 0) + --rope[seg].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 - tail = point_copy(tail); - ++ntails; + if (seg == len) { + // Had to move all segments, including tail. + // Check if it's a new tail pos + struct point * tail, ** pp; + + // Search/insert current tail in visited tails + tail = point_copy(rope + len - 1); + pp = tsearch(tail, &tails, point_tcmp); + if (*pp == tail) { + // This was a new one, tail is now in the tree + ++ntails; + } + else { + // Tail already in tree, free the one we just created. + free(tail); + } } + + --dist; } } printf("Unique tail spots visited: %d\n", ntails); - free(tail); + free(rope); #ifdef _GNU_SOURCE tdestroy(tails, free); #endif |