puzzle.c (6758B)
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 10 #define BUF_SIZE 65 11 12 struct packet_t { 13 uint8_t version; 14 uint8_t type; 15 uint64_t value; 16 uint16_t packets_size; 17 struct packet_t **packets; 18 }; 19 20 uint8_t hex2int(const int symbol); 21 char * int2bin(const uint8_t digit); 22 uint64_t str2int(char *str, size_t size); 23 uint64_t get_value(char *str, size_t *offset); 24 struct packet_t * get_packet(char *str, size_t *offset); 25 void delete_packet(struct packet_t *packet); 26 uint64_t calc_packet_sum(struct packet_t *packet); 27 uint64_t calc_packet(struct packet_t *packet); 28 uint64_t packet_sum(struct packet_t *packet); 29 uint64_t packet_mul(struct packet_t *packet); 30 uint64_t packet_min(struct packet_t *packet); 31 uint64_t packet_max(struct packet_t *packet); 32 uint64_t packet_gt(struct packet_t *packet); 33 uint64_t packet_lt(struct packet_t *packet); 34 uint64_t packet_eq(struct packet_t *packet); 35 36 void puzzle(const char *filename, long long *result1, long long *result2) { 37 FILE *infile = fopen(filename, "r"); 38 if (infile == NULL) { 39 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 40 return; 41 } 42 43 *result1 = 0; 44 *result2 = 0; 45 46 int symbol = 0; 47 char *binary = NULL; 48 size_t binary_size = 1; 49 50 binary = malloc(binary_size); 51 assert(binary != NULL); 52 binary[0] = '\0'; 53 54 while ((symbol = fgetc(infile)) != EOF) { 55 if (symbol == '\n') break; 56 uint8_t digit = hex2int(symbol); 57 binary_size += 4; 58 binary = realloc(binary, binary_size); 59 strlcat(binary, int2bin(digit), binary_size); 60 } 61 62 size_t offset = 0; 63 struct packet_t *packet = get_packet(binary, &offset); 64 assert(packet != NULL); 65 *result1 = calc_packet_sum(packet); 66 *result2 = calc_packet(packet); 67 68 delete_packet(packet); 69 free(binary); 70 // mutiny! ignoring feof/ferror. 71 fclose(infile); 72 } 73 74 uint64_t calc_packet_sum(struct packet_t *packet) { 75 uint32_t sum = packet->version; 76 if (packet->type != 4) { 77 for (uint16_t i = 0; i < packet->packets_size; ++i) { 78 sum += calc_packet_sum(packet->packets[i]); 79 } 80 } 81 return sum; 82 } 83 84 uint64_t calc_packet(struct packet_t *packet) { 85 switch (packet->type) { 86 case 0: 87 return packet_sum(packet); 88 case 1: 89 return packet_mul(packet); 90 case 2: 91 return packet_min(packet); 92 case 3: 93 return packet_max(packet); 94 case 4: 95 return packet->value; 96 case 5: 97 return packet_gt(packet); 98 case 6: 99 return packet_lt(packet); 100 case 7: 101 return packet_eq(packet); 102 } 103 return 0; 104 } 105 106 uint64_t packet_sum(struct packet_t *packet) { 107 uint64_t val = 0; 108 for (uint16_t i = 0; i < packet->packets_size; ++i) { 109 val += calc_packet(packet->packets[i]); 110 } 111 return val; 112 } 113 114 uint64_t packet_mul(struct packet_t *packet) { 115 uint64_t val = 1; 116 for (uint16_t i = 0; i < packet->packets_size; ++i) { 117 val *= calc_packet(packet->packets[i]); 118 } 119 return val; 120 } 121 122 uint64_t packet_min(struct packet_t *packet) { 123 assert(packet->packets_size > 0); 124 uint64_t val = calc_packet(packet->packets[0]); 125 for (uint16_t i = 1; i < packet->packets_size; ++i) { 126 uint64_t v = calc_packet(packet->packets[i]); 127 val = v < val ? v : val; 128 } 129 return val; 130 } 131 132 uint64_t packet_max(struct packet_t *packet) { 133 assert(packet->packets_size > 0); 134 uint64_t val = 0; 135 for (uint16_t i = 0; i < packet->packets_size; ++i) { 136 uint64_t v = calc_packet(packet->packets[i]); 137 val = v > val ? v : val; 138 } 139 return val; 140 } 141 142 uint64_t packet_gt(struct packet_t *packet) { 143 assert(packet->packets_size == 2); 144 uint64_t v1 = calc_packet(packet->packets[0]); 145 uint64_t v2 = calc_packet(packet->packets[1]); 146 return v1 > v2 ? 1 : 0; 147 } 148 149 uint64_t packet_lt(struct packet_t *packet) { 150 assert(packet->packets_size == 2); 151 uint64_t v1 = calc_packet(packet->packets[0]); 152 uint64_t v2 = calc_packet(packet->packets[1]); 153 return v1 < v2 ? 1 : 0; 154 } 155 156 uint64_t packet_eq(struct packet_t *packet) { 157 assert(packet->packets_size == 2); 158 uint64_t v1 = calc_packet(packet->packets[0]); 159 uint64_t v2 = calc_packet(packet->packets[1]); 160 return v1 == v2 ? 1 : 0; 161 } 162 163 void delete_packet(struct packet_t *packet) { 164 if (packet->type != 4) { 165 for (uint16_t i = 0; i < packet->packets_size; ++i) { 166 delete_packet(packet->packets[i]); 167 } 168 } 169 free(packet); 170 } 171 172 uint8_t hex2int(const int symbol) { 173 if (symbol >= '0' && symbol <= '9') { 174 return symbol - '0'; 175 } else if (symbol >= 'A' && symbol <= 'F') { 176 return symbol - 'A' + 10; 177 } 178 return 0; 179 } 180 181 char * int2bin(const uint8_t digit) { 182 static char bin[5]; 183 int cnt = 0; 184 // only "lower" 4 bits 185 for (int i = 8; i > 0; i >>= 1) { 186 bin[cnt++] = ((digit & i) == i) ? '1' : '0'; 187 } 188 bin[4] = '\0'; 189 return bin; 190 } 191 192 uint64_t str2int(char *str, size_t size) { 193 assert(size < BUF_SIZE); 194 static char data[BUF_SIZE] = {0}; 195 strlcpy(data, str, size+1); 196 return strtoull(data, NULL, 2); 197 } 198 199 struct packet_t * get_packet(char *str, size_t *offset) { 200 struct packet_t *packet = malloc(sizeof(struct packet_t)); 201 bzero(packet, sizeof(struct packet_t)); 202 size_t total_offset = 0; 203 204 packet->version = str2int(str+total_offset, 3); 205 total_offset += 3; 206 packet->type = str2int(str+total_offset, 3); 207 total_offset += 3; 208 209 if (packet->type == 4) { // literal values type 210 size_t local_offset = 0; 211 packet->value = get_value(str+total_offset, &local_offset); 212 total_offset += local_offset; 213 214 } else { // operator packet 215 uint16_t len_type = str2int(str+total_offset, 1); 216 total_offset += 1; 217 uint16_t len = 0; 218 219 if (len_type == 0) { // next 15 bits are length in bits 220 len = str2int(str+total_offset, 15); 221 total_offset += 15; 222 223 size_t sum_offset = 0; 224 packet->packets_size = 0; 225 while (sum_offset < len) { 226 packet->packets_size++; 227 size_t local_offset = 0; 228 struct packet_t *p = get_packet(str+total_offset, &local_offset); 229 assert(p != NULL); 230 sum_offset += local_offset; 231 total_offset += local_offset; 232 packet->packets = realloc(packet->packets, packet->packets_size * sizeof(void *)); 233 packet->packets[packet->packets_size - 1] = p; 234 } 235 *offset = sum_offset; 236 } else { // next 11 bits are number of packets 237 len = str2int(str+total_offset, 11); 238 total_offset += 11; 239 packet->packets_size = len; 240 packet->packets = calloc(len, sizeof(void *)); 241 for (uint16_t i = 0; i < len; ++i) { 242 size_t local_offset = 0; 243 struct packet_t *p = get_packet(str+total_offset, &local_offset); 244 assert(p != NULL); 245 total_offset += local_offset; 246 packet->packets[i] = p; 247 } 248 } 249 } 250 251 *offset = total_offset; 252 253 return packet; 254 } 255 256 uint64_t get_value(char *str, size_t *offset) { 257 uint64_t value = 0; 258 size_t local_offset = 0; 259 uint16_t flag = 1; 260 while (flag == 1) { 261 flag = str2int(str+local_offset, 1); 262 local_offset += 1; 263 uint64_t val = str2int(str+local_offset, 4); 264 value = (value << 4) + val; 265 local_offset += 4; 266 } 267 *offset = local_offset; 268 return value; 269 }