puzzle.c (3252B)
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 #include "util.h" 11 12 #define STR_LEN 1024 13 14 // simple stack operations on array_t 15 void array_push(struct array_t *array, char bracket); 16 char array_pop(struct array_t *array); 17 18 char validate_string(struct array_t *brackets, const char *str); 19 long long calc_score1(const char illegal); 20 long long calc_score2(struct array_t *brackets); 21 long long get_score2(const char c); 22 23 static int compare(const void *l, const void *r) { 24 long long d = *(long long *)l - *(long long *)r; 25 if (d > 0) return 1; 26 if (d < 0) return -1; 27 return 0; 28 } 29 30 void puzzle(const char *filename, long long *result1, long long *result2) { 31 FILE *infile = fopen(filename, "r"); 32 if (infile == NULL) { 33 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 34 return; 35 } 36 37 char buf[STR_LEN] = {0}; 38 unsigned int line_num = 0; 39 struct array_t scores = { .data = NULL }; 40 array_init(&scores, sizeof(long long), 10); 41 42 *result1 = 0; 43 44 while (fgets(buf, STR_LEN, infile) != NULL) { 45 struct array_t brackets = { .data = NULL }; 46 array_init(&brackets, sizeof(char), 10); 47 48 char illegal = validate_string(&brackets, buf); 49 if (illegal != 0) { 50 *result1 += calc_score1(illegal); 51 } else { 52 if (scores.count >= scores.cap) array_expand(&scores); 53 ((long long *)scores.data)[scores.count++] = calc_score2(&brackets); 54 } 55 56 free(brackets.data); 57 ++line_num; 58 bzero(buf, STR_LEN); 59 } 60 61 long long *scores_data = scores.data; 62 qsort(scores_data, scores.count, scores.elem_size, compare); 63 *result2 = scores_data[scores.count / 2]; 64 65 free(scores.data); 66 // mutiny! ignoring feof/ferror. 67 fclose(infile); 68 } 69 70 char validate_string(struct array_t *brackets, const char *str) { 71 size_t len = strlen(str); 72 assert(len > 2); // at least 2 characters + EOL 73 74 for (size_t i = 0; i < len; ++i) { 75 char c = str[i]; 76 switch (c) { 77 case '{': 78 array_push(brackets, '}'); 79 break; 80 case '(': 81 array_push(brackets, ')'); 82 break; 83 case '<': 84 array_push(brackets, '>'); 85 break; 86 case '[': 87 array_push(brackets, ']'); 88 break; 89 case '}': 90 case ')': 91 case '>': 92 case ']': { 93 if (array_pop(brackets) != c) { 94 return c; 95 } 96 break; 97 } 98 case '\n': 99 // do nothing 100 break; 101 default: 102 printf("invalid symbol: %c (#%d)\n", c, c); 103 } 104 } 105 106 return 0; 107 } 108 109 void array_push(struct array_t *array, char bracket) { 110 if (array->count >= array->cap) { 111 array_expand(array); 112 } 113 char *data = (char *)array->data; 114 data[array->count++] = bracket; 115 } 116 117 char array_pop(struct array_t *array) { 118 assert(array->count > 0); 119 char *data = (char *)array->data; 120 return data[--array->count]; 121 } 122 123 long long calc_score1(const char illegal) { 124 switch (illegal) { 125 case ')': 126 return 3; 127 case ']': 128 return 57; 129 case '}': 130 return 1197; 131 case '>': 132 return 25137; 133 default: 134 return 0; 135 } 136 } 137 138 long long calc_score2(struct array_t *brackets) { 139 long long score = 0; 140 while (brackets->count > 0) { 141 char c = array_pop(brackets); 142 score = score * 5 + get_score2(c); 143 } 144 return score; 145 } 146 147 long long get_score2(const char c) { 148 switch (c) { 149 case ')': 150 return 1; 151 case ']': 152 return 2; 153 case '}': 154 return 3; 155 case '>': 156 return 4; 157 default: 158 return 0; 159 } 160 }