puzzle.c (2966B)
1 #define _DEFAULT_SOURCE 2 3 #include <limits.h> 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <errno.h> 7 #include <string.h> 8 #include <strings.h> 9 #include <assert.h> 10 #include <stdbool.h> 11 12 #define MAX(a,b) (((a)>(b))?(a):(b)) 13 #define MIN(a,b) (((a)<(b))?(a):(b)) 14 15 #define STR_LEN 2048 16 17 typedef struct Vec2 { 18 int x, y; 19 struct Vec2 *next; 20 } Vec2; 21 22 Vec2 * make_vec2(int x, int y) { 23 Vec2 *v = malloc(sizeof(Vec2)); 24 v->x = x; 25 v->y = y; 26 v->next = NULL; 27 return v; 28 } 29 30 typedef struct List { 31 Vec2 *first; 32 Vec2 *last; 33 } List; 34 void list_add(List *l, int x, int y) { 35 Vec2 *v = make_vec2(x, y); 36 if (l->first==NULL) l->first = v; 37 if (l->last!=NULL) l->last->next = v; 38 l->last = v; 39 } 40 bool list_has(List *l, int x, int y) { 41 Vec2 *v1 = l->first; 42 while (v1!=NULL) { 43 if (v1->x==x && v1->y==y) { 44 return true; 45 } 46 v1 = v1->next; 47 } 48 return false; 49 } 50 void list_print(List *l) { 51 Vec2 *v1 = l->first; 52 while (v1!=NULL) { 53 printf("x:%2d,y:%2d (%p)\n",v1->x, v1->y, v1); 54 v1 = v1->next; 55 } 56 } 57 58 int calc_dist(Vec2 *v1, Vec2 *v2, List *emptiness, int incr) { 59 int min_x = MIN(v1->x, v2->x); 60 int max_x = MAX(v1->x, v2->x); 61 int min_y = MIN(v1->y, v2->y); 62 int max_y = MAX(v1->y, v2->y); 63 int dx = max_x - min_x; 64 int dy = max_y - min_y; 65 for (int x=min_x; x<max_x; ++x) { 66 if (list_has(emptiness, x, -1)) { 67 dx+=incr-1; 68 } 69 } 70 71 for (int y=min_y; y<max_y; ++y) { 72 if (list_has(emptiness, -1, y)) { 73 dy+=incr-1; 74 } 75 } 76 77 return dx+dy; 78 } 79 80 void puzzle(const char *filename, long long *result1, long long *result2) { 81 FILE *infile = fopen(filename, "r"); 82 if (infile == NULL) { 83 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 84 return; 85 } 86 87 char buf[STR_LEN] = {0}; 88 unsigned int line_num = 0; 89 int cols = 0; 90 int rows = 0; 91 char *map = NULL; 92 size_t map_size = 0; 93 94 while (fgets(buf, STR_LEN, infile) != NULL) { 95 int len = strlen(buf)-1; // ignore \n 96 if (cols==0) cols = len; 97 if (cols!=len) printf("width mismatch\n"); 98 99 map_size += cols*(line_num+1)*sizeof(char); 100 map = realloc(map, map_size); 101 for (int x=0; x<cols; ++x) { 102 map[line_num*cols+x] = buf[x]; 103 } 104 105 ++line_num; 106 bzero(buf, STR_LEN); 107 } 108 rows = line_num; 109 110 List galaxies = {0}; 111 List emptiness = {0}; 112 113 for (int y=0;y<rows;++y) { 114 bool y_empty = true; 115 for (int x=0;x<cols;++x) { 116 if (map[y*cols+x]=='#') { 117 list_add(&galaxies, x, y); 118 y_empty = false; 119 } 120 } 121 if (y_empty) { 122 list_add(&emptiness, -1, y); 123 } 124 } 125 for (int x=0; x<cols; ++x) { 126 bool x_empty = true; 127 for (int y=0; y<rows; ++y) { 128 if (map[y*cols+x]=='#') { 129 x_empty = false; 130 } 131 } 132 if (x_empty) { 133 list_add(&emptiness, x, -1); 134 } 135 } 136 137 *result1 = 0; 138 *result2 = 0; 139 Vec2 *g1 = galaxies.first; 140 while (g1!=NULL) { 141 Vec2 *g2 = g1; 142 while (g2!=NULL) { 143 if (g1!=g2) { 144 *result1 += calc_dist(g1, g2, &emptiness, 1); 145 *result2 += calc_dist(g1, g2, &emptiness, 1000000); 146 } 147 g2 = g2->next; 148 } 149 g1 = g1->next; 150 } 151 152 // mutiny! ignoring feof/ferror. 153 fclose(infile); 154 155 (void)result2; 156 }