uppgb.c (6495B)
1 #include "common.h" 2 #include <sys/queue.h> 3 4 typedef struct cube { 5 uint64_t coord[3]; 6 7 size_t nnbrs; 8 size_t *nbrs; 9 } cube; 10 11 void print_cube(cube *c) { 12 printf("(%llu, %llu, %llu)\n", c->coord[0], c->coord[1], c->coord[2]); 13 } 14 15 typedef struct entry { 16 uint64_t x; 17 uint64_t y; 18 uint64_t z; 19 20 STAILQ_ENTRY(entry) entries; 21 } entry; 22 23 int adjacent(cube *a, cube *b) { 24 int x1 = a->coord[0]; 25 int x2 = b->coord[0]; 26 int y1 = a->coord[1]; 27 int y2 = b->coord[1]; 28 int z1 = a->coord[2]; 29 int z2 = b->coord[2]; 30 return (abs(x1 - x2) <= 1 && y1 == y2 && z1 == z2) || 31 (abs(y1 - y2) <= 1 && x1 == x2 && z1 == z2) || 32 (abs(z1 - z2) <= 1 && x1 == x2 && y1 == y2); 33 } 34 35 void add_nbr(cube *x, size_t nbr_index) { 36 // printf("adding nbrs to cube (%llu, %llu, %llu)\n", x->coord[0], 37 //x->coord[1], x->coord[2]); 38 x->nbrs[x->nnbrs] = nbr_index; 39 x->nnbrs++; 40 } 41 42 uint64_t e(cube *cubes, size_t ncubes) { 43 uint64_t c = 0; 44 45 size_t i; 46 for (i = 0; i < ncubes; i++) 47 c += cubes[i].nnbrs; 48 49 return c / 2; 50 } 51 52 int main(int argc, char **argv) { 53 char **lines; 54 size_t nlines = readlines(&lines, "input"); 55 printf("#lines: %lu\n", nlines); 56 57 cube cubes[nlines]; 58 size_t i, j, k; 59 for (i = 0; i < nlines; i++) { 60 char *line = lines[i]; 61 line = sread_next_u64(&cubes[i].coord[0], line); 62 line = sread_next_u64(&cubes[i].coord[1], line); 63 line = sread_next_u64(&cubes[i].coord[2], line); 64 } 65 66 uint64_t maxx = 0, maxy = 0, maxz = 0; 67 for (i = 0; i < nlines; i++) { 68 if (maxx < cubes[i].coord[0]) 69 maxx = cubes[i].coord[0]; 70 if (maxy < cubes[i].coord[1]) 71 maxy = cubes[i].coord[1]; 72 if (maxz < cubes[i].coord[2]) 73 maxz = cubes[i].coord[2]; 74 } 75 76 printf("maxx = %llu, maxy = %llu, maxz = %llu\n", maxx, maxy, maxz); 77 78 uint8_t filler[maxx + 1][maxy + 1][maxz + 1]; 79 memset(filler, 0, (maxx + 1) * (maxy + 1) * (maxz + 1)); 80 81 for (i = 0; i < nlines; i++) { 82 filler[cubes[i].coord[0]][cubes[i].coord[1]][cubes[i].coord[2]] = 2; 83 } 84 85 size_t filled = 0; 86 STAILQ_HEAD(listhead, entry) head = STAILQ_HEAD_INITIALIZER(head); 87 88 entry *elt; 89 90 for (i = 0; i < maxy + 1; i++) { 91 for (j = 0; j < maxz + 1; j++) { 92 if (filler[0][i][j] == 0) { 93 elt = malloc(sizeof(*elt)); 94 elt->x = 0; 95 elt->y = i; 96 elt->z = j; 97 filler[elt->x][elt->y][elt->z] = 1; 98 STAILQ_INSERT_TAIL(&head, elt, entries); 99 } 100 if (filler[maxx][i][j] == 0) { 101 elt = malloc(sizeof(*elt)); 102 elt->x = maxx; 103 elt->y = i; 104 elt->z = j; 105 filler[elt->x][elt->y][elt->z] = 1; 106 STAILQ_INSERT_TAIL(&head, elt, entries); 107 } 108 } 109 } 110 111 for (i = 0; i < maxx + 1; i++) { 112 for (j = 0; j < maxz + 1; j++) { 113 if (filler[i][0][j] == 0) { 114 elt = malloc(sizeof(*elt)); 115 elt->x = i; 116 elt->y = 0; 117 elt->z = j; 118 filler[elt->x][elt->y][elt->z] = 1; 119 STAILQ_INSERT_TAIL(&head, elt, entries); 120 } 121 if (filler[i][maxy][j] == 0) { 122 elt = malloc(sizeof(*elt)); 123 elt->x = i; 124 elt->y = maxy; 125 elt->z = j; 126 filler[elt->x][elt->y][elt->z] = 1; 127 STAILQ_INSERT_TAIL(&head, elt, entries); 128 } 129 } 130 } 131 132 for (i = 0; i < maxx + 1; i++) { 133 for (j = 0; j < maxy + 1; j++) { 134 if (filler[i][j][0] == 0) { 135 elt = malloc(sizeof(*elt)); 136 elt->x = i; 137 elt->y = j; 138 elt->z = 0; 139 filler[elt->x][elt->y][elt->z] = 1; 140 STAILQ_INSERT_TAIL(&head, elt, entries); 141 } 142 if (filler[i][j][maxz] == 0) { 143 elt = malloc(sizeof(*elt)); 144 elt->x = i; 145 elt->y = j; 146 elt->z = maxz; 147 filler[elt->x][elt->y][elt->z] = 1; 148 STAILQ_INSERT_TAIL(&head, elt, entries); 149 } 150 } 151 } 152 153 while (!STAILQ_EMPTY(&head)) { 154 elt = STAILQ_FIRST(&head); 155 STAILQ_REMOVE_HEAD(&head, entries); 156 filled++; 157 158 if (elt->x > 0 && filler[elt->x - 1][elt->y][elt->z] == 0) { 159 entry *new = malloc(sizeof(*new)); 160 new->x = elt->x - 1; 161 new->y = elt->y; 162 new->z = elt->z; 163 filler[new->x][new->y][new->z] = 1; 164 STAILQ_INSERT_TAIL(&head, new, entries); 165 } 166 if (elt->x < maxx && filler[elt->x + 1][elt->y][elt->z] == 0) { 167 entry *new = malloc(sizeof(*new)); 168 new->x = elt->x + 1; 169 new->y = elt->y; 170 new->z = elt->z; 171 filler[new->x][new->y][new->z] = 1; 172 STAILQ_INSERT_TAIL(&head, new, entries); 173 } 174 175 if (elt->y > 0 && filler[elt->x][elt->y - 1][elt->z] == 0) { 176 entry *new = malloc(sizeof(*new)); 177 new->x = elt->x; 178 new->y = elt->y - 1; 179 new->z = elt->z; 180 filler[new->x][new->y][new->z] = 1; 181 STAILQ_INSERT_TAIL(&head, new, entries); 182 } 183 if (elt->y < maxy && filler[elt->x][elt->y + 1][elt->z] == 0) { 184 entry *new = malloc(sizeof(*new)); 185 new->x = elt->x; 186 new->y = elt->y + 1; 187 new->z = elt->z; 188 filler[new->x][new->y][new->z] = 1; 189 STAILQ_INSERT_TAIL(&head, new, entries); 190 } 191 192 if (elt->z > 0 && filler[elt->x][elt->y][elt->z - 1] == 0) { 193 entry *new = malloc(sizeof(*new)); 194 new->x = elt->x; 195 new->y = elt->y; 196 new->z = elt->z - 1; 197 filler[new->x][new->y][new->z] = 1; 198 STAILQ_INSERT_TAIL(&head, new, entries); 199 } 200 if (elt->z < maxz && filler[elt->x][elt->y][elt->z + 1] == 0) { 201 entry *new = malloc(sizeof(*new)); 202 new->x = elt->x; 203 new->y = elt->y; 204 new->z = elt->z + 1; 205 filler[new->x][new->y][new->z] = 1; 206 STAILQ_INSERT_TAIL(&head, new, entries); 207 } 208 209 free(elt); 210 } 211 212 size_t nucubes = (maxx + 1) * (maxy + 1) * (maxz + 1) - filled; 213 printf("nucubes = %zu\n", nucubes); 214 215 cube ucubes[nucubes]; 216 size_t c = 0; 217 for (i = 0; i < maxx + 1; i++) { 218 for (j = 0; j < maxy + 1; j++) { 219 for (k = 0; k < maxz + 1; k++) { 220 if (filler[i][j][k] != 1) { 221 ucubes[c].coord[0] = i; 222 ucubes[c].coord[1] = j; 223 ucubes[c].coord[2] = k; 224 225 ucubes[c].nnbrs = 0; 226 ucubes[c].nbrs = malloc(nucubes * sizeof(*(ucubes[c].nbrs))); 227 228 c++; 229 } 230 } 231 } 232 } 233 234 for (i = 0; i < nucubes; i++) { 235 for (j = i + 1; j < nucubes; j++) { 236 if (adjacent(&ucubes[i], &ucubes[j])) { 237 add_nbr(&ucubes[i], j); 238 add_nbr(&ucubes[j], i); 239 } 240 } 241 } 242 243 for (i = 0; i < nucubes; i++) { 244 print_cube(&ucubes[i]); 245 } 246 247 uint64_t ee = e(ucubes, nucubes); 248 printf("ee = %llu\n", ee); 249 250 assert(6 * nucubes >= ee); 251 printf("%llu\n", 6 * nucubes - 2 * ee); 252 }