puzzle.c (6628B)
1 #define _DEFAULT_SOURCE 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <errno.h> 6 #include <string.h> 7 #include <strings.h> 8 #include <assert.h> 9 #include <ctype.h> 10 #include <stdbool.h> 11 #include <math.h> 12 13 #include "util.h" 14 15 #define STR_LEN 1024 16 17 struct cuboid_t { 18 long long x1, y1, x2, y2, z1, z2; 19 bool on; 20 }; 21 22 void parse_cuboid(struct array_t *array, const char *str); 23 void init_cubes(bool (*cubes)[101][101][101], struct array_t *cuboids); 24 long long count_cubes(bool (*cubes)[101][101][101]); 25 struct array_t subtract_cuboid(struct cuboid_t *c1, struct cuboid_t *c2); 26 void add_cuboid(struct array_t *cuboids, struct cuboid_t *cuboid); 27 long long cuboid_size(struct cuboid_t *cuboid); 28 29 void puzzle(const char *filename, long long *result1, long long *result2) { 30 FILE *infile = fopen(filename, "r"); 31 if (infile == NULL) { 32 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 33 return; 34 } 35 36 char buf[STR_LEN] = {0}; 37 38 struct array_t sequence = { .data = NULL }; 39 array_init(&sequence, sizeof(struct cuboid_t), 10); 40 41 while (fgets(buf, STR_LEN, infile) != NULL) { 42 parse_cuboid(&sequence, buf); 43 bzero(buf, STR_LEN); 44 } 45 46 bool cubes[101][101][101] = {0}; 47 48 init_cubes(&cubes, &sequence); 49 *result1 = count_cubes(&cubes); 50 51 struct array_t cuboids = { .data = NULL }; 52 array_init(&cuboids, sizeof(struct cuboid_t), 100); 53 54 struct cuboid_t *seq_data = sequence.data; 55 for (size_t i = 0; i < sequence.count; ++i) { 56 struct cuboid_t *seq_cuboid = &seq_data[i]; 57 seq_cuboid->x2 += 1; 58 seq_cuboid->y2 += 1; 59 seq_cuboid->z2 += 1; 60 struct array_t new_cuboids = { .data = NULL }; 61 array_init(&new_cuboids, sizeof(struct cuboid_t), 100); 62 63 struct cuboid_t *cuboids_data = cuboids.data; 64 for (size_t j = 0; j < cuboids.count; ++j) { 65 struct cuboid_t *c = &cuboids_data[j]; 66 struct array_t subtracted = subtract_cuboid(c, seq_cuboid); 67 struct cuboid_t *subtracted_data = subtracted.data; 68 for (size_t k = 0; k < subtracted.count; ++k) { 69 if (cuboid_size(&subtracted_data[k]) > 0) { 70 add_cuboid(&new_cuboids, &subtracted_data[k]); 71 } 72 } 73 free(subtracted.data); 74 } 75 if (seq_cuboid->on) { 76 add_cuboid(&new_cuboids, seq_cuboid); 77 } 78 free(cuboids.data); 79 cuboids = new_cuboids; 80 cuboids.cap = cuboids.count; 81 } 82 83 *result2 = 0; 84 struct cuboid_t *cuboids_data = cuboids.data; 85 for (size_t i = 0; i < cuboids.count; ++i) { 86 *result2 += cuboid_size(&cuboids_data[i]); 87 } 88 89 free(sequence.data); 90 // mutiny! ignoring feof/ferror. 91 fclose(infile); 92 } 93 94 void add_cuboid(struct array_t *cuboids, struct cuboid_t *cuboid) { 95 if (cuboids->count >= cuboids->cap) { 96 array_expand(cuboids); 97 } 98 struct cuboid_t *cuboids_data = cuboids->data; 99 cuboids_data[cuboids->count++] = *cuboid; 100 } 101 102 struct array_t subtract_cuboid(struct cuboid_t *c1, struct cuboid_t *c2) { 103 assert(c1 != NULL && c2 != NULL); 104 105 struct array_t array = { .data = NULL }; 106 array_init(&array, sizeof(struct cuboid_t), 6); 107 struct cuboid_t *cuboids = array.data; 108 109 if (!(c1->x1 < c2->x2 && c1->x2 > c2->x1 && 110 c1->y1 < c2->y2 && c1->y2 > c2->y1 && 111 c1->z1 < c2->z2 && c1->z2 > c2->z1)) { 112 113 add_cuboid(&array, c1); 114 return array; 115 } else { 116 struct cuboid_t c = { 117 .x1 = fmin(fmax(c1->x1, c2->x1), c1->x2), 118 .x2 = fmin(fmax(c1->x1, c2->x2), c1->x2), 119 .y1 = fmin(fmax(c1->y1, c2->y1), c1->y2), 120 .y2 = fmin(fmax(c1->y1, c2->y2), c1->y2), 121 .z1 = fmin(fmax(c1->z1, c2->z1), c1->z2), 122 .z2 = fmin(fmax(c1->z1, c2->z2), c1->z2) 123 }; 124 struct cuboid_t *c3 = &c; 125 cuboids[array.count++] = (struct cuboid_t){ 126 .x1 = c1->x1, .x2 = c3->x1, 127 .y1 = c1->y1, .y2 = c1->y2, 128 .z1 = c1->z1, .z2 = c1->z2 129 }; 130 cuboids[array.count++] = (struct cuboid_t){ 131 .x1 = c3->x2, .x2 = c1->x2, 132 .y1 = c1->y1, .y2 = c1->y2, 133 .z1 = c1->z1, .z2 = c1->z2 134 }; 135 cuboids[array.count++] = (struct cuboid_t){ 136 .x1 = c3->x1, .x2 = c3->x2, 137 .y1 = c1->y1, .y2 = c3->y1, 138 .z1 = c1->z1, .z2 = c1->z2 139 }; 140 cuboids[array.count++] = (struct cuboid_t){ 141 .x1 = c3->x1, .x2 = c3->x2, 142 .y1 = c3->y2, .y2 = c1->y2, 143 .z1 = c1->z1, .z2 = c1->z2 144 }; 145 cuboids[array.count++] = (struct cuboid_t){ 146 .x1 = c3->x1, .x2 = c3->x2, 147 .y1 = c3->y1, .y2 = c3->y2, 148 .z1 = c1->z1, .z2 = c3->z1 149 }; 150 cuboids[array.count++] = (struct cuboid_t){ 151 .x1 = c3->x1, .x2 = c3->x2, 152 .y1 = c3->y1, .y2 = c3->y2, 153 .z1 = c3->z2, .z2 = c1->z2 154 }; 155 return array; 156 } 157 } 158 159 void init_cubes(bool (*cubes)[101][101][101], struct array_t *sequence) { 160 assert(cubes != NULL); 161 assert(sequence != NULL); 162 assert(sequence->data != NULL); 163 164 struct cuboid_t *sequence_data = sequence->data; 165 for (size_t i = 0; i < sequence->count; ++i) { 166 struct cuboid_t *cuboid = &sequence_data[i]; 167 if (cuboid->x1 >= -50 && cuboid->x2 <= 50 && 168 cuboid->y1 >= -50 && cuboid->y2 <= 50 && 169 cuboid->z1 >= -50 && cuboid->z2 <= 50) { 170 171 for (int x = cuboid->x1; x <= cuboid->x2; ++x) { 172 for (int y = cuboid->y1; y <= cuboid->y2; ++y) { 173 for (int z = cuboid->z1; z <= cuboid->z2; ++z) { 174 (*cubes)[x+50][y+50][z+50] = cuboid->on; 175 } 176 } 177 } 178 } 179 } 180 } 181 182 long long count_cubes(bool (*cubes)[101][101][101]) { 183 long long count = 0; 184 for (int x = 0; x <= 100; ++x) { 185 for (int y = 0; y <= 100; ++y) { 186 for (int z = 0; z <= 100; ++z) { 187 count += (*cubes)[x][y][z]; 188 } 189 } 190 } 191 return count; 192 } 193 194 void parse_cuboid(struct array_t *array, const char *str) { 195 assert(str != NULL); 196 assert(array != NULL); 197 assert(strlen(str) > 5); 198 struct cuboid_t cuboid = {0}; 199 int offset = 0; 200 if (strncmp(str, "on", 2) == 0) { 201 cuboid.on = true; 202 offset = 3; 203 } else if (strncmp(str, "off", 3) == 0) { 204 cuboid.on = false; 205 offset = 4; 206 } else { 207 printf("invalid string %s", str); 208 return; 209 } 210 211 char *tmp = strndup(str+offset, STR_LEN); 212 assert(tmp != NULL); 213 char *token = NULL; 214 215 while ((token = strsep(&tmp, ",")) != NULL) { 216 if (*token == '\n' || *token == '\0') break; 217 218 char *tmp2 = strndup(token + 2, STR_LEN); 219 assert(tmp2 != NULL); 220 char *t = NULL; 221 int nums[2] = {0}; 222 int cnt = 0; 223 while ((t = strsep(&tmp2, ".")) != NULL) { 224 if (*t != '\n' && *t != '\0') { 225 nums[cnt++] = atoi(t); 226 } 227 } 228 if (token[0] == 'x') { 229 cuboid.x1 = nums[0]; 230 cuboid.x2 = nums[1]; 231 } else if (token[0] == 'y') { 232 cuboid.y1 = nums[0]; 233 cuboid.y2 = nums[1]; 234 } else if (token[0] == 'z') { 235 cuboid.z1 = nums[0]; 236 cuboid.z2 = nums[1]; 237 } else { 238 printf("invalid string %s\n", tmp); 239 } 240 free(tmp2); 241 } 242 free(tmp); 243 244 if (array->count >= array->cap) array_expand(array); 245 struct cuboid_t *cuboids = array->data; 246 cuboids[array->count++] = cuboid; 247 } 248 249 long long cuboid_size(struct cuboid_t *cuboid) { 250 return (cuboid->x2 - cuboid->x1) * (cuboid->y2 - cuboid->y1) * (cuboid->z2 - cuboid->z1); 251 }