puzzle.c (6690B)
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 <stdbool.h> 10 #include <unistd.h> 11 #include <math.h> 12 13 #include "util.h" 14 15 #define STR_LEN 1024 16 17 struct num_t { 18 int value; 19 int depth; 20 }; 21 22 void parse(const char *str, struct array_t *array); 23 void print_nums(struct array_t *array); 24 void array_remove(struct array_t *nums, size_t index); 25 void array_insert(struct array_t *nums, size_t index, struct num_t num); 26 void array_add(struct array_t *nums, struct num_t num); 27 bool explode(struct array_t *nums); 28 bool split(struct array_t *nums); 29 void add(struct array_t *to, struct array_t *from); 30 int magnitude(struct array_t *nums); 31 int max_magnitude(struct array_t *all_nums); 32 int compare(const void *l, const void *r); 33 34 void puzzle(const char *filename, long long *result1, long long *result2) { 35 FILE *infile = fopen(filename, "r"); 36 if (infile == NULL) { 37 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 38 return; 39 } 40 41 char buf[STR_LEN] = {0}; 42 unsigned int line_num = 0; 43 44 *result1 = 0; 45 *result2 = 0; 46 47 struct array_t nums = { .data = NULL }; 48 array_init(&nums, sizeof(struct num_t), 10); 49 50 struct array_t all_nums = { .data = NULL }; 51 array_init(&all_nums, sizeof(struct array_t), 10); 52 53 while (fgets(buf, STR_LEN, infile) != NULL) { 54 if (all_nums.count >= all_nums.cap) array_expand(&all_nums); 55 56 struct array_t nums_add = { .data = NULL }; 57 array_init(&nums_add, sizeof(struct num_t), 10); 58 parse(buf, &nums_add); 59 60 ((struct array_t *)all_nums.data)[all_nums.count++] = array_copy(&nums_add); 61 if (nums.count == 0) { // first line 62 nums = nums_add; 63 continue; 64 } 65 add(&nums, &nums_add); 66 while (explode(&nums) || split(&nums)) { 67 // 68 } 69 ++line_num; 70 bzero(buf, STR_LEN); 71 } 72 73 *result1 = magnitude(&nums); 74 *result2 = max_magnitude(&all_nums); 75 76 free(nums.data); 77 // mutiny! ignoring feof/ferror. 78 fclose(infile); 79 } 80 81 int compare(const void *l, const void *r) { 82 return *(int *)r - *(int *)l; 83 } 84 85 int max_magnitude(struct array_t *all_nums) { 86 struct array_t magnitudes = { .data = NULL }; 87 array_init(&magnitudes, sizeof(int), all_nums->count * all_nums->count); 88 int *magnitudes_data = magnitudes.data; 89 assert(magnitudes_data != NULL); 90 91 struct array_t *all_nums_data = all_nums->data; 92 for (size_t i = 0; i < all_nums->count; ++i) { 93 for (size_t j = 0; j < all_nums->count; ++j) { 94 if (i == j) continue; 95 struct array_t nums_copy = array_copy(&all_nums_data[i]); 96 add(&nums_copy, &all_nums_data[j]); 97 while (explode(&nums_copy) || split(&nums_copy)) { 98 // 99 } 100 magnitudes_data[magnitudes.count++] = magnitude(&nums_copy); 101 free(nums_copy.data); 102 } 103 } 104 105 qsort(magnitudes_data, magnitudes.count, magnitudes.elem_size, compare); 106 int max_mag = magnitudes_data[0]; 107 free(magnitudes.data); 108 return max_mag; 109 } 110 111 int magnitude(struct array_t *nums) { 112 assert(nums != NULL); 113 while (nums->count > 1) { 114 struct num_t *data = nums->data; 115 for (size_t i = 0; i < nums->count-1; ++i) { 116 if (data[i].depth == data[i+1].depth) { 117 int mag = data[i].value*3 + data[i+1].value*2; 118 struct num_t mul = {.value=mag, .depth=data[i].depth-1}; 119 data[i] = mul; 120 array_remove(nums, i+1); 121 break; 122 } 123 } 124 } 125 struct num_t *data = nums->data; 126 return data[0].value; 127 } 128 129 void add(struct array_t *to, struct array_t *from) { 130 assert(to != NULL); 131 assert(from != NULL); 132 assert(to->elem_size == from->elem_size); 133 array_expand1(to, to->cap + from->cap); 134 assert(to->data != NULL); 135 struct num_t *to_data = to->data; 136 struct num_t *from_data = from->data; 137 for (size_t i = 0; i < to->count; ++i) { 138 to_data[i].depth++; 139 } 140 for (size_t i = 0; i < from->count; ++i) { 141 struct num_t num = from_data[i]; 142 num.depth++; 143 to_data[to->count++] = num; 144 } 145 } 146 147 bool explode(struct array_t *nums) { 148 assert(nums->count > 1); 149 struct num_t *array = nums->data; 150 for (size_t i = 0; i < nums->count-1; ++i) { 151 if (array[i].depth > 4 && array[i].depth == array[i+1].depth) { 152 if (i > 0) { 153 array[i-1].value += array[i].value; 154 } 155 if (i < nums->count-2) { 156 array[i+2].value += array[i+1].value; 157 } 158 array[i].depth--; 159 array[i].value = 0; 160 array_remove(nums, i+1); 161 return true; 162 } 163 } 164 return false; 165 } 166 167 bool split(struct array_t *nums) { 168 assert(nums->count > 1); 169 struct num_t *array = nums->data; 170 for (size_t i = 0; i < nums->count; ++i) { 171 if (array[i].value > 9) { 172 double l = floor((double)array[i].value / 2.0); 173 double r = ceil((double)array[i].value / 2.0); 174 int depth = array[i].depth; 175 array_remove(nums, i); 176 array = nums->data; 177 if (i >= nums->count) { 178 array_add(nums, (struct num_t){.value=l, .depth=depth+1}); 179 array_add(nums, (struct num_t){.value=r, .depth=depth+1}); 180 } else { 181 array_insert(nums, i, (struct num_t){.value=r, .depth=depth+1}); 182 array_insert(nums, i, (struct num_t){.value=l, .depth=depth+1}); 183 } 184 return true; 185 } 186 } 187 return false; 188 } 189 190 void parse(const char *str, struct array_t *array) { 191 size_t len = strlen(str); 192 int depth = 0; 193 for (size_t i = 0; i < len-1; ++i) { 194 if (str[i] == '[') { 195 depth++; 196 } else if (str[i] == ']') { 197 depth--; 198 } else if (str[i] >= '0' && str[i] <= '9') { 199 if (array->count >= array->cap) array_expand(array); 200 ((struct num_t *)array->data)[array->count++] = (struct num_t){.value=str[i]-'0', .depth=depth}; 201 } 202 } 203 } 204 205 void print_nums(struct array_t *array) { 206 struct num_t *nums = array->data; 207 for (size_t i = 0; i < array->count; ++i) { 208 printf("%2d,", nums[i].value); 209 } 210 printf("\n"); 211 } 212 213 void array_remove(struct array_t *nums, size_t index) { 214 assert(index < nums->count); 215 struct num_t *data = nums->data; 216 struct num_t *new_data = calloc(nums->count-1, nums->elem_size); 217 assert(new_data != NULL); 218 size_t new_count = 0; 219 for (size_t i = 0; i < nums->count; ++i) { 220 if (i != index) { 221 new_data[new_count++] = data[i]; 222 } 223 } 224 free(data); 225 nums->data = new_data; 226 nums->count = new_count; 227 nums->cap = new_count; 228 } 229 230 void array_insert(struct array_t *nums, size_t index, struct num_t num) { 231 assert(index < nums->count); 232 struct num_t *data = nums->data; 233 struct num_t *new_data = calloc(nums->count + 1, nums->elem_size); 234 assert(new_data != NULL); 235 size_t new_count = 0; 236 for (size_t i = 0; i < nums->count; ++i) { 237 if (i == index) { 238 new_data[new_count++] = num; 239 new_data[new_count++] = data[i]; 240 } else { 241 new_data[new_count++] = data[i]; 242 } 243 } 244 nums->data = new_data; 245 nums->count = new_count; 246 nums->cap = new_count; 247 } 248 249 250 void array_add(struct array_t *nums, struct num_t num) { 251 assert(nums != NULL); 252 if (nums->count >= nums->cap) array_expand(nums); 253 struct num_t *data = nums->data; 254 data[nums->count++] = num; 255 }