day03.c (3149B)
1 #include <stdio.h> 2 #include <inttypes.h> 3 #include <stdbool.h> 4 #include <stdlib.h> 5 #include "cputime.h" 6 7 typedef struct { 8 char data[8]; 9 int len; 10 } Buffer; 11 12 typedef struct { 13 int x, y; 14 } Vec2; 15 16 typedef struct { 17 Vec2 p1, p2; 18 int len; 19 } Line; 20 21 typedef struct { 22 int len; 23 Line lines[512]; 24 } Wire; 25 26 int btoi(Buffer buf) { 27 int num = 0; 28 for (int i=0;i<buf.len;++i) num = num*10+buf.data[i]; 29 return num; 30 } 31 32 Line normalize(Line l) { 33 if (l.p1.x>l.p2.x || l.p1.y>l.p2.y) { 34 Vec2 t = l.p1; 35 l.p1 = l.p2; 36 l.p2 = t; 37 } 38 return l; 39 } 40 41 bool get_intersection(Line * restrict l1, Line * restrict l2, Vec2 * restrict p, int64_t * restrict steps) { 42 (void)steps; 43 Line ln1 = normalize(*l1); 44 Line ln2 = normalize(*l2); 45 if (ln1.p1.x==ln1.p2.x) { // ln1 vertical 46 if (ln2.p1.x==ln2.p2.x) return false; // ln2 is vertical too 47 if (ln1.p1.x>ln2.p1.x && ln1.p2.x<ln2.p2.x && 48 ln2.p1.y>ln1.p1.y && ln2.p2.y<ln1.p2.y) { 49 p->x = ln1.p1.x; 50 p->y = ln2.p1.y; 51 *steps = abs(l1->p1.y - p->y) + abs(l2->p1.x - p->x); 52 return true; 53 } 54 } else if (ln1.p1.y==ln1.p2.y) { // ln1 horizontal 55 if (ln2.p1.y==ln2.p2.y) return false; // ln2 is horizontal too 56 if (ln2.p1.x>ln1.p1.x && ln2.p2.x<ln1.p2.x && 57 ln1.p1.y>ln2.p1.y && ln1.p2.y<ln2.p2.y) { 58 p->x = ln2.p1.x; 59 p->y = ln1.p1.y; 60 *steps = abs(l1->p1.x - p->x) + abs(l2->p1.y - p->y); 61 return true; 62 } 63 } 64 return false; 65 } 66 67 int main(void) { 68 Buffer buf = {0}; 69 Vec2 prev = {0}; 70 Wire w1 = {0}; 71 Wire w2 = {0}; 72 Wire *cw = &w1; 73 char dir; 74 for (int c=getchar();c!=EOF;c=getchar()) { 75 if (c==','||c=='\n') { 76 int dist = btoi(buf); 77 buf.len = 0; 78 Vec2 p = prev; 79 if (dir=='U') p.y += dist; 80 else if (dir=='D') p.y -= dist; 81 else if (dir=='L') p.x -= dist; 82 else if (dir=='R') p.x += dist; 83 cw->lines[cw->len++] = (Line){ .p1=prev, .p2=p, .len=dist }; 84 prev = p; 85 if (c=='\n') { 86 cw = &w2; 87 prev.x = 0; 88 prev.y = 0; 89 } 90 } else if (c>='A'&&c<='Z') { 91 dir = c; 92 } else { 93 buf.data[buf.len++] = c-'0'; 94 } 95 } 96 int64_t p1 = 0; 97 int64_t p2 = 0; 98 99 int64_t steps1 = 0; 100 for (int i=0;i<w1.len;++i) { 101 int64_t steps2 = 0; 102 for (int j=0;j<w2.len;++j) { 103 Vec2 p = {0}; 104 int64_t steps = 0; 105 if (get_intersection(&w1.lines[i], &w2.lines[j], &p, &steps)) { 106 int dist = abs(p.x)+abs(p.y); 107 if (p1==0) p1 = dist; 108 else if (dist<p1) p1 = dist; 109 int64_t steps_sum = steps1+steps2+steps; 110 if (p2==0) p2 = steps_sum; 111 else if (steps_sum<p2) p2 = steps_sum; 112 } 113 steps2 += w2.lines[j].len; 114 } 115 steps1 += w1.lines[i].len; 116 } 117 printf("p1: %"PRIi64"\np2: %"PRIi64"\n", p1, p2); 118 return 0; 119 }