1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
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;
}
|
