advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs | README | LICENSE

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 }