gopher-clustering.c - brcon2024-hackathons - Bitreichcon 2024 Hackathons | |
git clone git://bitreich.org/brcon2024-hackathons git://enlrupgkhuxnvlhsf6lc3fz… | |
Log | |
Files | |
Refs | |
Tags | |
Submodules | |
--- | |
gopher-clustering.c (48223B) | |
--- | |
1 #define _POSIX_C_SOURCE 200112L | |
2 | |
3 #include <assert.h> | |
4 #include <stdarg.h> | |
5 #include <stdint.h> | |
6 #include <stdio.h> | |
7 #include <stdlib.h> | |
8 #include <string.h> | |
9 | |
10 #include <math.h> | |
11 | |
12 #include <netdb.h> | |
13 #include <sys/socket.h> | |
14 #include <sys/types.h> | |
15 #include <termios.h> | |
16 #include <unistd.h> | |
17 | |
18 uint32_t | |
19 fnv1a(int n,...) | |
20 { | |
21 int i; | |
22 char *s; | |
23 va_list l; | |
24 uint32_t h; | |
25 | |
26 h = 0x811c9dc5; | |
27 | |
28 va_start(l, n); | |
29 for (i = 0; i < n; i++) { | |
30 for (s = va_arg(l, char*); *s; s++) { | |
31 h ^= *s; | |
32 h *= 0x01000193; | |
33 } | |
34 } | |
35 va_end(l); | |
36 | |
37 return h; | |
38 } | |
39 | |
40 uint32_t | |
41 xorshift(uint32_t *s) | |
42 { | |
43 *s ^= *s << 13; | |
44 *s ^= *s >> 17; | |
45 *s ^= *s << 5; | |
46 return *s; | |
47 } | |
48 | |
49 /* | |
50 https://github.com/skeeto/hash-prospector/issues/19#issuecomment… | |
51 */ | |
52 uint32_t | |
53 mix(uint32_t x) | |
54 { | |
55 x ^= x >> 16; | |
56 x *= 0x21f0aaad; | |
57 x ^= x >> 15; | |
58 x *= 0x735a2d97; | |
59 x ^= x >> 16; | |
60 return x; | |
61 } | |
62 | |
63 struct cell { | |
64 void *data; | |
65 char c; | |
66 }; | |
67 | |
68 #define MAPHEIGHT (50) | |
69 #define MAPWIDTH (160) | |
70 struct cell map[MAPHEIGHT][MAPWIDTH]; | |
71 | |
72 struct gopherentry { | |
73 struct gopherentry *next; | |
74 char type; | |
75 char *fields[4]; | |
76 size_t i, s; | |
77 }; | |
78 | |
79 char * | |
80 gopher_fieldend(char *s) | |
81 { | |
82 for (; *s; s++) { | |
83 if (*s == '\t') | |
84 break; | |
85 if (*s == '\r' && *(s+1) == '\n') | |
86 break; | |
87 if (*s == '\n') | |
88 break; | |
89 } | |
90 return s; | |
91 } | |
92 | |
93 char * | |
94 gopher_nextentry(char *s) | |
95 { | |
96 char *c; | |
97 | |
98 if (c = strchr(s, '\n')) | |
99 return c + 1; | |
100 return NULL; | |
101 } | |
102 | |
103 void * | |
104 xmalloc(size_t s) | |
105 { | |
106 void *p; | |
107 | |
108 if (!(p = malloc(s))) { | |
109 perror(NULL); | |
110 exit(1); | |
111 } | |
112 return p; | |
113 } | |
114 | |
115 void * | |
116 xrealloc(void *p, size_t s) | |
117 { | |
118 if (!(p = realloc(p, s))) { | |
119 perror(NULL); | |
120 exit(1); | |
121 } | |
122 return p; | |
123 } | |
124 | |
125 /* Allow a lot of ugly things... */ | |
126 size_t | |
127 gopher_parsemenu(char *d, struct gopherentry **g) | |
128 { | |
129 ssize_t gl; | |
130 size_t fl, i, s; | |
131 char *c, *p, pt; | |
132 struct gopherentry *cg; | |
133 | |
134 gl = 0; | |
135 cg = NULL; | |
136 | |
137 s = 0; | |
138 pt = 0; | |
139 for (c = d; c && *c; c = gopher_nextentry(c)) { | |
140 if (*c == '.') | |
141 break; | |
142 if (*c == '\n') | |
143 continue; | |
144 | |
145 gl++; | |
146 cg = xrealloc(cg, gl * sizeof(struct gopherentry)); | |
147 memset(&cg[gl-1], 0, sizeof(struct gopherentry)); | |
148 | |
149 if (*c != 'i' && pt == 'i') | |
150 s++; | |
151 pt = *c; | |
152 | |
153 cg[gl-1].type = *c; | |
154 cg[gl-1].i = gl-1; | |
155 cg[gl-1].s = s; | |
156 c++; | |
157 | |
158 for (i = 0; i < 4; i++) { | |
159 p = gopher_fieldend(c); | |
160 fl = p - c; | |
161 cg[gl-1].fields[i] = xmalloc(fl + 1); | |
162 memcpy(cg[gl-1].fields[i], c, fl); | |
163 cg[gl-1].fields[i][fl] = '\0'; | |
164 if (*p != '\t') | |
165 break; | |
166 c = p + 1; | |
167 } | |
168 } | |
169 s++; | |
170 *g = cg; | |
171 return gl; | |
172 } | |
173 | |
174 ssize_t | |
175 gopher_removeentries(struct gopherentry *g, size_t l) | |
176 { | |
177 size_t i, j; | |
178 | |
179 for (i = 0; i < l;) { | |
180 if ((g[i].type == 'i' && g[i].type == '3') || !g[i].fiel… | |
181 l--; | |
182 memmove(&g[i], &g[i+1], (l - i) * sizeof(*g)); | |
183 continue; | |
184 } | |
185 for (j = 0; j < i; j++) { | |
186 if (!strcmp(g[i].fields[1], g[j].fields[1]) && | |
187 !strcmp(g[i].fields[2], g[j].fields[2]) && | |
188 !strcmp(g[i].fields[3], g[j].fields[3])) | |
189 break; | |
190 } | |
191 if (j < i) { | |
192 l--; | |
193 memmove(&g[i], &g[i+1], (l - i) * sizeof(*g)); | |
194 continue; | |
195 } | |
196 i++; | |
197 } | |
198 | |
199 return l; | |
200 } | |
201 | |
202 ssize_t | |
203 gopher_request(char *host, char *port, char *selector, char *buffer, siz… | |
204 { | |
205 int fd; | |
206 struct addrinfo hints; | |
207 struct addrinfo *r, *rp; | |
208 ssize_t n, result, rn; | |
209 | |
210 memset(&hints, 0, sizeof(hints)); | |
211 hints.ai_family = AF_UNSPEC; | |
212 hints.ai_socktype = SOCK_STREAM; | |
213 | |
214 if (getaddrinfo(host, port, &hints, &r) != 0) | |
215 return -1; | |
216 | |
217 for (rp = r; rp; rp = rp->ai_next) { | |
218 if ((fd = socket(rp->ai_family, rp->ai_socktype, rp->ai_… | |
219 continue; | |
220 if (connect(fd, rp->ai_addr, rp->ai_addrlen) != -1) | |
221 break; | |
222 close(fd); | |
223 } | |
224 freeaddrinfo(r); | |
225 if (!rp) | |
226 return -1; | |
227 | |
228 result = -1; | |
229 if (write(fd, selector, strlen(selector)) != strlen(selector)) | |
230 goto cleanup; | |
231 | |
232 if (write(fd, "\r\n", 2) != 2) | |
233 goto cleanup; | |
234 | |
235 n = 0; | |
236 while (1) { | |
237 if (n + 512 > l - 1) | |
238 goto cleanup; | |
239 if ((rn = read(fd, &buffer[n], 512)) == -1) | |
240 goto cleanup; | |
241 else if (!rn) | |
242 break; | |
243 n += rn; | |
244 } | |
245 | |
246 buffer[n] = '\0'; | |
247 result = n; | |
248 | |
249 cleanup: | |
250 close(fd); | |
251 | |
252 return result; | |
253 } | |
254 | |
255 size_t | |
256 triangularnumber(size_t n) | |
257 { | |
258 return (n * n + n) / 2; | |
259 } | |
260 | |
261 size_t | |
262 distanceindex(size_t i, size_t j) | |
263 { | |
264 size_t t; | |
265 | |
266 if (i < j) { | |
267 t = i; | |
268 i = j; | |
269 j = t; | |
270 } | |
271 | |
272 return triangularnumber(i) + j; | |
273 } | |
274 | |
275 /* | |
276 https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_wit… | |
277 Which references https://www.codeproject.com/Articles/13525/Fast… | |
278 The code there is using the CPOL: https://www.codeproject.com/in… | |
279 */ | |
280 size_t | |
281 levenshteindistance(char *a, char *b) | |
282 { | |
283 size_t i, j, dc, ic, sc, r; | |
284 size_t *v0, *v1, *t; | |
285 | |
286 v0 = xmalloc((strlen(b) + 1) * sizeof(*v0)); | |
287 v1 = xmalloc((strlen(b) + 1) * sizeof(*v1)); | |
288 | |
289 for (i = 0; i <= strlen(b); i++) | |
290 v0[i] = i; | |
291 | |
292 for (i = 0; i < strlen(a); i++) { | |
293 v1[0] = i + 1; | |
294 for (j = 0; j < strlen(b); j++) { | |
295 dc = v0[j + 1] + 1; | |
296 ic = v1[j] + 1; | |
297 if (a[i] == b[j]) | |
298 sc = v0[j]; | |
299 else | |
300 sc = v0[j] + 1; | |
301 if (dc < ic && dc < sc) | |
302 v1[j + 1] = dc; | |
303 else if (ic < dc && ic < sc) | |
304 v1[j + 1] = ic; | |
305 else | |
306 v1[j + 1] = sc; | |
307 } | |
308 t = v0; | |
309 v0 = v1; | |
310 v1 = t; | |
311 } | |
312 | |
313 r = v0[strlen(b)]; | |
314 | |
315 free(v1); | |
316 free(v0); | |
317 | |
318 return r; | |
319 } | |
320 | |
321 /* | |
322 Remove common prefix and suffix. The pazz0distance is the sum of… | |
323 */ | |
324 size_t | |
325 pazz0distance(char *a, char *b) | |
326 { | |
327 size_t pl, sl; | |
328 size_t al, bl; | |
329 | |
330 al = strlen(a); | |
331 bl = strlen(b); | |
332 | |
333 for (pl = 0; pl < al && pl < bl && a[pl] == b[pl]; pl++); | |
334 for (sl = 0; al - sl > pl && bl - sl > pl && a[al - 1 - sl] == b… | |
335 | |
336 return al + bl - 2 * (pl + sl); | |
337 } | |
338 | |
339 struct point { | |
340 double dims[2]; | |
341 }; | |
342 | |
343 void | |
344 sammon(double *distances, size_t l, uint32_t prng, struct point *points) | |
345 { | |
346 size_t i, j, k, t, tmax; | |
347 double *gnarf; | |
348 double c, lr; | |
349 double e1, e2, sum, lasterror; | |
350 struct point *newpoints; | |
351 | |
352 gnarf = calloc(triangularnumber(l), sizeof(*gnarf)); | |
353 newpoints = calloc(l, sizeof(*newpoints)); | |
354 | |
355 for (i = 0; i < l; i++) { | |
356 points[i].dims[0] = (double)xorshift(&prng) / UINT32_MAX… | |
357 points[i].dims[1] = (double)xorshift(&prng) / UINT32_MAX… | |
358 } | |
359 | |
360 c = 0; | |
361 for (i = 0; i < l; i++) { | |
362 gnarf[distanceindex(i, i)] = 0; | |
363 for (j = 0; j < i; j++) { | |
364 gnarf[distanceindex(i, j)] = sqrt(pow(points[i].… | |
365 c += distances[distanceindex(i, j)]; | |
366 } | |
367 } | |
368 | |
369 lasterror = 0; | |
370 for (t = 0, tmax = 1 << 12; t < tmax; t++) { | |
371 lr = 0.01; | |
372 for (i = 0; i < l; i++) { | |
373 for (j = 0; j < 2; j++) { | |
374 e1 = -2. / c; | |
375 sum = 0; | |
376 for (k = 0; k < l; k++) { | |
377 if (i == k) | |
378 continue; | |
379 sum += (distances[distanceindex(… | |
380 } | |
381 e1 *= sum; | |
382 | |
383 e2 = -2. / c; | |
384 sum = 0; | |
385 for (k = 0; k < l; k++) { | |
386 if (i == k) | |
387 continue; | |
388 sum += 1. / (distances[distancei… | |
389 } | |
390 e2 *= sum; | |
391 | |
392 newpoints[i].dims[j] = points[i].dims[j]… | |
393 } | |
394 } | |
395 | |
396 sum = 0; | |
397 for (i = 0; i < l; i++) { | |
398 for (j = 0; j < i; j++) { | |
399 gnarf[distanceindex(i, j)] = sqrt(pow(ne… | |
400 sum += pow(distances[distanceindex(i, j)… | |
401 } | |
402 } | |
403 printf("%lf\n", sum / c); | |
404 if (t > 0 && fabs(sum / c - lasterror) < 0.000000000001) | |
405 break; | |
406 lasterror = sum / c; | |
407 | |
408 memcpy(points, newpoints, l * sizeof(*points)); | |
409 } | |
410 | |
411 free(newpoints); | |
412 free(gnarf); | |
413 } | |
414 | |
415 int | |
416 dynmsc(struct gopherentry *g, size_t l, size_t k, double *distances, siz… | |
417 { | |
418 size_t i, j, n, ck; | |
419 ssize_t m1, m, m2; | |
420 size_t ti, th, huh; | |
421 size_t iter; | |
422 double dsum, d, d2, gnarf, tdsum; | |
423 struct { | |
424 size_t medoid; | |
425 size_t n; | |
426 double dsum; | |
427 } *clusters; | |
428 struct { | |
429 size_t n1, n2, n3; | |
430 double d1, d2, d3; | |
431 } *cache; | |
432 double *dS, *dS2; | |
433 double cdS, cdS2; | |
434 size_t cm, cx; | |
435 ssize_t lx; | |
436 int flag, result; | |
437 uint32_t r; | |
438 double *C; | |
439 | |
440 if (!l) | |
441 return 0; | |
442 | |
443 if (l < k) | |
444 k = l; | |
445 | |
446 clusters = calloc(k, sizeof(*clusters)); | |
447 if (!clusters) | |
448 return -1; | |
449 | |
450 result = -1; | |
451 | |
452 /* | |
453 Seed the medoids randomly | |
454 */ | |
455 for (i = n = 0; i < l; i++) { | |
456 if ((l - i) * (xorshift(&prng) / (double)UINT32_MAX) < k… | |
457 clusters[n++].medoid = i; | |
458 if (n == k) | |
459 break; | |
460 } | |
461 | |
462 cache = calloc(l, sizeof(*cache)); | |
463 if (!cache) | |
464 goto cleanup; | |
465 | |
466 dS = calloc(k, sizeof(*dS)); | |
467 if (!dS) | |
468 goto cleanup; | |
469 | |
470 dS2 = calloc(k, sizeof(*dS2)); | |
471 if (!dS2) | |
472 goto cleanup; | |
473 | |
474 while (k > 3) { | |
475 for (i = 0; i < l; i++) { | |
476 cache[i].d1 = cache[i].d2 = cache[i].d3 = INFINITY; | |
477 for (j = 0; j < k; j++) { | |
478 d = distances[distanceindex(i, clusters[j].medoi… | |
479 if (d < cache[i].d1) { | |
480 cache[i].d3 = cache[i].d2; | |
481 cache[i].d2 = cache[i].d1; | |
482 cache[i].d1 = d; | |
483 cache[i].n3 = cache[i].n2; | |
484 cache[i].n2 = cache[i].n1; | |
485 cache[i].n1 = j; | |
486 } else if (d < cache[i].d2) { | |
487 cache[i].d3 = cache[i].d2; | |
488 cache[i].d2 = d; | |
489 cache[i].n3 = cache[i].n2; | |
490 cache[i].n2 = j; | |
491 } else if (d < cache[i].d3) { | |
492 cache[i].d3 = d; | |
493 cache[i].n3 = j; | |
494 } | |
495 } | |
496 } | |
497 | |
498 for (i = 0; i < k; i++) { | |
499 dS[i] = 0; | |
500 for (j = 0; j < l; j++) { | |
501 if (cache[j].n1 != i) | |
502 continue; | |
503 dS[i] += cache[j].d1 / cache[j].d2 - cache[j].d2… | |
504 } | |
505 for (j = 0; j < l; j++) { | |
506 if (cache[j].n2 != i) | |
507 continue; | |
508 dS[i] += cache[j].d1 / cache[j].d2 - cache[j].d1… | |
509 } | |
510 } | |
511 | |
512 lx = -1; | |
513 for (iter = 0; iter < 100; iter++) { | |
514 cdS = 0; | |
515 for (i = 0; i < l; i++) { | |
516 if (i == lx) | |
517 goto fastermsc_finished; | |
518 | |
519 for (j = 0; j < k; j++) { | |
520 if (clusters[j].medoid == i) | |
521 goto fastmsc_nexti; | |
522 } | |
523 | |
524 memcpy(dS2, dS, k * sizeof(*dS2)); | |
525 cdS2 = 0; | |
526 for (j = 0; j < l; j++) { | |
527 d = distances[distanceindex(i, j)]; | |
528 if (d < cache[j].d1) { | |
529 cdS2 += cache[j].d1 / cache[j].d… | |
530 dS2[cache[j].n1] += d / cache[j]… | |
531 dS2[cache[j].n2] += cache[j].d1 … | |
532 } else if (d < cache[j].d2) { | |
533 cdS2 += cache[j].d1 / cache[j].d… | |
534 dS2[cache[j].n1] += cache[j].d1 … | |
535 dS2[cache[j].n2] += cache[j].d1 … | |
536 } else if (d < cache[j].d3) { | |
537 dS2[cache[j].n1] += cache[j].d2 … | |
538 dS2[cache[j].n2] += cache[j].d1 … | |
539 } | |
540 } | |
541 d = -INFINITY; | |
542 for (j = 0; j < k; j++) { | |
543 if (dS2[j] > d) { | |
544 d = dS2[j]; | |
545 m = j; | |
546 } | |
547 } | |
548 dS2[m] += cdS2; | |
549 if (dS2[m] <= 0) | |
550 continue; | |
551 //printf("%lf\t%lf\n", dS2[m], cdS2); | |
552 printf("%lu (%lu) <-> %lu\n", clusters[m].medoid, (size_t)m, i); | |
553 lx = i; | |
554 clusters[m].medoid = i; | |
555 for (j = 0; j < l; j++) { | |
556 if (cache[j].n1 != m && cache[j].n2 != m… | |
557 continue; | |
558 cache[j].d1 = cache[j].d2 = cache[j].d3 … | |
559 for (n = 0; n < k; n++) { | |
560 d = distances[distanceindex(j, c… | |
561 if (d < cache[j].d1) { | |
562 cache[j].d3 = cache[j].d… | |
563 cache[j].d2 = cache[j].d… | |
564 cache[j].d1 = d; | |
565 cache[j].n3 = cache[j].n… | |
566 cache[j].n2 = cache[j].n… | |
567 cache[j].n1 = n; | |
568 } else if (d < cache[j].d2) { | |
569 cache[j].d3 = cache[j].d… | |
570 cache[j].d2 = d; | |
571 cache[j].n3 = cache[j].n… | |
572 cache[j].n2 = n; | |
573 } else if (d < cache[j].d3) { | |
574 cache[j].d3 = d; | |
575 cache[j].n3 = n; | |
576 } | |
577 } | |
578 } | |
579 for (j = 0; j < k; j++) { | |
580 dS[j] = 0; | |
581 for (n = 0; n < l; n++) { | |
582 if (cache[n].n1 != j) | |
583 continue; | |
584 dS[j] += cache[n].d1 / cache[n].… | |
585 } | |
586 for (n = 0; n < l; n++) { | |
587 if (cache[n].n2 != j) | |
588 continue; | |
589 dS[j] += cache[n].d1 / cache[n].… | |
590 } | |
591 } | |
592 printf("lx = %lu\n", i); | |
593 fastmsc_nexti:; | |
594 } | |
595 if (lx == -1) | |
596 break; | |
597 } | |
598 fastermsc_finished:; | |
599 d = INFINITY; | |
600 for (j = 0; j < k; j++) { | |
601 if (dS2[j] < d) { | |
602 d = dS2[j]; | |
603 m = j; | |
604 } | |
605 } | |
606 if (m < k - 1) | |
607 memmove(&clusters[m], &clusters[m + 1], k - m - 1); | |
608 k--; | |
609 printf("k = %lu\n", k); | |
610 } | |
611 | |
612 for (i = 0; i < k; i++) | |
613 clusters[i].n = 0; | |
614 | |
615 for (i = 0; i < l; i++) { | |
616 d = INFINITY; | |
617 for (j = 0; j < k; j++) { | |
618 if (distances[distanceindex(clusters[j].medoid, … | |
619 assoc[i] = j; | |
620 d = distances[distanceindex(clusters[j].… | |
621 } | |
622 } | |
623 clusters[assoc[i]].n++; | |
624 } | |
625 | |
626 dsum = 0; | |
627 for (i = 0; i < l; i++) { | |
628 d = INFINITY; | |
629 d2 = INFINITY; | |
630 for (j = 0; j < k; j++) { | |
631 if (distances[distanceindex(clusters[j].medoid, … | |
632 d2 = d; | |
633 d = distances[distanceindex(clusters[j].… | |
634 } else if (distances[distanceindex(clusters[j].m… | |
635 d2 = distances[distanceindex(clusters[j]… | |
636 } | |
637 } | |
638 if (clusters[assoc[i]].medoid != i) | |
639 dsum += 1 - d / (d2 + 0.000000000001); | |
640 printf("%lu\t%lu\t%lf\t%lf\t%lf\t%lu\t%s\n", i, assoc[i]… | |
641 } | |
642 printf("Silhouette = %lf\n", dsum / (l - k)); | |
643 | |
644 result = k; | |
645 cleanup: | |
646 free(clusters); | |
647 return result; | |
648 } | |
649 | |
650 int | |
651 fastermsc(struct gopherentry *g, size_t l, size_t k, double *distances, … | |
652 { | |
653 size_t i, j, n, ck; | |
654 ssize_t m1, m, m2; | |
655 size_t ti, th, huh; | |
656 double dsum, d, d2, gnarf, tdsum; | |
657 struct { | |
658 size_t medoid; | |
659 size_t n; | |
660 double dsum; | |
661 } *clusters; | |
662 struct { | |
663 size_t n1, n2, n3; | |
664 double d1, d2, d3; | |
665 } *cache; | |
666 double *dS, *dS2; | |
667 double cdS, cdS2; | |
668 size_t cm, cx; | |
669 ssize_t lx; | |
670 int flag, result; | |
671 uint32_t r; | |
672 double *C; | |
673 | |
674 if (!l) | |
675 return 0; | |
676 | |
677 if (l < k) | |
678 k = l; | |
679 | |
680 clusters = calloc(k, sizeof(*clusters)); | |
681 if (!clusters) | |
682 return -1; | |
683 | |
684 result = -1; | |
685 | |
686 /* | |
687 Seed the medoids randomly | |
688 */ | |
689 for (i = n = 0; i < l; i++) { | |
690 if ((l - i) * (xorshift(&prng) / (double)UINT32_MAX) < k… | |
691 clusters[n++].medoid = i; | |
692 if (n == k) | |
693 break; | |
694 } | |
695 | |
696 cache = calloc(l, sizeof(*cache)); | |
697 if (!cache) | |
698 goto cleanup; | |
699 | |
700 dS = calloc(k, sizeof(*dS)); | |
701 if (!dS) | |
702 goto cleanup; | |
703 | |
704 dS2 = calloc(k, sizeof(*dS2)); | |
705 if (!dS2) | |
706 goto cleanup; | |
707 | |
708 for (i = 0; i < l; i++) { | |
709 cache[i].d1 = cache[i].d2 = cache[i].d3 = INFINITY; | |
710 for (j = 0; j < k; j++) { | |
711 d = distances[distanceindex(i, clusters[j].medoi… | |
712 if (d < cache[i].d1) { | |
713 cache[i].d3 = cache[i].d2; | |
714 cache[i].d2 = cache[i].d1; | |
715 cache[i].d1 = d; | |
716 cache[i].n3 = cache[i].n2; | |
717 cache[i].n2 = cache[i].n1; | |
718 cache[i].n1 = j; | |
719 } else if (d < cache[i].d2) { | |
720 cache[i].d3 = cache[i].d2; | |
721 cache[i].d2 = d; | |
722 cache[i].n3 = cache[i].n2; | |
723 cache[i].n2 = j; | |
724 } else if (d < cache[i].d3) { | |
725 cache[i].d3 = d; | |
726 cache[i].n3 = j; | |
727 } | |
728 } | |
729 } | |
730 | |
731 for (i = 0; i < k; i++) { | |
732 dS[i] = 0; | |
733 for (j = 0; j < l; j++) { | |
734 if (cache[j].n1 != i) | |
735 continue; | |
736 dS[i] += cache[j].d1 / cache[j].d2 - cache[j].d2… | |
737 } | |
738 for (j = 0; j < l; j++) { | |
739 if (cache[j].n2 != i) | |
740 continue; | |
741 dS[i] += cache[j].d1 / cache[j].d2 - cache[j].d1… | |
742 } | |
743 } | |
744 | |
745 lx = -1; | |
746 for (;;) { | |
747 cdS = 0; | |
748 for (i = 0; i < l; i++) { | |
749 if (i == lx) | |
750 goto fastermsc_finished; | |
751 | |
752 for (j = 0; j < k; j++) { | |
753 if (clusters[j].medoid == i) | |
754 goto fastmsc_nexti; | |
755 } | |
756 | |
757 memcpy(dS2, dS, k * sizeof(*dS2)); | |
758 cdS2 = 0; | |
759 for (j = 0; j < l; j++) { | |
760 d = distances[distanceindex(i, j)]; | |
761 if (d < cache[j].d1) { | |
762 cdS2 += cache[j].d1 / cache[j].d… | |
763 dS2[cache[j].n1] += d / cache[j]… | |
764 dS2[cache[j].n2] += cache[j].d1 … | |
765 } else if (d < cache[j].d2) { | |
766 cdS2 += cache[j].d1 / cache[j].d… | |
767 dS2[cache[j].n1] += cache[j].d1 … | |
768 dS2[cache[j].n2] += cache[j].d1 … | |
769 } else if (d < cache[j].d3) { | |
770 dS2[cache[j].n1] += cache[j].d2 … | |
771 dS2[cache[j].n2] += cache[j].d1 … | |
772 } | |
773 } | |
774 d = -INFINITY; | |
775 for (j = 0; j < k; j++) { | |
776 if (dS2[j] > d) { | |
777 d = dS2[j]; | |
778 m = j; | |
779 } | |
780 } | |
781 dS2[m] += cdS2; | |
782 if (dS2[m] <= 0) | |
783 continue; | |
784 //printf("%lf\t%lf\n", dS2[m], cdS2); | |
785 printf("%lu (%lu) <-> %lu\n", clusters[m].medoid, (size_t)m, i); | |
786 lx = i; | |
787 clusters[m].medoid = i; | |
788 for (j = 0; j < l; j++) { | |
789 if (cache[j].n1 != m && cache[j].n2 != m… | |
790 continue; | |
791 cache[j].d1 = cache[j].d2 = cache[j].d3 … | |
792 for (n = 0; n < k; n++) { | |
793 d = distances[distanceindex(j, c… | |
794 if (d < cache[j].d1) { | |
795 cache[j].d3 = cache[j].d… | |
796 cache[j].d2 = cache[j].d… | |
797 cache[j].d1 = d; | |
798 cache[j].n3 = cache[j].n… | |
799 cache[j].n2 = cache[j].n… | |
800 cache[j].n1 = n; | |
801 } else if (d < cache[j].d2) { | |
802 cache[j].d3 = cache[j].d… | |
803 cache[j].d2 = d; | |
804 cache[j].n3 = cache[j].n… | |
805 cache[j].n2 = n; | |
806 } else if (d < cache[j].d3) { | |
807 cache[j].d3 = d; | |
808 cache[j].n3 = n; | |
809 } | |
810 } | |
811 } | |
812 for (j = 0; j < k; j++) { | |
813 dS[j] = 0; | |
814 for (n = 0; n < l; n++) { | |
815 if (cache[n].n1 != j) | |
816 continue; | |
817 dS[j] += cache[n].d1 / cache[n].… | |
818 } | |
819 for (n = 0; n < l; n++) { | |
820 if (cache[n].n2 != j) | |
821 continue; | |
822 dS[j] += cache[n].d1 / cache[n].… | |
823 } | |
824 } | |
825 printf("lx = %lu\n", i); | |
826 fastmsc_nexti:; | |
827 } | |
828 if (lx == -1) | |
829 break; | |
830 } | |
831 fastermsc_finished:; | |
832 | |
833 for (i = 0; i < k; i++) | |
834 clusters[i].n = 0; | |
835 | |
836 for (i = 0; i < l; i++) { | |
837 d = INFINITY; | |
838 for (j = 0; j < k; j++) { | |
839 if (distances[distanceindex(clusters[j].medoid, … | |
840 assoc[i] = j; | |
841 d = distances[distanceindex(clusters[j].… | |
842 } | |
843 } | |
844 clusters[assoc[i]].n++; | |
845 } | |
846 | |
847 dsum = 0; | |
848 for (i = 0; i < l; i++) { | |
849 d = INFINITY; | |
850 d2 = INFINITY; | |
851 for (j = 0; j < k; j++) { | |
852 if (distances[distanceindex(clusters[j].medoid, … | |
853 d2 = d; | |
854 d = distances[distanceindex(clusters[j].… | |
855 } else if (distances[distanceindex(clusters[j].m… | |
856 d2 = distances[distanceindex(clusters[j]… | |
857 } | |
858 } | |
859 if (clusters[assoc[i]].medoid != i) | |
860 dsum += 1 - d / (d2 + 0.000000000001); | |
861 printf("%lu\t%lu\t%lf\t%lf\t%lf\t%lu\t%s\n", i, assoc[i]… | |
862 } | |
863 printf("Silhouette = %lf\n", dsum / (l - k)); | |
864 | |
865 result = k; | |
866 cleanup: | |
867 free(clusters); | |
868 return result; | |
869 } | |
870 | |
871 int | |
872 fastmsc(struct gopherentry *g, size_t l, size_t k, double *distances, si… | |
873 { | |
874 size_t i, j, n, ck; | |
875 ssize_t m1, m, m2; | |
876 size_t ti, th; | |
877 double dsum, d, d2, gnarf, tdsum; | |
878 struct { | |
879 size_t medoid; | |
880 size_t n; | |
881 double dsum; | |
882 } *clusters; | |
883 struct { | |
884 size_t n1, n2; | |
885 double d1, d2, d3; | |
886 } *cache; | |
887 double *dS, *dS2; | |
888 double cdS, cdS2; | |
889 size_t cm, cx; | |
890 int flag, result; | |
891 uint32_t r; | |
892 double *C; | |
893 | |
894 if (!l) | |
895 return 0; | |
896 | |
897 if (l < k) | |
898 k = l; | |
899 | |
900 clusters = calloc(k, sizeof(*clusters)); | |
901 if (!clusters) | |
902 return -1; | |
903 | |
904 result = -1; | |
905 | |
906 /* | |
907 seed the medoids using PAM BUILD | |
908 */ | |
909 d = INFINITY; | |
910 m = -1; | |
911 for (i = 0; i < l; i++) { | |
912 dsum = 0; | |
913 for (j = 0; j < l; j++) | |
914 dsum += distances[distanceindex(i, j)]; | |
915 if (dsum < d) { | |
916 m = i; | |
917 d = dsum; | |
918 } | |
919 } | |
920 if (m == -1) | |
921 goto cleanup; | |
922 ck = 0; | |
923 clusters[ck].medoid = m; | |
924 ck++; | |
925 | |
926 C = xmalloc(l * l * sizeof(*C)); | |
927 | |
928 for (; ck < k; ck++) { | |
929 memset(C, 0, l * l * sizeof(*C)); | |
930 for (i = 0; i < l; i++) { | |
931 for (j = 0; j < ck; j++) { | |
932 if (clusters[j].medoid == i) | |
933 goto build_nexti; | |
934 } | |
935 for (j = 0; j < l; j++) { | |
936 if (i == j) | |
937 continue; | |
938 for (n = 0; n < ck; n++) { | |
939 if (clusters[n].medoid == j) | |
940 goto build_nextj; | |
941 } | |
942 d = INFINITY; | |
943 for (n = 0; n < ck; n++) { | |
944 if (distances[distanceindex(j, c… | |
945 d = distances[distancein… | |
946 } | |
947 C[j * l + i] = d - distances[distanceind… | |
948 if (C[j * l + i] < 0) | |
949 C[j * l + i] = 0; | |
950 build_nextj:; | |
951 } | |
952 build_nexti:; | |
953 } | |
954 d = -1; | |
955 m = -1; | |
956 for (i = 0; i < l; i++) { | |
957 for (j = 0; j < ck; j++) { | |
958 if (clusters[j].medoid == i) | |
959 goto build_nexti2; | |
960 } | |
961 dsum = 0; | |
962 for (j = 0; j < l; j++) | |
963 dsum += C[j * l + i]; | |
964 if (dsum > d) { | |
965 d = dsum; | |
966 m = i; | |
967 } | |
968 build_nexti2:; | |
969 } | |
970 clusters[ck].medoid = m; | |
971 } | |
972 free(C); | |
973 | |
974 /* | |
975 Seed the medoids randomly | |
976 for (i = n = 0; i < l; i++) { | |
977 if ((l - i) * (xorshift(&prng) / (double)UINT32_MAX) < k… | |
978 clusters[n++].medoid = i; | |
979 if (n == k) | |
980 break; | |
981 } | |
982 */ | |
983 | |
984 cache = calloc(l, sizeof(*cache)); | |
985 if (!cache) | |
986 goto cleanup; | |
987 | |
988 dS = calloc(k, sizeof(*dS)); | |
989 if (!dS) | |
990 goto cleanup; | |
991 | |
992 dS2 = calloc(k, sizeof(*dS2)); | |
993 if (!dS2) | |
994 goto cleanup; | |
995 | |
996 for (;;) { | |
997 for (i = 0; i < l; i++) { | |
998 cache[i].d1 = cache[i].d2 = cache[i].d3 = INFINI… | |
999 for (j = 0; j < k; j++) { | |
1000 d = distances[distanceindex(i, clusters[… | |
1001 if (d < cache[i].d1) { | |
1002 cache[i].d3 = cache[i].d2; | |
1003 cache[i].d2 = cache[i].d1; | |
1004 cache[i].d1 = d; | |
1005 cache[i].n2 = cache[i].n1; | |
1006 cache[i].n1 = j; | |
1007 } else if (d < cache[i].d2) { | |
1008 cache[i].d3 = cache[i].d2; | |
1009 cache[i].d2 = d; | |
1010 cache[i].n2 = j; | |
1011 } else if (d < cache[i].d3) { | |
1012 cache[i].d3 = d; | |
1013 } | |
1014 } | |
1015 } | |
1016 | |
1017 for (i = 0; i < k; i++) { | |
1018 dS[i] = 0; | |
1019 for (j = 0; j < l; j++) { | |
1020 if (cache[j].n1 != i) | |
1021 continue; | |
1022 dS[i] += cache[j].d1 / cache[j].d2 - cac… | |
1023 } | |
1024 for (j = 0; j < l; j++) { | |
1025 if (cache[j].n2 != i) | |
1026 continue; | |
1027 dS[i] += cache[j].d1 / cache[j].d2 - cac… | |
1028 } | |
1029 } | |
1030 | |
1031 cdS = 0; | |
1032 for (i = 0; i < l; i++) { | |
1033 for (j = 0; j < k; j++) { | |
1034 if (clusters[j].medoid == i) | |
1035 goto fastmsc_nexti; | |
1036 } | |
1037 memcpy(dS2, dS, k * sizeof(*dS2)); | |
1038 cdS2 = 0; | |
1039 for (j = 0; j < l; j++) { | |
1040 d = distances[distanceindex(i, j)]; | |
1041 if (d < cache[j].d1) { | |
1042 cdS2 += cache[j].d1 / cache[j].d… | |
1043 dS2[cache[j].n1] += d / cache[j]… | |
1044 dS2[cache[j].n2] += cache[j].d1 … | |
1045 } else if (d < cache[j].d2) { | |
1046 cdS2 += cache[j].d1 / cache[j].d… | |
1047 dS2[cache[j].n1] += cache[j].d1 … | |
1048 dS2[cache[j].n2] += cache[j].d1 … | |
1049 } else if (d < cache[j].d3) { | |
1050 dS2[cache[j].n1] += cache[j].d2 … | |
1051 dS2[cache[j].n2] += cache[j].d1 … | |
1052 } | |
1053 } | |
1054 d = -INFINITY; | |
1055 d2 = INFINITY; | |
1056 for (j = 0; j < k; j++) { | |
1057 if (dS2[j] > d) { | |
1058 d = dS2[j]; | |
1059 m = j; | |
1060 } | |
1061 if (dS2[j] < d2) { | |
1062 d2 = dS2[j]; | |
1063 m2 = j; | |
1064 } | |
1065 } | |
1066 printf("%lf (%ld)\t%lf (%ld)\n", d, m, d2, m2); | |
1067 dS2[m] += cdS2; | |
1068 if (dS2[m] > cdS) { | |
1069 cdS = dS2[m]; | |
1070 cm = m; | |
1071 cx = i; | |
1072 } | |
1073 fastmsc_nexti:; | |
1074 } | |
1075 if (cdS <= 0) | |
1076 break; | |
1077 clusters[cm].medoid = cx; | |
1078 } | |
1079 | |
1080 for (i = 0; i < k; i++) | |
1081 clusters[i].n = 0; | |
1082 | |
1083 for (i = 0; i < l; i++) { | |
1084 d = INFINITY; | |
1085 for (j = 0; j < k; j++) { | |
1086 if (distances[distanceindex(clusters[j].medoid, … | |
1087 assoc[i] = j; | |
1088 d = distances[distanceindex(clusters[j].… | |
1089 } | |
1090 } | |
1091 clusters[assoc[i]].n++; | |
1092 } | |
1093 | |
1094 dsum = 0; | |
1095 for (i = 0; i < l; i++) { | |
1096 d = INFINITY; | |
1097 d2 = INFINITY; | |
1098 for (j = 0; j < k; j++) { | |
1099 if (distances[distanceindex(clusters[j].medoid, … | |
1100 d2 = d; | |
1101 d = distances[distanceindex(clusters[j].… | |
1102 } else if (distances[distanceindex(clusters[j].m… | |
1103 d2 = distances[distanceindex(clusters[j]… | |
1104 } | |
1105 } | |
1106 if (clusters[assoc[i]].medoid != i) | |
1107 dsum += 1 - d / (d2 + 0.000000000001); | |
1108 printf("%lu\t%lu\t%lf\t%lf\t%lf\t%lu\t%s\n", i, assoc[i]… | |
1109 } | |
1110 printf("Silhouette = %lf\n", dsum / (l - k)); | |
1111 | |
1112 result = k; | |
1113 cleanup: | |
1114 free(clusters); | |
1115 return result; | |
1116 } | |
1117 | |
1118 /* | |
1119 Seeding of medoids based on the PAM BUILD description in https:/… | |
1120 I was too stupid to understand other descriptions. | |
1121 */ | |
1122 int | |
1123 kmedoids(struct gopherentry *g, size_t l, size_t k, double *distances, s… | |
1124 { | |
1125 size_t i, j, n, ck; | |
1126 ssize_t m1, m; | |
1127 size_t ti, th; | |
1128 double dsum, d, d2, gnarf, tdsum; | |
1129 struct { | |
1130 size_t medoid; | |
1131 size_t n; | |
1132 double dsum; | |
1133 } *clusters; | |
1134 int flag, result; | |
1135 uint32_t r; | |
1136 double *C; | |
1137 | |
1138 if (!l) | |
1139 return 0; | |
1140 | |
1141 if (l < k) | |
1142 k = l; | |
1143 | |
1144 clusters = calloc(k, sizeof(*clusters)); | |
1145 if (!clusters) | |
1146 return -1; | |
1147 | |
1148 result = -1; | |
1149 | |
1150 /* seed the medoids using PAM BUILD */ | |
1151 d = INFINITY; | |
1152 m = -1; | |
1153 for (i = 0; i < l; i++) { | |
1154 dsum = 0; | |
1155 for (j = 0; j < l; j++) | |
1156 dsum += distances[distanceindex(i, j)]; | |
1157 if (dsum < d) { | |
1158 m = i; | |
1159 d = dsum; | |
1160 } | |
1161 } | |
1162 if (m == -1) | |
1163 goto cleanup; | |
1164 ck = 0; | |
1165 clusters[ck].medoid = m; | |
1166 ck++; | |
1167 | |
1168 C = xmalloc(l * l * sizeof(*C)); | |
1169 | |
1170 for (; ck < k; ck++) { | |
1171 memset(C, 0, l * l * sizeof(*C)); | |
1172 for (i = 0; i < l; i++) { | |
1173 for (j = 0; j < ck; j++) { | |
1174 if (clusters[j].medoid == i) | |
1175 goto build_nexti; | |
1176 } | |
1177 for (j = 0; j < l; j++) { | |
1178 if (i == j) | |
1179 continue; | |
1180 for (n = 0; n < ck; n++) { | |
1181 if (clusters[n].medoid == j) | |
1182 goto build_nextj; | |
1183 } | |
1184 d = INFINITY; | |
1185 for (n = 0; n < ck; n++) { | |
1186 if (distances[distanceindex(j, c… | |
1187 d = distances[distancein… | |
1188 } | |
1189 C[j * l + i] = d - distances[distanceind… | |
1190 if (C[j * l + i] < 0) | |
1191 C[j * l + i] = 0; | |
1192 build_nextj:; | |
1193 } | |
1194 build_nexti:; | |
1195 } | |
1196 d = -1; | |
1197 m = -1; | |
1198 for (i = 0; i < l; i++) { | |
1199 for (j = 0; j < ck; j++) { | |
1200 if (clusters[j].medoid == i) | |
1201 goto build_nexti2; | |
1202 } | |
1203 dsum = 0; | |
1204 for (j = 0; j < l; j++) | |
1205 dsum += C[j * l + i]; | |
1206 if (dsum > d) { | |
1207 d = dsum; | |
1208 m = i; | |
1209 } | |
1210 build_nexti2:; | |
1211 } | |
1212 clusters[ck].medoid = m; | |
1213 } | |
1214 free(C); | |
1215 | |
1216 /* | |
1217 Seed the medoids randomly | |
1218 for (i = n = 0; i < l; i++) { | |
1219 if ((l - i) * (xorshift(&prng) / (double)UINT32_MAX) < k… | |
1220 clusters[n++].medoid = i; | |
1221 if (n == k) | |
1222 break; | |
1223 } | |
1224 */ | |
1225 | |
1226 for (;;) { | |
1227 tdsum = INFINITY; | |
1228 for (i = 0; i < k; i++) { | |
1229 for (j = 0; j < l; j++) { | |
1230 for (n = 0; n < k; n++) { | |
1231 if (j == clusters[n].medoid) | |
1232 goto swap_nextj; | |
1233 } | |
1234 dsum = 0; | |
1235 for (n = 0; n < l; n++) { | |
1236 if (n == j) | |
1237 continue; | |
1238 for (m = 0; m < k; m++) { | |
1239 if (clusters[m].medoid =… | |
1240 goto swap_nextn; | |
1241 } | |
1242 d = INFINITY; | |
1243 d2 = INFINITY; | |
1244 for (m = 0; m < k; m++) { | |
1245 if (distances[distancein… | |
1246 d2 = d; | |
1247 d = distances[di… | |
1248 } else if (distances[dis… | |
1249 d2 = distances[d… | |
1250 } | |
1251 } | |
1252 /* | |
1253 printf("%lf\t%lf\t%lf\t%lf\n", distances[distanceindex(clusters[i].medoi… | |
1254 */ | |
1255 if (distances[distanceindex(clus… | |
1256 if (distances[distancein… | |
1257 gnarf = 0; | |
1258 else | |
1259 gnarf = distance… | |
1260 } else if (distances[distanceind… | |
1261 if (distances[distancein… | |
1262 gnarf = distance… | |
1263 else | |
1264 gnarf = d2 - d; | |
1265 } else { | |
1266 continue; | |
1267 } | |
1268 dsum += gnarf; | |
1269 swap_nextn:; | |
1270 } | |
1271 if (dsum < tdsum) { | |
1272 ti = i; | |
1273 th = j; | |
1274 tdsum = dsum; | |
1275 /* | |
1276 printf("%lu\t%lu\t%lf\n", clusters[ti].medoid, th, tdsum); | |
1277 */ | |
1278 } | |
1279 swap_nextj:; | |
1280 } | |
1281 } | |
1282 if (tdsum >= 0) | |
1283 break; | |
1284 clusters[ti].medoid = th; | |
1285 } | |
1286 | |
1287 for (i = 0; i < k; i++) | |
1288 clusters[i].n = 0; | |
1289 | |
1290 for (i = 0; i < l; i++) { | |
1291 d = INFINITY; | |
1292 for (j = 0; j < k; j++) { | |
1293 if (distances[distanceindex(clusters[j].medoid, … | |
1294 assoc[i] = j; | |
1295 d = distances[distanceindex(clusters[j].… | |
1296 } | |
1297 } | |
1298 clusters[assoc[i]].n++; | |
1299 } | |
1300 | |
1301 dsum = 0; | |
1302 for (i = 0; i < l; i++) { | |
1303 d = INFINITY; | |
1304 d2 = INFINITY; | |
1305 for (j = 0; j < k; j++) { | |
1306 if (distances[distanceindex(clusters[j].medoid, … | |
1307 d2 = d; | |
1308 d = distances[distanceindex(clusters[j].… | |
1309 } else if (distances[distanceindex(clusters[j].m… | |
1310 d2 = distances[distanceindex(clusters[j]… | |
1311 } | |
1312 } | |
1313 if (clusters[assoc[i]].medoid != i) | |
1314 dsum += 1 - d / (d2 + 0.000000000001); | |
1315 printf("%lu\t%lu\t%lf\t%lf\t%lf\t%lu\t%s\n", i, assoc[i]… | |
1316 if (clusters[assoc[i]].medoid == i) | |
1317 assoc[i] |= 128; | |
1318 } | |
1319 printf("Silhouette = %lf\n", dsum / (l - k)); | |
1320 | |
1321 /* | |
1322 while (1) { | |
1323 flag = 0; | |
1324 for (i = 0; i < l; i++) { | |
1325 d = INFINITY; | |
1326 m = assoc[i]; | |
1327 for (j = 0; j < k; j++) { | |
1328 if (distances[distanceindex(clusters[j].… | |
1329 d = distances[distanceindex(clus… | |
1330 assoc[i] = j; | |
1331 } | |
1332 } | |
1333 if (assoc[i] != m) | |
1334 flag = 1; | |
1335 } | |
1336 if (!flag) | |
1337 break; | |
1338 | |
1339 for (i = 0; i < k; i++) | |
1340 clusters[i].dsum = INFINITY; | |
1341 | |
1342 for (i = 0; i < l; i++) { | |
1343 dsum = 0; | |
1344 for (j = 0; j < l; j++) { | |
1345 if (assoc[i] != assoc[j]) | |
1346 continue; | |
1347 dsum += distanceindex(i, j); | |
1348 } | |
1349 if (dsum < clusters[assoc[i]].dsum) { | |
1350 clusters[assoc[i]].dsum = dsum; | |
1351 clusters[assoc[i]].medoid = i; | |
1352 } | |
1353 } | |
1354 } | |
1355 */ | |
1356 result = k; | |
1357 cleanup: | |
1358 free(clusters); | |
1359 return result; | |
1360 } | |
1361 | |
1362 struct room { | |
1363 struct room *p; | |
1364 void *d; | |
1365 size_t x, y; | |
1366 size_t w, h; | |
1367 }; | |
1368 | |
1369 int | |
1370 generaterooms_collides(size_t x1, size_t y1, size_t w1, size_t h1, | |
1371 size_t x2, size_t y2, size_t w2, size_t h2, | |
1372 size_t margin) | |
1373 { | |
1374 return !((y1 >= y2 + h2 + margin || y2 >= y1 + h1 + margin) || (… | |
1375 } | |
1376 | |
1377 int | |
1378 generaterooms_isfree(struct room *rs, size_t l, size_t x, size_t y, size… | |
1379 { | |
1380 size_t i; | |
1381 | |
1382 for (i = 0; i < l; i++) { | |
1383 if (generaterooms_collides(rs[i].x, rs[i].y, rs[i].w, rs… | |
1384 x, y, w, h, margin)) | |
1385 return 0; | |
1386 } | |
1387 return 1; | |
1388 } | |
1389 | |
1390 struct rect { | |
1391 struct rect *next, *next2; | |
1392 struct room *room; | |
1393 size_t x1, y1; | |
1394 size_t x2, y2; | |
1395 size_t d; | |
1396 }; | |
1397 | |
1398 struct rect * | |
1399 generaterooms_gnarf_randomneighbor(struct rect *x, struct rect *rs, uint… | |
1400 { | |
1401 struct rect *r, *result; | |
1402 size_t n; | |
1403 | |
1404 n = 0; | |
1405 result = NULL; | |
1406 for (r = rs; r; r = r->next) { | |
1407 if (r->y2 < x->y1 || r->y1 > x->y2 || r->x2 < x->x1 || r… | |
1408 continue; | |
1409 if ((r->y2 == x->y1 || r->y1 == x->y2) && (r->x2 == x->x… | |
1410 continue; | |
1411 n++; | |
1412 if (xorshift(prng) / (1. + UINT32_MAX) < 1. / n) | |
1413 result = r; | |
1414 } | |
1415 | |
1416 return result; | |
1417 } | |
1418 | |
1419 #define ROOM_HEIGHT_MIN 3 | |
1420 #define ROOM_WIDTH_MIN 5 | |
1421 #define ROOM_MARGIN_MIN 1 | |
1422 #define CELL_HEIGHT_MIN (ROOM_HEIGHT_MIN + ROOM_MARGIN_MIN + 3) | |
1423 #define CELL_WIDTH_MIN (ROOM_WIDTH_MIN + ROOM_MARGIN_MIN + 3) | |
1424 size_t | |
1425 generaterooms_gnarf(char *host, char *port, char *selector, struct room … | |
1426 { | |
1427 struct rect *queuehead, *queuetail; | |
1428 struct rect *r, *t; | |
1429 struct rect *rects, *walk; | |
1430 size_t w, h, i, j, rl, n; | |
1431 uint32_t prng; | |
1432 int vertical; | |
1433 struct room *room; | |
1434 | |
1435 prng = fnv1a(4, host, port, selector, "seed"); | |
1436 | |
1437 r = xmalloc(sizeof(*r)); | |
1438 r->x1 = r->y1 = ROOM_MARGIN_MIN; | |
1439 r->x2 = MAPWIDTH; | |
1440 r->y2 = MAPHEIGHT; | |
1441 r->d = 0; | |
1442 | |
1443 queuetail = r; | |
1444 queuetail->next = NULL; | |
1445 queuehead = r; | |
1446 | |
1447 rects = NULL; | |
1448 rl = 0; | |
1449 | |
1450 while (queuehead) { | |
1451 r = queuehead; | |
1452 if (queuetail == queuehead) | |
1453 queuetail = NULL; | |
1454 queuehead = queuehead->next; | |
1455 | |
1456 /* | |
1457 if (r->d >= 8) { | |
1458 r->next = rects; | |
1459 rects = r; | |
1460 rl++; | |
1461 continue; | |
1462 } | |
1463 */ | |
1464 | |
1465 if (r->x2 - r->x1 >= CELL_WIDTH_MIN * 2 && r->y2 - r->y1… | |
1466 vertical = xorshift(&prng) & 1; | |
1467 } else if (r->x2 - r->x1 >= CELL_WIDTH_MIN * 2) { | |
1468 vertical = 0; | |
1469 } else if (r->y2 - r->y1 >= CELL_HEIGHT_MIN * 2) { | |
1470 vertical = 1; | |
1471 } else { | |
1472 r->next = rects; | |
1473 rects = r; | |
1474 rl++; | |
1475 continue; | |
1476 } | |
1477 | |
1478 if (vertical) { | |
1479 w = r->x2 - r->x1; | |
1480 h = CELL_HEIGHT_MIN + xorshift(&prng) % (1 + r->… | |
1481 } else { | |
1482 w = CELL_WIDTH_MIN + xorshift(&prng) % (1 + r->x… | |
1483 h = r->y2 - r->y1; | |
1484 } | |
1485 | |
1486 t = xmalloc(sizeof(*t)); | |
1487 t->x1 = r->x1; | |
1488 t->y1 = r->y1; | |
1489 t->x2 = r->x1 + w; | |
1490 t->y2 = r->y1 + h; | |
1491 t->d = r->d + 1; | |
1492 t->next = NULL; | |
1493 t->room = NULL; | |
1494 | |
1495 if (!queuetail) { | |
1496 queuehead = t; | |
1497 queuetail = t; | |
1498 } else { | |
1499 queuetail->next = t; | |
1500 queuetail = t; | |
1501 } | |
1502 | |
1503 t = xmalloc(sizeof(*t)); | |
1504 if (vertical) { | |
1505 t->x1 = r->x1; | |
1506 t->y1 = r->y1 + h; | |
1507 } else { | |
1508 t->x1 = r->x1 + w; | |
1509 t->y1 = r->y1; | |
1510 } | |
1511 t->x2 = r->x2; | |
1512 t->y2 = r->y2; | |
1513 t->d = r->d + 1; | |
1514 t->next = NULL; | |
1515 t->room = NULL; | |
1516 | |
1517 queuetail->next = t; | |
1518 queuetail = t; | |
1519 | |
1520 free(r); | |
1521 } | |
1522 | |
1523 if (l > rl) | |
1524 l = rl; | |
1525 | |
1526 for (r = rects; r; r = r->next) { | |
1527 if (MAPHEIGHT / 2 >= r->y1 && MAPHEIGHT / 2 < r->y2 && | |
1528 MAPWIDTH / 2 >= r->x1 && MAPWIDTH / 2 < r->x2) | |
1529 break; | |
1530 } | |
1531 | |
1532 i = 0; | |
1533 rs[i].w = ROOM_WIDTH_MIN + xorshift(&prng) % (1 + r->x2 - r->x1 … | |
1534 rs[i].h = ROOM_HEIGHT_MIN + xorshift(&prng) % (1 + r->y2 - r->y1… | |
1535 rs[i].x = r->x1 + xorshift(&prng) % (1 + r->x2 - r->x1 - ROOM_MA… | |
1536 rs[i].y = r->y1 + xorshift(&prng) % (1 + r->y2 - r->y1 - ROOM_MA… | |
1537 rs[i].p = NULL; | |
1538 r->room = &rs[i]; | |
1539 | |
1540 walk = r; | |
1541 walk->next2 = NULL; | |
1542 | |
1543 i++; | |
1544 for (; i < l;) { | |
1545 t = generaterooms_gnarf_randomneighbor(r, rects, &prng); | |
1546 if (!t || t->room) { | |
1547 n = 0; | |
1548 for (t = walk; t; t = t->next2) { | |
1549 n++; | |
1550 if (xorshift(&prng) / (1. + UINT32_MAX) … | |
1551 r = t; | |
1552 | |
1553 } | |
1554 continue; | |
1555 } | |
1556 rs[i].w = ROOM_WIDTH_MIN + xorshift(&prng) % (1 + t->x2 … | |
1557 rs[i].h = ROOM_HEIGHT_MIN + xorshift(&prng) % (1 + t->y2… | |
1558 rs[i].x = t->x1 + xorshift(&prng) % (1 + t->x2 - t->x1 -… | |
1559 rs[i].y = t->y1 + xorshift(&prng) % (1 + t->y2 - t->y1 -… | |
1560 rs[i].p = r->room; | |
1561 t->room = &rs[i]; | |
1562 i++; | |
1563 r = t; | |
1564 r->next2 = walk; | |
1565 walk = r; | |
1566 } | |
1567 | |
1568 /* | |
1569 for (r = rects, i = 0; i < l; i++, r = r->next) { | |
1570 rs[i].w = 3 + xorshift(&prng) % (1 + r->x2 - r->x1 - 1 -… | |
1571 rs[i].h = 2 + xorshift(&prng) % (1 + r->y2 - r->y1 - 1 -… | |
1572 rs[i].x = r->x1 + xorshift(&prng) % (1 + r->x2 - r->x1 -… | |
1573 rs[i].y = r->y1 + xorshift(&prng) % (1 + r->y2 - r->y1 -… | |
1574 rs[i].p = NULL; | |
1575 } | |
1576 */ | |
1577 | |
1578 return l; | |
1579 } | |
1580 | |
1581 #define ROOMS_MARGIN_MIN 1 | |
1582 #define ROOMS_MARGIN_MAX 3 | |
1583 #define MAP_MARGIN 1 | |
1584 size_t | |
1585 generaterooms_stupid(char *host, char *port, char *selector, struct room… | |
1586 { | |
1587 size_t i, j, ri, m, n; | |
1588 ssize_t y, x; | |
1589 ssize_t w, h; | |
1590 char buffer[3]; | |
1591 struct room *r; | |
1592 uint32_t prng; | |
1593 | |
1594 rs[0].h = 4 + fnv1a(4, host, port, selector, "h") % 5; | |
1595 rs[0].w = 4 + fnv1a(4, host, port, selector, "w") % 5; | |
1596 rs[0].y = MAPHEIGHT / 2 - rs[0].h / 2; | |
1597 rs[0].x = MAPWIDTH / 2 - rs[0].w / 2; | |
1598 for (i = 1; i < l; i++) { | |
1599 snprintf(buffer, sizeof(buffer), "%u", i); | |
1600 prng = fnv1a(5, host, port, selector, buffer, "seed"); | |
1601 n = 0; | |
1602 do { | |
1603 do { | |
1604 switch (xorshift(&prng) % 3) { | |
1605 case 0: | |
1606 h = 3 + xorshift(&prng) % 3; | |
1607 w = 3 + xorshift(&prng) % 2; | |
1608 break; | |
1609 case 1: | |
1610 w = 3 + xorshift(&prng) % 3; | |
1611 h = 4 + xorshift(&prng) % 2; | |
1612 break; | |
1613 case 2: | |
1614 h = w = 4 + xorshift(&prng) % 5; | |
1615 break; | |
1616 } | |
1617 m = ROOMS_MARGIN_MIN + xorshift(&prng) %… | |
1618 j = xorshift(&prng) % i; | |
1619 switch (xorshift(&prng) % 4) { | |
1620 case 0: | |
1621 x = rs[j].x; | |
1622 if (w < rs[j].w) | |
1623 x += xorshift(&prng) % (… | |
1624 else | |
1625 x -= xorshift(&prng) % (… | |
1626 y = rs[j].y - h - m; | |
1627 break; | |
1628 case 1: | |
1629 x = rs[j].x + rs[j].w + m; | |
1630 y = rs[j].y; | |
1631 if (h < rs[j].h) | |
1632 y += xorshift(&prng) % (… | |
1633 else | |
1634 y -= xorshift(&prng) % (… | |
1635 break; | |
1636 case 2: | |
1637 x = rs[j].x; | |
1638 if (w < rs[j].w) | |
1639 x += xorshift(&prng) % (… | |
1640 else | |
1641 x -= xorshift(&prng) % (… | |
1642 y = rs[j].y + rs[j].h + m; | |
1643 break; | |
1644 case 3: | |
1645 x = rs[j].x - w - m; | |
1646 y = rs[j].y; | |
1647 if (h < rs[j].h) | |
1648 y += xorshift(&prng) % (… | |
1649 else | |
1650 y -= xorshift(&prng) % (… | |
1651 break; | |
1652 } | |
1653 } while (x < MAP_MARGIN || x + w + MAP_MARGIN > … | |
1654 n++; | |
1655 } while (n <= 100 && !generaterooms_isfree(rs, i, x, y, … | |
1656 if (n > 100) | |
1657 break; | |
1658 rs[i].h = h; | |
1659 rs[i].w = w; | |
1660 rs[i].x = x; | |
1661 rs[i].y = y; | |
1662 rs[i].p = &rs[j]; | |
1663 } | |
1664 return i; | |
1665 } | |
1666 | |
1667 #define ROOMS_GRID_ROWS 5 | |
1668 #define ROOMS_GRID_COLS 10 | |
1669 size_t | |
1670 generaterooms_grid(char *host, char *port, char *selector, struct room *… | |
1671 { | |
1672 size_t i, j, k, x, y; | |
1673 unsigned char cells[ROOMS_GRID_ROWS * ROOMS_GRID_COLS]; | |
1674 char buffer[3]; | |
1675 uint32_t prng; | |
1676 | |
1677 memset(cells, 0, sizeof(cells)); | |
1678 | |
1679 if (l > ROOMS_GRID_ROWS * ROOMS_GRID_COLS) | |
1680 l = ROOMS_GRID_ROWS * ROOMS_GRID_COLS; | |
1681 | |
1682 for (i = 0; i < l; i++) { | |
1683 snprintf(buffer, sizeof(buffer), "%u", i); | |
1684 prng = fnv1a(5, host, port, selector, buffer, "seed"); | |
1685 j = 0; | |
1686 do { | |
1687 k = xorshift(&prng) % (ROOMS_GRID_ROWS * ROOMS_G… | |
1688 j++; | |
1689 } while (j <= 100 && cells[k]); | |
1690 if (j > 100) | |
1691 break; | |
1692 y = k / ROOMS_GRID_COLS; | |
1693 x = k % ROOMS_GRID_COLS; | |
1694 cells[k] = 1; | |
1695 rs[i].w = 3 + xorshift(&prng) % (1 + 8 - 2 - 3); | |
1696 rs[i].h = 3 + xorshift(&prng) % (1 + 5 - 2 - 3); | |
1697 rs[i].x = x * 8 + 1 + xorshift(&prng) % (1 + 8 - 2 - rs[… | |
1698 rs[i].y = y * 5 + 1 + xorshift(&prng) % (1 + 5 - 2 - rs[… | |
1699 /* | |
1700 printf("%u\t%u\t%u\t%u\n", rs[i].w, rs[i].h, rs[i].x, rs[i].y); | |
1701 */ | |
1702 rs[i].p = NULL; | |
1703 } | |
1704 | |
1705 return i; | |
1706 } | |
1707 | |
1708 void | |
1709 generaterooms_grid2_(struct room *r, uint32_t *prng, size_t x, size_t y) | |
1710 { | |
1711 r->w = 3 + xorshift(prng) % (1 + 8 - 2 - 3); | |
1712 r->h = 3 + xorshift(prng) % (1 + 5 - 2 - 3); | |
1713 r->x = x * 8 + 1 + xorshift(prng) % (1 + 8 - 2 - r->w); | |
1714 r->y = y * 5 + 1 + xorshift(prng) % (1 + 5 - 2 - r->h); | |
1715 r->p = NULL; | |
1716 /* | |
1717 printf("%u\t%u\t%u\t%u\n", r->w, r->h, r->x, r->y); | |
1718 */ | |
1719 } | |
1720 | |
1721 size_t | |
1722 generaterooms_grid2(char *host, char *port, char *selector, struct room … | |
1723 { | |
1724 const struct { | |
1725 ssize_t y, x; | |
1726 } gnarf[8] = { | |
1727 { -1, 0 }, | |
1728 { 0, 1 }, | |
1729 { 1, 0 }, | |
1730 { 0, -1 }, | |
1731 { -1, 1 }, | |
1732 { 1, 1 }, | |
1733 { 1, -1 }, | |
1734 { -1, -1 } | |
1735 }; | |
1736 size_t i, j, k, m, n; | |
1737 ssize_t x, y; | |
1738 struct room *cells[ROOMS_GRID_ROWS][ROOMS_GRID_COLS]; | |
1739 char buffer[3]; | |
1740 uint32_t prng; | |
1741 struct room *r; | |
1742 | |
1743 memset(cells, 0, sizeof(cells)); | |
1744 | |
1745 if (l > ROOMS_GRID_ROWS * ROOMS_GRID_COLS) | |
1746 l = ROOMS_GRID_ROWS * ROOMS_GRID_COLS; | |
1747 | |
1748 prng = fnv1a(5, host, port, selector, "seed"); | |
1749 x = ROOMS_GRID_COLS / 2; | |
1750 y = ROOMS_GRID_ROWS / 2; | |
1751 | |
1752 r = &rs[0]; | |
1753 generaterooms_grid2_(r, &prng, x, y); | |
1754 cells[y][x] = r; | |
1755 | |
1756 for (i = 1; i < l; i++) { | |
1757 for (n = 0; n < 100; n++) { | |
1758 m = xorshift(&prng) % 4; | |
1759 x += gnarf[m].x; | |
1760 y += gnarf[m].y; | |
1761 if (x < 0 || x >= ROOMS_GRID_COLS || y < 0 || y … | |
1762 m = xorshift(&prng) % i; | |
1763 r = &rs[m]; | |
1764 x = r->x / 8; | |
1765 y = r->y / 5; | |
1766 } else { | |
1767 generaterooms_grid2_(&rs[i], &prng, x, y… | |
1768 rs[i].p = r; | |
1769 cells[y][x] = r = &rs[i]; | |
1770 break; | |
1771 } | |
1772 } | |
1773 if (n >= 100) | |
1774 break; | |
1775 } | |
1776 | |
1777 return i; | |
1778 } | |
1779 | |
1780 size_t | |
1781 distance(size_t x1, size_t y1, size_t x2, size_t y2) | |
1782 { | |
1783 size_t d; | |
1784 | |
1785 if (y1 < y2) | |
1786 d = y2 - y1; | |
1787 else | |
1788 d = y1 - y2; | |
1789 if (x1 < x2) | |
1790 d += x2 - x1; | |
1791 else | |
1792 d += x1 - x2; | |
1793 | |
1794 return d; | |
1795 } | |
1796 | |
1797 void | |
1798 nearestpoints(struct room *a, struct room *b, size_t *ax, size_t *ay, si… | |
1799 { | |
1800 if (a->y >= b->y && a->y < b->y + b->h) { | |
1801 *ay = *by = a->y; | |
1802 } else if (b->y >= a->y && b->y < a->y + a->h) { | |
1803 *ay = *by = b->y; | |
1804 } else if (a->y >= b->y) { | |
1805 *ay = a->y; | |
1806 *by = b->y + b->h - 1; | |
1807 } else if (b->y >= a->y) { | |
1808 *ay = a->y + a->h - 1; | |
1809 *by = b->y; | |
1810 } | |
1811 | |
1812 if (a->x >= b->x && a->x < b->x + b->w) { | |
1813 *ax = *bx = a->x; | |
1814 } else if (b->x >= a->x && b->x < a->x + a->w) { | |
1815 *ax = *bx = b->x; | |
1816 } else if (a->x >= b->x) { | |
1817 *ax = a->x; | |
1818 *bx = b->x + b->w - 1; | |
1819 } else if (b->x >= a->x) { | |
1820 *ax = a->x + a->w - 1; | |
1821 *bx = b->x; | |
1822 } | |
1823 } | |
1824 | |
1825 size_t | |
1826 roomdistance(struct room *a, struct room *b) | |
1827 { | |
1828 size_t x1, y1; | |
1829 size_t x2, y2; | |
1830 | |
1831 nearestpoints(a, b, &x1, &y1, &x2, &y2); | |
1832 | |
1833 return distance(x1, y1, x2, y2); | |
1834 } | |
1835 | |
1836 struct room * | |
1837 nearestroom(struct room *rs, size_t l, struct room *x, uint32_t prng) | |
1838 { | |
1839 size_t i, d, cd; | |
1840 ssize_t j; | |
1841 double n; | |
1842 | |
1843 j = -1; | |
1844 d = UINT32_MAX; | |
1845 for (i = 0; i < l; i++) { | |
1846 if (&rs[i] == x) | |
1847 continue; | |
1848 if ((cd = roomdistance(&rs[i], x)) < d) { | |
1849 j = i; | |
1850 d = cd; | |
1851 n = 1; | |
1852 } else if (cd == d) { | |
1853 n++; | |
1854 if (xorshift(&prng) / (UINT32_MAX + 1.) < 1. / n) | |
1855 j = i; | |
1856 } | |
1857 } | |
1858 | |
1859 if (j == -1) | |
1860 return NULL; | |
1861 | |
1862 return &rs[j]; | |
1863 } | |
1864 | |
1865 void | |
1866 connectrooms(struct room *a, struct room *b) | |
1867 { | |
1868 size_t i, j; | |
1869 ssize_t ii; | |
1870 size_t x1, y1; | |
1871 size_t x2, y2; | |
1872 | |
1873 nearestpoints(a, b, &x1, &y1, &x2, &y2); | |
1874 | |
1875 if (y1 > y2) { | |
1876 ii = -1; | |
1877 } else if (y2 > y1) { | |
1878 ii = 1; | |
1879 } else { | |
1880 ii = 0; | |
1881 } | |
1882 | |
1883 /* | |
1884 printf("%lu\t%lu\t%d\n", y1, y2, ii); | |
1885 */ | |
1886 for (i = y1; i != y2; i += ii) | |
1887 map[i][x1].c = '.'; | |
1888 | |
1889 if (x1 > x2) { | |
1890 ii = -1; | |
1891 } else if (x2 > x1) { | |
1892 ii = 1; | |
1893 } else { | |
1894 ii = 0; | |
1895 } | |
1896 | |
1897 for (i = x1; i != x2; i += ii) | |
1898 map[y2][i].c = '.'; | |
1899 } | |
1900 | |
1901 void | |
1902 rendermap(void) | |
1903 { | |
1904 size_t i, j; | |
1905 | |
1906 for (i = 0; i < MAPHEIGHT; i++) { | |
1907 for (j = 0; j < MAPWIDTH; j++) | |
1908 putchar(map[i][j].c); | |
1909 putchar('\n'); | |
1910 } | |
1911 } | |
1912 | |
1913 size_t | |
1914 diff(size_t a, size_t b) | |
1915 { | |
1916 if (a < b) | |
1917 return b - a; | |
1918 return a - b; | |
1919 } | |
1920 | |
1921 /* | |
1922 https://en.wikipedia.org/wiki/Levenshtein_distance#Recursive | |
1923 */ | |
1924 size_t | |
1925 levenshteindistance_slow(char *a, char *b) | |
1926 { | |
1927 size_t k, l, m; | |
1928 | |
1929 if (!*a) | |
1930 return strlen(b); | |
1931 else if (!*b) | |
1932 return strlen(a); | |
1933 else if (*a == *b) | |
1934 return levenshteindistance_slow(a + 1, b + 1); | |
1935 | |
1936 k = levenshteindistance_slow(a + 1, b); | |
1937 l = levenshteindistance_slow(a, b + 1); | |
1938 m = levenshteindistance_slow(a + 1, b + 1); | |
1939 | |
1940 if (k < l && k < m) | |
1941 return 1 + k; | |
1942 else if (l < k && l < m) | |
1943 return 1 + l; | |
1944 else | |
1945 return 1 + m; | |
1946 } | |
1947 | |
1948 ssize_t | |
1949 placeitems_kmedoid(char *host, char *port, char *selector, struct gopher… | |
1950 { | |
1951 size_t i, j; | |
1952 ssize_t r; | |
1953 double *distances, d; | |
1954 double *mdists; | |
1955 struct { | |
1956 double selector; | |
1957 double segment; | |
1958 double index; | |
1959 } *distanceparts, maxdistanceparts; | |
1960 uint32_t prng; | |
1961 struct point *points; | |
1962 | |
1963 distanceparts = xmalloc(triangularnumber(l) * sizeof(*distancepa… | |
1964 | |
1965 memset(&maxdistanceparts, 0, sizeof(maxdistanceparts)); | |
1966 for (i = 0; i < l; i++) { | |
1967 memset(&distanceparts[distanceindex(i, i)], 0, sizeof(*d… | |
1968 for (j = 0; j < i; j++) { | |
1969 distanceparts[distanceindex(i, j)].selector = le… | |
1970 distanceparts[distanceindex(i, j)].segment = dif… | |
1971 distanceparts[distanceindex(i, j)].index = diff(… | |
1972 | |
1973 if (distanceparts[distanceindex(i, j)].selector … | |
1974 maxdistanceparts.selector = distancepart… | |
1975 if (distanceparts[distanceindex(i, j)].segment >… | |
1976 maxdistanceparts.segment = distanceparts… | |
1977 if (distanceparts[distanceindex(i, j)].index > m… | |
1978 maxdistanceparts.index = distanceparts[d… | |
1979 } | |
1980 } | |
1981 for (i = 0; i < l; i++) { | |
1982 for (j = 0; j < i; j++) { | |
1983 distanceparts[distanceindex(i, j)].selector /= m… | |
1984 distanceparts[distanceindex(i, j)].segment /= ma… | |
1985 distanceparts[distanceindex(i, j)].index /= maxd… | |
1986 } | |
1987 } | |
1988 | |
1989 distances = xmalloc(triangularnumber(l) * sizeof(*distances)); | |
1990 prng = fnv1a(4, host, port, selector, "wiggle"); | |
1991 for (i = 0; i < l; i++) { | |
1992 distances[distanceindex(i, i)] = 0; | |
1993 for (j = 0; j < i; j++) | |
1994 distances[distanceindex(i, j)] = + distanceparts… | |
1995 } | |
1996 free(distanceparts); | |
1997 | |
1998 r = kmedoids(g, l, k, distances, assocs, fnv1a(4, host, port, se… | |
1999 | |
2000 points = calloc(l, sizeof(*points)); | |
2001 sammon(distances, l, fnv1a(4, host, port, selector, "sammonseed"… | |
2002 | |
2003 for (i = 0; i < l; i++) | |
2004 printf("%lf\t%lf\t%ld\t%lu\t%s\n", points[i].dims[0], po… | |
2005 | |
2006 free(points); | |
2007 free(distances); | |
2008 | |
2009 return r; | |
2010 } | |
2011 | |
2012 size_t | |
2013 placeitems_hash(char *host, char *port, char *selector, struct gopherent… | |
2014 { | |
2015 size_t i; | |
2016 | |
2017 for (i = 0; i < l; i++) | |
2018 assocs[i] = fnv1a(6, host, port, selector, g[i].fields[1… | |
2019 | |
2020 return k; | |
2021 } | |
2022 | |
2023 size_t py, px; | |
2024 | |
2025 enum { | |
2026 Portal, | |
2027 StaircaseDown, | |
2028 Bookshelf | |
2029 }; | |
2030 | |
2031 void | |
2032 generatemap(char *host, char *port, char *selector, struct gopherentry *… | |
2033 { | |
2034 size_t i, j, k; | |
2035 size_t x, y; | |
2036 ssize_t n, m; | |
2037 size_t *cassocs; | |
2038 struct room *rooms, *r; | |
2039 struct { | |
2040 unsigned char x, y; | |
2041 } positions[3]; | |
2042 uint32_t prng; | |
2043 char buffer[3]; | |
2044 | |
2045 memset(map, 0, sizeof(map)); | |
2046 | |
2047 for (i = 0; i < MAPHEIGHT; i++) { | |
2048 for (j = 0; j < MAPWIDTH; j++) { | |
2049 map[i][j].c = '#'; | |
2050 } | |
2051 } | |
2052 k = 7; | |
2053 rooms = calloc(k, sizeof(*rooms)); | |
2054 if (!rooms) | |
2055 return; | |
2056 k = generaterooms_gnarf(host, port, selector, rooms, k); | |
2057 | |
2058 cassocs = calloc(l, sizeof(*cassocs)); | |
2059 if (!cassocs) | |
2060 goto cleanup; | |
2061 | |
2062 k = placeitems_kmedoid(host, port, selector, g, l, cassocs, k); | |
2063 | |
2064 /* Insert rooms */ | |
2065 for (i = 0; i < k; i++) { | |
2066 for (y = rooms[i].y; y < rooms[i].y + rooms[i].h; y++) { | |
2067 for (x = rooms[i].x; x < rooms[i].x + rooms[i].w… | |
2068 map[y][x].c = '.'; | |
2069 } | |
2070 } | |
2071 | |
2072 /* Insert connections */ | |
2073 for (i = 0; i < k; i++) { | |
2074 if (rooms[i].p) | |
2075 connectrooms(&rooms[i], rooms[i].p); | |
2076 /* | |
2077 if ((r = nearestroom(rooms, i, &rooms[i], fnv1a(4, host,… | |
2078 connectrooms(&rooms[i], r); | |
2079 */ | |
2080 } | |
2081 | |
2082 /* Insert items */ | |
2083 for (i = 0; i < k; i++) { | |
2084 snprintf(buffer, sizeof(buffer), "%d", i); | |
2085 prng = fnv1a(4, host, port, selector, buffer); | |
2086 for (j = 0; j < 3; j++) { | |
2087 /* Ugly brute force strategy... I'm sure there i… | |
2088 do { | |
2089 positions[j].x = rooms[i].x + xorshift(&… | |
2090 positions[j].y = rooms[i].y + xorshift(&… | |
2091 for (m = 0; m < j && positions[m].x != p… | |
2092 positions[m].y != p… | |
2093 } while (m < j); | |
2094 } | |
2095 for (j = 0; j < l; j++) { | |
2096 if (cassocs[j] != i) | |
2097 continue; | |
2098 /* | |
2099 printf("%s\t%lu\n", g[j].fields[1], cassocs[j]); | |
2100 */ | |
2101 switch (g[j].type) { | |
2102 case '0': | |
2103 x = positions[Bookshelf].x; | |
2104 y = positions[Bookshelf].y; | |
2105 map[y][x].c = 'E'; | |
2106 break; | |
2107 case '1': | |
2108 if (strcmp(g[j].fields[2], host) || strc… | |
2109 x = positions[Portal].x; | |
2110 y = positions[Portal].y; | |
2111 map[y][x].c = 'O'; | |
2112 } else { | |
2113 x = positions[StaircaseDown].x; | |
2114 y = positions[StaircaseDown].y; | |
2115 if (map[y][x].data) | |
2116 map[y][x].c = 'L'; | |
2117 else | |
2118 map[y][x].c = '>'; | |
2119 } | |
2120 break; | |
2121 } | |
2122 g[j].next = map[y][x].data; | |
2123 map[y][x].data = &g[j]; | |
2124 } | |
2125 } | |
2126 | |
2127 free(cassocs); | |
2128 cleanup: | |
2129 free(rooms); | |
2130 } | |
2131 | |
2132 char gopherbuffer[16 * 1024 * 1024]; | |
2133 | |
2134 void | |
2135 interact(void) | |
2136 { | |
2137 } | |
2138 | |
2139 void | |
2140 loop(void) | |
2141 { | |
2142 char c; | |
2143 | |
2144 do { | |
2145 switch (c) { | |
2146 case 'h': | |
2147 break; | |
2148 case 'j': | |
2149 break; | |
2150 case 'k': | |
2151 break; | |
2152 case 'l': | |
2153 break; | |
2154 case ' ': | |
2155 interact(); | |
2156 break; | |
2157 } | |
2158 } while (1); | |
2159 } | |
2160 | |
2161 int | |
2162 main(int argc, char *argv[]) | |
2163 { | |
2164 ssize_t l; | |
2165 struct gopherentry *g; | |
2166 char *host, *port, *selector; | |
2167 struct termios termios, ntermios; | |
2168 | |
2169 if (argc < 2) { | |
2170 printf("%s host [port [selector]]\n", argv[0]); | |
2171 return 1; | |
2172 } | |
2173 | |
2174 /* | |
2175 memset(&termios, 0, sizeof(termios)); | |
2176 if (tcgetattr(0, &termios) == -1) | |
2177 return 1; | |
2178 | |
2179 memcpy(&ntermios, &termios, sizeof(termios)); | |
2180 ntermios.c_lflag &= ~(ICANON | ECHO); | |
2181 ntermios.c_cc[VMIN] = 1; | |
2182 ntermios.c_cc[VTIME] = 0; | |
2183 | |
2184 if (tcsetattr(0, TCSANOW, &ntermios) == -1) | |
2185 return 1; | |
2186 */ | |
2187 | |
2188 host = argv[1]; | |
2189 port = (argc > 2) ? argv[2] : "70"; | |
2190 selector = (argc > 3) ? argv[3] : ""; | |
2191 | |
2192 do { | |
2193 l = gopher_request(host, port, selector, gopherbuffer, s… | |
2194 if (l == -1) | |
2195 return 1; | |
2196 | |
2197 l = gopher_parsemenu(gopherbuffer, &g); | |
2198 if (l == -1) | |
2199 return 1; | |
2200 | |
2201 l = gopher_removeentries(g, l); | |
2202 | |
2203 generatemap(host, port, selector, g, l); | |
2204 /* | |
2205 rendermap(); | |
2206 */ | |
2207 | |
2208 /* | |
2209 loop(); | |
2210 */ | |
2211 } while (0); | |
2212 | |
2213 /* | |
2214 if (tcsetattr(0, TCSANOW, &termios) == -1) | |
2215 return 1; | |
2216 */ | |
2217 | |
2218 return 0; | |
2219 } |