18b.c (2072B)
1 /* 2 I have lost my code for part one. It reused some stuff from day 3 10. This code can be adjusted to work for part one, just change the 4 input reading part. 5 */ 6 7 #include <inttypes.h> 8 #include <stdio.h> 9 #include <stdlib.h> 10 #include <string.h> 11 12 #define N 1000 13 #define MAX(x,y) ((x)>(y)?(x):(y)) 14 #define MIN(x,y) ((x)<(y)?(x):(y)) 15 16 typedef struct { int64_t i, j; } point_t; 17 18 char *buf, in[50]; 19 int64_t k, l, oldl, n, r, t, nolda, nb, a[N], olda[N], b[N]; 20 point_t p[N]; 21 point_t go[] = {{.i=0, .j=1}, {.i=1, .j=0}, {.i=0, .j=-1}, {.i=-1, .j=0}}; 22 23 int cmp_int64(const void *x, const void *y) { 24 const int64_t *a = x, *b = y; 25 return *a > *b ? 1 : (*a < *b) ? -1 : 0; 26 } 27 28 int cmp_point(const void *x, const void *y) { 29 const point_t *p = x, *q = y; 30 int a = cmp_int64(&p->i, &q->i); 31 int b = cmp_int64(&p->j, &q->j); 32 return a ? a : b; 33 } 34 35 int64_t val(char c) { 36 if (c >= '0' && c <= '9') return c - '0'; 37 return c - 'a' + 10; 38 } 39 40 int64_t removedoubles(int64_t a[], int64_t n) { 41 int64_t i, j = 0; 42 for (i = 0; i < n; i++) { 43 a[j] = a[i]; 44 if (i+1 < n && a[j] == a[i+1]) 45 i++; 46 else 47 j++; 48 } 49 return j; 50 } 51 52 int64_t overlaplen(int64_t a[], int64_t na, int64_t b[], int64_t nb) { 53 int64_t ret = 0; 54 for (int64_t i = 0; 2*i+1 < na; i++) 55 for (int64_t j = 0; 2*j+1 < nb; j++) 56 ret += MAX(0, 57 MIN(a[2*i+1], b[2*j+1]) - MAX(a[2*i], b[2*j]) + 1); 58 return ret; 59 } 60 61 int main() { 62 p[n++] = (point_t) {0}; 63 while ((buf = fgets(in, 50, stdin)) != NULL) { 64 while (*buf != '#') buf++; 65 k = 0; 66 for (int i = 1; i < 6; i++) 67 k = 16*k + val(*(buf+i)); 68 point_t d = go[*(buf+6) - '0']; 69 p[n] = (point_t){.i = p[n-1].i+d.i*k, .j = p[n-1].j+d.j*k}; 70 n++; 71 } 72 73 qsort(p, --n, sizeof(point_t), &cmp_point); 74 75 for (int64_t i = 0, ia = 0; i < n-1; i++) { 76 a[ia++] = p[i].j; 77 if (p[i].i != p[i+1].i) { 78 qsort(a, ia, sizeof(int64_t), &cmp_int64); 79 ia = removedoubles(a, ia); 80 t += overlaplen(a, ia, a, ia)*(p[i+1].i - p[i].i + 1) - 81 overlaplen(a, ia, olda, nolda); 82 nolda = ia; 83 memcpy(olda, a, nolda * sizeof(int64_t)); 84 } 85 } 86 87 printf("%" PRId64 "\n", t); 88 return 0; 89 }