puzzle2.c (3914B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <errno.h> 4 #include <string.h> 5 #include <strings.h> 6 #include <stdbool.h> 7 #include <sys/stat.h> 8 #include <assert.h> 9 10 #include "util.h" 11 12 #define MAX_LEN 16 13 #define BITS_COUNT 12 14 #define STR_LEN 13 // BITS_COUNT + 1 (EOL/EOF or terminating byte) 15 #define FMT_STRING "%" FMT(STR_LEN) "s" 16 17 bool copy_numbers(const struct array_t *src, struct array_t *dst); 18 void move_numbers(struct array_t *src, struct array_t *dst); 19 bool filter_numbers_by_bit(struct array_t *numbers, int bit_num, bool (cmp)(size_t, size_t)); 20 21 bool compare_oxygen(size_t zeroes, size_t ones) { 22 return zeroes > ones; 23 } 24 25 bool compare_scrubber(size_t zeroes, size_t ones) { 26 return zeroes <= ones; 27 } 28 29 int puzzle2(const char *filename) { 30 FILE *infile = fopen(filename, "r"); 31 if (infile == NULL) { 32 PRINT_ERR(fopen) 33 return -1; 34 } 35 36 struct array_t numbers = { .data = NULL }; 37 38 // deducing the approx numbers array size from the filesize 39 struct stat filestats = {0}; 40 if (stat(filename, &filestats) == -1) { 41 PRINT_ERR(stat) 42 return -1; 43 } else { 44 array_init(&numbers, sizeof(long), filestats.st_size / STR_LEN); 45 assert(numbers.data != NULL); 46 } 47 48 char buf[MAX_LEN] = {0}; 49 char str[STR_LEN] = {0}; 50 51 while (fgets(buf, MAX_LEN, infile) != NULL) { 52 if (sscanf(buf, FMT_STRING, str) == 1) { 53 // just a precaution, good 'ole "allocate x2 if it doesn't fit anymore" 54 if (numbers.count >= numbers.cap) { 55 array_expand(&numbers); 56 } 57 long *data = (long *)numbers.data; 58 data[numbers.count++] = strtol(str, NULL, 2); 59 bzero(buf, MAX_LEN); 60 bzero(str, STR_LEN); 61 } 62 } 63 64 long oxygen_number = 0; 65 long scrubber_number = 0; 66 struct array_t oxygen = { .data = NULL }; 67 struct array_t scrubber = { .data = NULL }; 68 array_init(&oxygen, numbers.elem_size, 10); 69 array_init(&scrubber, numbers.elem_size, 10); 70 if (!copy_numbers(&numbers, &oxygen) || !copy_numbers(&numbers, &scrubber)) { 71 fprintf(stderr, "copy_numbers() error\n"); 72 return false; 73 } 74 75 for (int bit = BITS_COUNT - 1; bit >= 0; --bit) { 76 filter_numbers_by_bit(&oxygen, bit, compare_oxygen); 77 filter_numbers_by_bit(&scrubber, bit, compare_scrubber); 78 } 79 80 if (oxygen.count != 1 || scrubber.count != 1) { 81 fprintf(stderr, "Filter failed\n"); 82 goto finish; 83 } 84 85 oxygen_number = ((long *)oxygen.data)[0]; 86 scrubber_number = ((long *)scrubber.data)[0]; 87 88 // mutiny! ignoring feof/ferror. 89 finish: 90 free(numbers.data); 91 free(oxygen.data); 92 free(scrubber.data); 93 fclose(infile); 94 95 return oxygen_number * scrubber_number; 96 } 97 98 bool copy_numbers(const struct array_t *src, struct array_t *dst) { 99 if (src->data == NULL || src->count == 0 || src->cap == 0) 100 return false; 101 102 size_t dst_size = src->count * src->elem_size; 103 dst->data = realloc(dst->data, dst_size); 104 dst->count = src->count; 105 dst->cap = src->cap; 106 memcpy(dst->data, src->data, dst_size); 107 108 return true; 109 } 110 111 void move_numbers(struct array_t *src, struct array_t *dst) { 112 free(dst->data); 113 dst->data = src->data; 114 dst->count = src->count; 115 dst->cap = src->cap; 116 } 117 118 bool filter_numbers_by_bit(struct array_t *numbers, int bit_num, bool (cmp)(size_t, size_t)) { 119 if (numbers->count == 1) 120 return false; 121 122 struct array_t filtered_0 = { .data = NULL }; 123 array_init(&filtered_0, numbers->elem_size, numbers->count); 124 assert(filtered_0.data != NULL); 125 126 struct array_t filtered_1 = { .data = NULL }; 127 array_init(&filtered_1, numbers->elem_size, numbers->count); 128 assert(filtered_1.data != NULL); 129 130 long *data = numbers->data; 131 long *f0_data = filtered_0.data; 132 long *f1_data = filtered_1.data; 133 for (size_t i = 0; i < numbers->count; ++i) { 134 if (data[i] & (1 << bit_num)) { 135 f1_data[filtered_1.count++] = data[i]; 136 } else { 137 f0_data[filtered_0.count++] = data[i]; 138 } 139 } 140 141 if (cmp(filtered_0.count, filtered_1.count)) { 142 move_numbers(&filtered_0, numbers); 143 free(filtered_1.data); 144 } else { 145 move_numbers(&filtered_1, numbers); 146 free(filtered_0.data); 147 } 148 149 return true; 150 }